JP6720844B2 - データ管理プログラム、データ管理方法及びデータ管理装置 - Google Patents

Description

本発明は、データを分散させて管理する技術に関する。

キーに対応付けられた値の集合を複数の記憶部に分散して記憶するシステムにおいて、同種のキーに係る値を同じ記憶部に配置すれば、当該キーによる探索の効率がよい。

但し、複数のキーを含むデータを登録する場合に、キー毎にデータを振り分けて配置する処理は煩雑となる。つまり、登録処理の負荷を考慮すれば、複数のキーを含むデータを一括していずれかの管理装置に割り当てることが望まれる。

国際公開第２０１３／０６１６８０号公報 特開２０１３−１５６９６０号公報

本発明の目的は、一側面では、探索効率が良くなるように、複数のキーを含むデータを配置することである。

一態様に係るデータ管理方法は、（Ａ）キー及び値を含む組の集合を分散して記憶する複数の記憶部のいずれかに、複数の組を追加する場合に、当該複数の組の各々に含まれるキーについて当該キーが値の探索のために用いられた頻度を特定し、（Ｂ）特定された頻度によって、複数の組の各々に含まれるキーに重みを付けて、複数の記憶部の各々について複数の組に含まれる複数のキーの、当該記憶部における包含度を算出し、（Ｃ）包含度に基づいて複数の組の追加先となる記憶部を選択する処理を含む。

一側面としては、探索効率が良くなるように、複数のキーを含むデータを配置できる。

図１は、接近記録を生成する様子を示す図である。 図２は、ネットワーク構成例を示す図である。 図３は、管理システムのハードウエア構成例を示す図である。 図４は、登録フェーズのシーケンスを示す図である。 図５は、収集データの例を示す図である。 図６は、蓄積データの例を示す図である。 図７は、通知データの例を示す図である。 図８は、管理テーブルの例を示す図である。 図９は、ブルームフィルタの例を示す図である。 図１０は、ブルームフィルタの例を示す図である。 図１１は、通知データの伝送例を示す図である。 図１２は、登録フェーズのシーケンスを示す図である。 図１３は、探索フェーズのシーケンスを示す図である。 図１４は、使用頻度テーブルの例を示す図である。 図１５は、合計ポイントの算出例を示す図である。 図１６は、管理ノードのモジュール構成例を示す図である。 図１７は、一次登録処理（Ａ）フローを示す図である。 図１８は、ブルームフィルタ判定処理（Ａ）フローを示す図である。 図１９は、一次登録処理（Ａ）フローを示す図である。 図２０は、ブルームフィルタ更新処理（Ａ）フローを示す図である。 図２１は、二次登録処理フローを示す図である。 図２２は、探索装置のモジュール構成例を示す図である。 図２３は、探索処理（Ａ）フローを示す図である。 図２４は、探索処理（Ａ）フローを示す図である。 図２５は、実施の形態２に係るブルームフィルタの例を示す図である。 図２６は、一次登録処理（Ｂ）フローを示す図である。 図２７は、ポイント加算処理フローを示す図である。 図２８は、一次登録処理（Ｂ）フローを示す図である。 図２９は、ブルームフィルタ更新処理（Ｂ）フローを示す図である。 図３０は、探索処理（Ｂ）フローを示す図である。 図３１は、ブルームフィルタ判定処理（Ｂ）フローを示す図である。 図３２は、コンピュータの機能ブロック図である。

［実施の形態１］
本実施の形態に係るデータ管理方法を適用した見守りサービスについて説明する。見守りサービスは、地域の住民が学童を見守ることを目的とする。地域の住民であるユーザが市中で学童に接近すると、ユーザ端末において記録を生成する。

図１に、ユーザ端末１０１において接近記録を生成する様子を示す図である。学童を見守るユーザは、ユーザ端末１０１ａを保持している。学童は、夫々ビーコン発信装置１０３を保持している。ユーザ端末１０１ａは、例えばスマートフォンである。ユーザ端末１０１ａは、近距離無線方式（例えば、ＢＬＥ（Bluetooth（登録商標） Low Energy）通信方式）の通信デバイス、時計、ＧＰＳ（Global Positioning System）装置及びカメラを有している。ビーコン発信装置１０３は、近距離無線方式によるビーコン信号を発信する。

ユーザとビーコン発信装置１０３ａを保持する学童との距離が縮まると、ユーザ端末１０１ａは、ビーコン発信装置１０３ａが発信するビーコン信号を受信する。ユーザ端末１０１ａは、ビーコン信号からビーコンＩＤを抽出する。ビーコン発信装置１０３ａが発信するビーコン信号に含まれるビーコンＩＤは、Ｂ０１である。ユーザ端末１０１ａは、時計部を用いてビーコン信号を受信した日時（以下、受信日時という。）を特定する。ユーザ端末１０１ａは、ＧＰＳ装置を用いてビーコン信号を受信した地理的位置を特定する。更に、ユーザ端末１０１ａは、ユーザに動画の撮影を促し、ユーザの操作に従って動画を撮影する。そして、ユーザ端末１０１ａは、ビーコンＩＤ、受信日時、地理的位置及び動画データを対応付けて記憶する。このとき記憶されるデータを、以下では接近記録という。この段階で、ビーコンＩＤのＢ０１と、受信日時のＴ２０１と、地理的位置のＰ２０１と、動画データのＭ２０１．ｍｐｅｇとを含む接近記録が生成される。

その後、ユーザとビーコン発信装置１０３ｂを保持する学童との距離が縮まると、ユーザ端末１０１ａは、ビーコン発信装置１０３ｂが発信するビーコン信号を受信する。ユーザ端末１０１ａは、当該ビーコン信号からビーコンＩＤのＢ０３を抽出する。この段階で、ビーコンＩＤのＢ０３と、受信日時のＴ２０２と、地理的位置のＰ２０２と、動画データのＭ２０２．ｍｐｅｇとを含む接近記録が生成される。

更に、ユーザとビーコン発信装置１０３ｃを保持する学童との距離が縮まると、ユーザ端末１０１ａは、ビーコン発信装置１０３ｃが発信するビーコン信号を受信する。ユーザ端末１０１ａは、ビーコン信号からビーコンＩＤのＢ０６を抽出する。この段階で、ビーコンＩＤのＢ０６と、受信日時のＴ２０３と、地理的位置のＰ２０３と、動画データのＭ２０３．ｍｐｅｇとを含む接近記録が生成される。

その後、ユーザ端末１０１で生成された接近記録は、市中の拠点に設けられた装置に集められる。図２に、ネットワーク構成例を示す。この例では、３つの拠点が設定されているものとする。各拠点のシステムでは、スイッチ２０５に、蓄積ノード２０１及びアクセスポイント２０３が接続されている。アクセスポイント２０３は、ユーザ端末１０１と無線ＬＡＮ（Local Area Network）の通信を行う。蓄積ノード２０１は、ユーザ端末１０１から収集した接近記録を蓄積する。

また、各拠点のシステムは、広域ネットワークを介して管理システム２０７に接続している。広域ネットワークは、例えば企業内のネットワークやインターネットである。

図３に、管理システム２０７のハードウエア構成例を示す。管理システム２０７におけるスイッチ３０５に、複数の管理ノード３０１ａ乃至３０１ｃ等、及び探索装置３０３が接続している。複数の管理ノード３０１ａ乃至３０１ｃ等は、接近記録が蓄積されている場所、つまり蓄積ノードＩＤを管理する。具体的には、複数の管理ノード３０１ａ乃至３０１ｃは、接近記録に含まれるビーコンＩＤと蓄積ノードＩＤとの組を分散して保持する。このように、データを分散させれば、接近記録を多く集める場合に対処し易い。

続いて、接近記録が追加される登録フェーズについて説明する。図４に、登録フェーズのシーケンスを示す。アクセスポイント２０３ａを介してユーザ端末１０１ａと蓄積ノード２０１ａとが接続すると、ユーザ端末１０１ａは、収集データを蓄積ノード２０１ａへ送信する（Ｓ４０１）。

図５に、収集データの例を示す。収集データは、接近記録の集合である。図５に示した収集データは、図１に示した３つの接近記録をまとめたものである。接近記録は、ビーコンＩＤが格納されるフィールドと、受信日時が格納されるフィールドと、地理的位置が格納されるフィールドと、動画データが格納されるフィールドとを有している。

図４の説明に戻る。蓄積ノード２０１ａは、受信した収集データを、自ら保持する蓄積データに加える（Ｓ４０３）。

図６に、蓄積データの例を示す。蓄積データには、受信した収集データの接近記録が蓄積される。図示した蓄積データは、図５に示した収集データの接近記録が追加された状態を示している。第３レコードから第５レコードは、図５に示した収集データの接近記録と同じである。

図４の説明に戻る。蓄積ノード２０１ａは、追加した収集データに含まれるビーコンＩＤに関する通知データを管理ノード３０１ａへ送信する（Ｓ４０５）。

図７に、通知データの例を示す。通知データのヘッダには、接近記録が追加された蓄積ノード２０１のＩＤが設定される。通知データのレコードには、追加された接近記録に含まれているビーコンＩＤが設定される。この通知データの例は、Ｂ０１、Ｂ０３及びＢ０６というビーコンＩＤを含む接近記録がＳ０１というＩＤで特定される蓄積ノード２０１に追加されたことを示している。

図４の説明に戻る。管理ノード３０１ａは、通知データを受信すると、当該通知データの内容を自ら管理するか否かを判断する。ここで、管理ノード３０１ａは、自ら管理すると判断したものとする（Ｓ４０７）。このときの判断方法については、後述する。

通知データの内容を自ら管理する場合には、管理ノード３０１ａは、当該通知データの内容を、自ら保持する管理テーブルに加える（Ｓ４０９）。

図８に、管理テーブルの例を示す。管理テーブルのレコードは、ビーコンＩＤが格納されるフィールドと、蓄積ノードＩＤが格納されるフィールドとを有している。このレコードに格納されるビーコンＩＤは、通知データに設定されているビーコンＩＤである。同じく蓄積ノードＩＤは、通知データに設定されている蓄積ノードＩＤである。この例における第３レコードは、Ｂ０１というビーコンＩＤを含む接近記録が、Ｓ０２というＩＤで特定される蓄積ノード２０１に蓄積されていることを示している。

図４の説明に戻る。管理ノード３０１ａは、自ら保持する管理テーブルに対応するブルームフィルタを更新する（Ｓ４１１）。

ブルームフィルタは、一般的にキーが集合に含まれるか否かを判別するために用いられる。見守りサービスにおけるビーコンＩＤは、キーに相当する。同じく管理テーブルは、集合に相当する。本実施の形態におけるブルームフィルタは、従来技術の通りである。

図９に、ブルームフィルタの例を示す。ブルームフィルタは、配列形式のデータである。この例で、配列要素は１ビットであり、配列要素の数はｍ個である。ビットは、インデックスによって特定される。この例で、配列数はｍ個であるので、インデックスは０〜ｍ−１の自然数である。初期状態において、各ビットには０が設定されている。

ブルームフィルタを用いるために、ｋ個のハッシュ関数が用意されている。各ハッシュ関数は、キーを０〜ｍ−１のインデックスに変換する。つまり、キーを各ハッシュ関数に入力することによって、ｋ個のインデックスを得る。新たなキーを集合に加える場合に、インデックスで特定されるビットが０であれば、１に変更される。インデックスで特定されるビットが既に１であれば、変更されない。

図９は、最初にキーＡが集合に加えられた場合にブルームフィルタが更新される様子を示している。キーＡを入力した第１ハッシュ関数は、インデックスの値８を出力する。そして、ブルームフィルタのビット［８］が１に変更される。キーＡを入力した第２ハッシュ関数は、インデックスの値１を出力する。そして、ブルームフィルタのビット［１］が１に変更される。キーＡを入力した第ｋハッシュ関数は、インデックスの値１１を出力する。そして、ブルームフィルタのビット［１１］が１に変更される。第３ハッシュ関数乃至第ｋ−１ハッシュ関数についても同様である。

続いてキーＢが集合に加えられた場合にブルームフィルタが更新される様子を、図１０に示す。キーＢを入力した第１ハッシュ関数は、インデックスの値０を出力する。そして、ブルームフィルタのビット［０］が１に変更される。キーＢを入力した第２ハッシュ関数は、インデックスの値１を出力する。但し、ブルームフィルタのビット［１］は、既に１であるので変更されない。キーＢを入力した第ｋハッシュ関数は、インデックスの値８を出力する。そして、ブルームフィルタのビット［８］も、既に１であるので変更されない。第３ハッシュ関数乃至第ｋ−１ハッシュ関数についても同様である。

このようにして、キーをｋ個のビットにマッピングすることによって、キーが集合に加えられたことを記録する。一方、あるキーが集合に含まれるか判定する場合には、上述と同様に当該キーから変換されたｋ個のインデックスによって特定されたビットがすべて１であるか否かを判定する。そして、ｋ個のインデックスによって特定されたビットがすべて１である場合に、当該キーが集合に含まれると判定する。一方、ｋ個のインデックスによって特定されたビットのうち１つでも０である場合には、当該キーが集合に含まれないと判定する。以上で、ブルームフィルタについての説明を終える。

上述した通知データの流れについて説明を加える。図１１に、通知データの伝送例を示す。上述した例では、蓄積ノード２０１ａが通知データを管理ノード３０１ａへ送信し（Ｓ１１０１）、通知データを受信した管理ノード３０１ａ自身が当該通知データの内容を管理する。但し、蓄積ノード２０１から通知データを受信した管理ノード３０１自身が、常に当該通知データの内容を管理するとは限らない。通知データを受信した管理ノード３０１が、他の管理ノード３０１に当該通知データの内容を管理させると判断することもある。図示するように、蓄積ノード２０１ｂが通知データを管理ノード３０１ｂへ送信した場合に（Ｓ１１０３）、通知データを受信した管理ノード３０１ｂが当該通知データの内容を管理ノード３０１ａに管理させると判断すれば、当該通知データは管理ノード３０１ａに転送される（Ｓ１１０５）。

このように、登録フェーズにおいて、管理ノード３０１ｂが通知データを管理ノード３０１ａに転送する場合のシーケンスを、図１２に示す。ユーザ端末１０１ｂと蓄積ノード２０１ｂとが接続すると、ユーザ端末１０１ｂは、収集データを蓄積ノード２０１ｂへ送信する（Ｓ１２０１）。

蓄積ノード２０１ｂは、受信した収集データを、自ら保持する蓄積データに加える（Ｓ１２０３）。そして、蓄積ノード２０１ｂは、追加した収集データに含まれるビーコンＩＤに関する通知データを管理ノード３０１ｂへ送信する（Ｓ１２０５）。

管理ノード３０１ｂは、通知データを受信すると、当該通知データの内容を管理ノード３０１ａに管理させると判断するものとする（Ｓ１２０７）。そして、管理ノード３０１ｂは、蓄積ノード２０１ｂから受信した通知データを管理ノード３０１ａへ転送する（Ｓ１２０９）。

管理ノード３０１ａは、管理ノード３０１ｂから転送された通知データを受け付けると、当該通知データを、自ら保持する管理テーブルに加える（Ｓ１２１１）。そして、管理ノード３０１ａは、自ら保持する管理テーブルに対応するブルームフィルタを更新する（Ｓ１２１３）。以上で登録フェーズの概要の説明を終える。

続いて、図１３を用いて、学童の保護者であるユーザが接近記録を取得するための探索フェーズのシーケンスについて説明する。接近記録を取得しようとするユーザのユーザ端末１０１ｃから探索装置３０３へ、蓄積ノード２０１の照会が送られる（Ｓ１３０１）。この照会には、接近記録を指定するビーコンＩＤが含まれている。

蓄積ノード２０１の照会を受信した探索装置３０３は、管理ノード３０１毎に、ブルームフィルタを用いて当該管理ノード３０１において当該ビーコンＩＤが管理されているか否かを判定する。この例では、探索装置３０３は、まず管理ノード３０１ａ（Ｃ０１）で当該ビーコンＩＤが管理されていると判定したものとする（Ｓ１３０３）。

探索装置３０３は、指定されたビーコンＩＤを管理している管理ノード３０１ａに対して蓄積ノード２０１の照会を送る（Ｓ１３０５）。蓄積ノード２０１の照会には、指定されたビーコンＩＤが含まれている。この例では、探索装置３０３は、まず管理ノード３０１ａへ蓄積ノード２０１の照会を送る。

蓄積ノード２０１の照会を受信した管理ノード３０１ａは、自ら保持する蓄積データにおいて当該照会に含まれるビーコンＩＤをキーとして蓄積ノードＩＤの探索を行う（Ｓ１３０７）。そして、管理ノード３０１ａは、見つけ出した蓄積ノードＩＤを探索装置３０３へ送り返す（Ｓ１３０９）。

探索装置３０３は、次に管理ノード３０１ｂ（Ｃ０２）で当該ビーコンＩＤが管理されていないと判定したものとする（Ｓ１３１１）。この場合には、管理ノード３０１ｂに対して、蓄積ノード２０１の照会は送られない。同様の処理を、残りの管理ノード３０１に対しても行う。

探索装置３０３は、各管理ノード３０１に係る処理を終えると、それまでに受信した蓄積ノードＩＤをリストとしてユーザ端末１０１ｃへ送る（Ｓ１３１３）。

ユーザは、このリストを取得することによって、自ら指定したビーコンＩＤに係る接近記録がどの蓄積ノード２０１に保持されているかを知る。この例では、このリストに含まれる蓄積ノード２０１ａのＩＤであるＳ０１が含まれていたものとする。ユーザ端末１０１ｃは、蓄積ノード２０１ａに対して接近記録の要求を送信する（Ｓ１３１５）。接近記録の要求は、指定されたビーコンＩＤを含むものとする。

接近記録の要求を受信した蓄積ノード２０１ａは、自ら保持する蓄積データから、指定されたビーコンＩＤを含む接近記録を抽出する。そして抽出した接近記録をユーザ端末１０１ｃへ送り返す（Ｓ１３１７）。

上述したリストに複数の蓄積ノードＩＤが含まれる場合には、ユーザ端末１０１ｃは、他の蓄積ノード２０１へも接近記録の要求を送る。そして、ユーザ端末１０１ｃは、更に接近記録を取得する。このようにして、ユーザ端末１０１ｃは、所定のビーコンＩＤを含む接近記録を収集する。

ここで、本実施の形態において、通知データの追加先となる管理ノード３０１を判断する方法について説明する。管理ノード３０１は、通知データに含まれるビーコンＩＤと同一のビーコンＩＤが、蓄積ノードＩＤを探索するために用いられた頻度（以下、使用頻度という。）を特定する。使用頻度は、使用頻度テーブルを用いてカウントされる。

図１４に、使用頻度テーブルの例を示す。この例における使用頻度テーブルは、ビーコンＩＤに対応するレコード（以下、使用頻度レコードという。）を有している。使用頻度レコードは、ビーコンＩＤが格納されるフィールドと、使用頻度が格納されるフィールドとを有している。

使用頻度は、当該ビーコンＩＤが検索キーとして使用された頻度である。図示した１番目のレコードは、Ｂ０１というビーコンＩＤを検索キーとする探索が２０回行われたことを示している。

尚、この例では、使用頻度テーブルを探索装置３０３で保持する。但し、使用頻度テーブルを他の装置において保持するようにしてもよい。

このようにして管理されている使用頻度によって、通知データに含まれる各ビーコンＩＤに対して重み付けがなされる。そして、管理ノード３０１は、当該重み付けを反映して、複数の管理ノード３０１の各々における、通知データに含まれるビーコンＩＤの包含度を算出する。包含度は、以下に述べる合計ポイントとして算出される。

図１５を用いて、合計ポイントを算出する手順について説明する。この例で、通知データには、３つのビーコンＩＤ（Ｂ０１、Ｂ０３及びＢ０６）が含まれているものとする。合計ポイントは、各管理ノード３０１の管理テーブルにおいて包含しているビーコンＩＤの使用頻度を合算することによって求められる。

例えば、管理ノード３０１ａ（Ｃ０１）における管理テーブルは、Ｂ０１というビーコンＩＤを含んでいるが、Ｂ０３というビーコンＩＤ及びＢ０６というビーコンＩＤを含んでいない。そして、Ｂ０１というビーコンＩＤにおける使用頻度は２０であるので、合計ポイントは２０となる。

同じく管理ノード３０１ｂ（Ｃ０２）における管理テーブルは、Ｂ０１というビーコンＩＤを含んでいないが、Ｂ０３というビーコンＩＤ及びＢ０６というビーコンＩＤを含んでいる。そして、Ｂ０３というビーコンＩＤにおける使用頻度は５であり、Ｂ０６というビーコンＩＤにおける使用頻度は７である。従って、合計ポイントは１２となる。

同じく管理ノード３０１ｃ（Ｃ０３）における管理テーブルは、Ｂ０３というビーコンＩＤを含んでいるが、Ｂ０１というビーコンＩＤ及びＢ０６というビーコンＩＤを含んでいない。そして、Ｂ０３というビーコンＩＤにおける使用頻度は５であるので、合計ポイントは５となる。

このようにして算出された合計ポイントが大きい方、つまり包含度が高い方の管理ノード３０１を、通知データの追加先として選択する。以上で、本実施の形態の概要についての説明を終える。

続いて、管理ノード３０１の動作について説明する。図１６に、管理ノード３０１のモジュール構成例を示す。管理ノード３０１は、受信部１６０１、算出部１６０３、判定部１６０５、特定部１６０７、選択部１６０９、追加部１６１１、更新部１６１３、転送部１６１５、受付部１６１７、抽出部１６１９及び送信部１６２１を有する。

受信部１６０１は、種々のデータを受信する。算出部１６０３は、管理ノード３０１毎の合計ポイントを算出する。尚、この例における合計ポイントは、内部パラメータである。判定部１６０５は、ブルームフィルタ判定処理を実行する。特定部１６０７は、使用頻度テーブルにおいてビーコンＩＤの使用頻度を特定する。選択部１６０９は、通知データが追加される管理ノード３０１を選択する。追加部１６１１は、自ら保持する管理テーブルに通知データの内容を追加する。更新部１６１３は、ブルームフィルタ更新処理を実行する。転送部１６１５は、通知データを他の管理ノード３０１へ転送する。受付部１６１７は、他の管理ノード３０１から送られた通知データを受け付ける。抽出部１６１９は、管理テーブルからビーコンＩＤに対応する蓄積ノードＩＤを抽出する。送信部１６２１は、種々のデータを送信する。

管理ノード３０１は、更に第１ハッシュ関数乃至第ｋハッシュ関数に相当する各計算を行うハッシュ計算部を有する。第１ハッシュ計算部１６３１は、第１ハッシュ関数に相当する計算を行う。第２ハッシュ計算部１６３３は、第２ハッシュ関数に相当する計算を行う。第ｋハッシュ計算部１６３５は、第ｋハッシュ関数に相当する計算を行う。第３ハッシュ計算部乃至第ｋ−１ハッシュ計算部は、図示しない。

上述した受信部１６０１、算出部１６０３、判定部１６０５、特定部１６０７、選択部１６０９、追加部１６１１、更新部１６１３、転送部１６１５、受付部１６１７、抽出部１６１９、送信部１６２１及び各ハッシュ計算部は、ハードウエア資源（例えば、図３２）と、以下で述べる処理をプロセッサに実行させるプログラムとを用いて実現される。

また、管理ノード３０１は、通知記憶部１６５１、管理テーブル記憶部１６５３及びブルームフィルタ記憶部１６５５を有する。

通知記憶部１６５１は、受信した通知データを記憶する。管理テーブル記憶部１６５３は、管理テーブルを記憶する。ブルームフィルタ記憶部１６５５は、ブルームフィルタを記憶する。

上述した通知記憶部１６５１、管理テーブル記憶部１６５３及びブルームフィルタ記憶部１６５５は、ハードウエア資源（例えば、図３２）を用いて実現される。

続いて、管理ノード３０１における処理について説明する。まず、蓄積ノード２０１から通知データを受信した場合の処理（以下、一次登録処理という。）について説明する。本実施の形態における管理ノード３０１は、一次登録処理（Ａ）を実行する。図１７に、一次登録処理（Ａ）フローを示す。

受信部１６０１が蓄積ノード２０１から通知データを受信すると（Ｓ１７０１）、管理ノード３０１はＳ１７０３以下の処理を行う。算出部１６０３は、受信した通知データに含まれるビーコンＩＤを１つ特定する（Ｓ１７０３）。例えば、算出部１６０３は、通知データに設定されている順に１つのビーコンＩＤを特定する。

算出部１６０３は、管理ノード３０１を１つ特定する（Ｓ１７０５）。例えば、算出部１６０３は、管理ノードＩＤの昇順に１つの管理ノード３０１を特定する。

判定部１６０５は、ブルームフィルタ判定処理（Ａ）を実行する（Ｓ１７０７）。ブルームフィルタ判定処理（Ａ）では、Ｓ１７０３で特定されたビーコンＩＤが、Ｓ１７０５で特定された管理ノード３０１のブルームフィルタに適用される。その結果、判定部１６０５は、当該管理ノード３０１の管理テーブルに当該ビーコンＩＤが含まれているか否かを判定する。判定部１６０５は、当該ビーコンＩＤ及び当該管理ノード３０１のＩＤを引数として用いる。

図１８に、ブルームフィルタ判定処理（Ａ）フローを示す。判定部１６０５は、引数としてビーコンＩＤ及び管理ノードＩＤを得ると（Ｓ１８０１）、当該管理ノードＩＤに対応するブルームフィルタを特定する（Ｓ１８０３）。更に、判定部１６０５は、各ハッシュ関数に当該ビーコンＩＤを入力してｋ個のインデックスを得る（Ｓ１８０５）。つまり、各ハッシュ計算部による処理が実行される。

判定部１６０５は、Ｓ１８０５で得たインデックスを１つ特定する（Ｓ１８０７）。判定部１６０５は、Ｓ１８０３で特定したブルームフィルタにおいて当該インデックスで特定されるビットが１であるか否かを判定する（Ｓ１８０９）。

当該ブルームフィルタにおいて当該インデックスで特定されるビットが１ではないと判定した場合には、判定部１６０５は、引数の管理ノードＩＤで特定される管理テーブルにビーコンＩＤが含まれないと判定する（Ｓ１８１１）。そして、ブルームフィルタ判定処理（Ａ）を終え、呼び出し元の処理に復帰する。

一方、当該ブルームフィルタにおいて当該インデックスで特定されるビットが１であると判定した場合には、判定部１６０５は、未処理のインデックスがあるか否かを判定する（Ｓ１８１３）。未処理のインデックスがあると判定した場合には、Ｓ１８０７に示した処理に戻って、上述した処理を繰り返す。

一方、未処理のインデックスがないと判定した場合には、判定部１６０５は、引数の管理ノードＩＤで特定される管理テーブルにビーコンＩＤが含まれると判定する（Ｓ１８１５）。ブルームフィルタ判定処理（Ａ）を終えると、呼び出し元の処理に復帰する。

図１７の説明に戻る。算出部１６０３は、当該管理ノード３０１の管理テーブルに当該ビーコンＩＤが含まれると判定したか否かによって処理を分岐させる（Ｓ１７０９）。

当該管理ノード３０１の管理テーブルに当該ビーコンＩＤが含まれると判定した場合には、特定部１６０７は、使用頻度テーブルにおいて当該ビーコンＩＤの使用頻度を特定する（Ｓ１７１１）。算出部１６０３は、特定された使用頻度を当該管理ノード３０１の合計ポイントに加える（Ｓ１７１３）。そして、Ｓ１７１５の処理に移る。

一方、当該管理ノード３０１の管理テーブルに当該ビーコンＩＤが含まれないと判定した場合には、当該管理ノード３０１の合計ポイントを変えずに、Ｓ１７１５の処理に移る。

算出部１６０３は、未処理の管理ノード３０１があるか否かを判定する（Ｓ１７１５）。未処理の管理ノード３０１があると判定した場合には、Ｓ１７０５に示した処理に戻って、上述した処理を繰り返す。

一方、未処理の管理ノード３０１がないと判定した場合には、算出部１６０３は、未処理のビーコンＩＤがあるか否かを判定する（Ｓ１７１７）。未処理のビーコンＩＤがあると判定した場合には、Ｓ１７０３に示した処理に戻って、上述した処理を繰り返す。

一方、未処理のビーコンＩＤがないと判定した場合には、端子Ａを介して、図１９に示したＳ１９０１の処理に移る。

選択部１６０９は、合計ポイントが最大である管理ノード３０１を特定する（Ｓ１９０１）。このとき、特定される管理ノード３０１は、１つであると限らない。選択部１６０９は、複数の管理ノード３０１が特定されたか否かを判定する（Ｓ１９０３）。

複数の管理ノード３０１が特定されたと判定した場合、つまり最大である管理ノード３０１が２つ以上ある場合には、選択部１６０９は、特定された複数の管理ノード３０１の中に自らの管理ノード３０１が含まれるか否かを判定する（Ｓ１９０５）。

自らの管理ノード３０１が含まれると判定した場合には、選択部１６０９は、自らの管理ノード３０１を選択する（Ｓ１９０７）。その結果、追加部１６１１は、通知データに含まれるビーコンＩＤを自ら保持する管理テーブルに追加する（Ｓ１９０９）。このとき、通知データに含まれる蓄積ノードＩＤが各ビーコンＩＤに対応付けられる。そして、更新部１６１３は、ブルームフィルタ更新処理（Ａ）を実行する（Ｓ１９１１）。ブルームフィルタ更新処理（Ａ）では、管理ノード３０１自身が保持するブルームフィルタを更新する。

図２０に、ブルームフィルタ更新処理（Ａ）フローを示す。更新部１６１３は、通知データに含まれるビーコンＩＤを１つ特定する（Ｓ２００１）。更新部１６１３は、例えば通知データに設定されている順番に従って、１つのビーコンＩＤを特定する。

更新部１６１３は、各ハッシュ関数に当該ビーコンＩＤを入力してｋ個のインデックスを得る（Ｓ２００３）。

更新部１６１３は、Ｓ２００３で得たインデックスを１つ特定し（Ｓ２００５）、自ら保持するブルームフィルタにおいて当該インデックスで特定されるビットが０であるか否かを判定する（Ｓ２００７）。当該ビットが０であると判定した場合には、更新部１６１３は、当該ビットを１に変更する（Ｓ２００９）。一方、当該ビットが０でないと判定した場合には、つまり当該ビットが１である場合には、当該ビットを変更しない。

更新部１６１３は、未処理のインデックスがあるか否かを判定する（Ｓ２０１１）。未処理のインデックスがあると判定した場合には、Ｓ２００５に示した処理に戻って、上述した処理を繰り返す。

一方、未処理のインデックスがないと判定した場合には、更新部１６１３は、未処理のビーコンＩＤがあるか否かを判定する（Ｓ２０１３）。未処理のビーコンＩＤがあると判定した場合には、Ｓ２００１に示した処理に戻って、上述した処理を繰り返す。

一方、未処理のビーコンＩＤがないと判定した場合には、ブルームフィルタ更新処理（Ａ）を終える。そして、呼び出し元の処理に復帰する。

図１９の説明に戻る。ブルームフィルタ更新処理（Ａ）を終えると、端子Ｂを介して図１７に示したＳ１７０１の処理に戻る。

一方、図１９のＳ１９０５において、特定された複数の管理ノード３０１の中に自らの管理ノード３０１が含まれないと判定した場合には、選択部１６０９は、優先順位に従って管理ノード３０１を選択する（Ｓ１９１３）。優先順位は、予め設定されているものとする。転送部１６１５は、選択された管理ノード３０１に、Ｓ１７０１で受信した通知データを転送する（Ｓ１９１５）。そして、端子Ｂを介して図１７に示したＳ１７０１の処理に戻る。

また、図１９のＳ１９０３において、複数の管理ノード３０１が特定されていないと判定した場合、つまり最大である管理ノード３０１が１つである場合には、選択部１６０９は、特定された１つの管理ノード３０１を選択する（Ｓ１９１７）。転送部１６１５は、選択された管理ノード３０１に、Ｓ１７０１で受信した通知データを転送する（Ｓ１９１９）。但し、自らの管理ノード３０１を選択した場合には、Ｓ１９０９及びＳ１９１１と同様の処理が実行される。そして、端子Ｂを介して図１７に示したＳ１７０１の処理に戻る。

続いて、他の管理ノード３０１から転送された通知データを受け付けた場合の処理（以下、二次登録処理という。）について説明する。図２１に、二次登録処理フローを示す。

受付部１６１７が、他の管理ノード３０１から転送された通知データを受け付けると（Ｓ２１０１）、追加部１６１１は、通知データに含まれるビーコンＩＤを、自ら保持する管理テーブルに追加する（Ｓ２１０３）。このとき、通知データに含まれる蓄積ノードＩＤが各ビーコンＩＤに対応付けられる。そして、更新部１６１３は、ブルームフィルタ更新処理（Ａ）を実行する（Ｓ２１０５）。

ブルームフィルタ更新処理（Ａ）を終えると、Ｓ２１０１に示した処理に戻って、上述した処理を繰り返す。以上で、管理ノード３０１の動作についての説明を終える。

次に、探索装置３０３の動作について説明する。図２２に、探索装置３０３のモジュール構成例を示す。探索装置３０３は、受信部２２０１、判定部２２０３、照会部２２０５、送信部２２０７、計数部２２０９及び使用頻度記憶部２２３１を有する。

受信部２２０１は、各種データを受信する。判定部２２０３は、ブルームフィルタ判定処理を実行する。照会部２２０５は、管理ノード３０１に対して蓄積ノード２０１の照会を行う。送信部２２０７は、各種データを送信する。計数部２２０９は、ビーコンＩＤの使用頻度を計数する。

上述した受信部２２０１、判定部２２０３、照会部２２０５、送信部２２０７及び計数部２２０９は、ハードウエア資源（例えば、図３２）と、以下で述べる処理をプロセッサに実行させるプログラムとを用いて実現される。

使用頻度記憶部２２３１は、使用頻度テーブルを記憶する。使用頻度記憶部２２３１は、ハードウエア資源（例えば、図３２）を用いて実現される。

本実施の形態における探索装置３０３は、探索処理（Ａ）を実行する。図２３に、探索処理（Ａ）フローを示す。

受信部２２０１は、ユーザ端末１０１から、所望の接近記録が蓄積されている蓄積ノード２０１の照会を受信する（Ｓ２３０１）。当該蓄積ノード２０１の照会は、所望の接近記録を指定するビーコンＩＤを含む。

照会部２２０５は、管理ノード３０１を１つ特定する（Ｓ２３０５）。例えば、照会部２２０５は、管理ノードＩＤの昇順に１つの管理ノード３０１を特定する。

判定部２２０３は、ブルームフィルタ判定処理（Ａ）を実行する（Ｓ２３０７）。このとき、判定部２２０３は、Ｓ２３０１で受信した蓄積ノード２０１の照会に含まれるビーコンＩＤ及びＳ２３０５で特定された管理ノード３０１のＩＤを引数として用いる。尚、繰り返されるブルームフィルタ判定処理（Ａ）において、ビーコンＩＤからインデックスを得る処理が重複するので、２回目以降の処理は省略するようにしてもよい。

照会部２２０５は、当該管理ノード３０１の管理テーブルに当該ビーコンＩＤが含まれると判定したか否かによって処理を分岐させる（Ｓ２３０９）。当該管理ノード３０１の管理テーブルに当該ビーコンＩＤが含まれると判定した場合には、送信部２２０７は、当該管理ノード３０１へ蓄積ノード２０１の照会を送信する（Ｓ２３１１）。蓄積ノード２０１の照会は、当該ビーコンＩＤが含まれる。そして、受信部２２０１は、当該管理ノード３０１から当該ビーコンＩＤに対応する蓄積ノードＩＤを受信する（Ｓ２３１３）。蓄積ノードＩＤは、一時的に保持される。

一方、Ｓ２３０９において当該管理ノード３０１の管理テーブルに当該ビーコンＩＤが含まれないと判定した場合には、蓄積ノード２０１の照会を送信せずに、Ｓ２３１５の処理に移る。

照会部２２０５は、未処理の管理ノード３０１があるか否かを判定する（Ｓ２３１５）。未処理の管理ノード３０１があると判定した場合には、Ｓ２３０５に示した処理に戻って、上述した処理を繰り返す。一方、未処理の管理ノード３０１がないと判定した場合には、端子Ｃを介して、図２４に示したＳ２４０１の処理に移る。

送信部２２０７は、図２３のＳ２３１３で受信した蓄積ノードＩＤのリストを、蓄積ノード２０１の照会の送信元であるユーザ端末１０１へ送信する（Ｓ２４０１）。そして、計数部２２０９は、使用頻度テーブルにおいて、蓄積ノード２０１の照会に含まれるビーコンＩＤに対応する使用頻度に１を加える（Ｓ２４０３）。端子Ｄを介して、図２３に示したＳ２３０１の処理に戻る。

最後に、管理ノード３０１の処理について補足する。管理ノード３０１の受信部１６０１が、探索装置３０３から蓄積ノード２０１の照会を受信すると、管理ノード３０１の抽出部１６１９は、自ら保持する管理テーブルから、当該照会に含まれるビーコンＩＤに対応する蓄積ノードＩＤを抽出する。そして、管理ノード３０１の送信部１６２１は、蓄積ノードＩＤを探索装置３０３へ送信する。

本実施の形態によれば、ビーコンＩＤ及び蓄積ノードＩＤを含む複数組を一括して登録する場合に、探索される傾向に応じて同じビーコンＩＤに係る組を同じ管理ノード３０１に配置する。従って、登録処理の負荷を抑えつつ、探索処理の負荷を軽減できる。

また、ビーコンＩＤによって特定される接近記録へのアクセス効率が高まる。

［実施の形態２］
上述した実施の形態では、使用頻度テーブルにおいてビーコンＩＤが使用された頻度をカウントする例について説明したが、本実施の形態では、ブルームフィルタにおいてビーコンＩＤが使用された頻度をカウントする例について説明する。

図２５に、実施の形態２におけるブルームフィルタの例を示す。本実施の形態のブルームフィルタにおける配列要素はカウンタである。つまり、配列要素は、複数のビット（例えば、４ビット）を有する。そして、カウンタは、インデックスによって特定される。初期状態において、各カウンタには０に設定されている。新たなキーを集合に加える場合に、インデックスで特定されるカウンタの値が０であれば、当該カウンタの値は１に変更される。インデックスで特定されるカウンタの値が１以上であれば、当該カウンタの値は変更されない。

本実施の形態では、ビーコンＩＤが検索キーとして探索に使用される度に、当該ビーコンＩＤに基づくインデックスで特定される各カウンタの値に１が加えられる。図示した例で、この例は、初めてキーＢが探索に使用された場合にブルームフィルタが更新される様子を示している。キーＢを入力した第１ハッシュ関数は、インデックスの値０を出力する。そして、ブルームフィルタのカウンタ［０］が１から２に変更される。キーＢを入力した第２ハッシュ関数は、インデックスの値１を出力する。そして、ブルームフィルタのカウンタ［１］が１から２に変更される。キーＢを入力した第ｋハッシュ関数は、インデックスの値８を出力する。そして、ブルームフィルタのカウンタ［８］が１から２に変更される。本実施の形態で、カウンタは、ビーコンＩＤが使用された程度を示すものとして用いられる。尚、配列要素の数ｍとハッシュ関数の数ｋとが或る程度大きければ、あるビーコンＩＤに基づく各インデックスで特定されるカウンタの合計は、当該ビーコンＩＤの使用頻度と看做して構わない。

本実施の形態における管理ノード３０１は、一次登録処理（Ａ）に代えて、一次登録処理（Ｂ）を実行する。図２６に、一次登録処理（Ｂ）フローを示す。Ｓ１７０１の処理は、一次登録処理（Ａ）の場合と同様である。

算出部１６０３は、受信した通知データに含まれるビーコンＩＤを１つ特定する（Ｓ２６０１）。例えば、算出部１６０３は、通知データに設定されている順に１つのビーコンＩＤを特定する。

算出部１６０３は、管理ノード３０１を１つ特定する（Ｓ２６０３）。例えば、算出部１６０３は、管理ノードＩＤの昇順に１つの管理ノード３０１を特定する。

算出部１６０３は、ポイント加算処理を実行する（Ｓ２６０５）。ポイント加算処理では、ブルームフィルタの配列要素であるカウンタの値に基づいて、管理ノード３０１毎の合計ポイントを算出する。算出部１６０３は、受信した通知データに含まれるビーコンＩＤ及びＳ２６０３で特定された管理ノード３０１のＩＤを引数とする。

図２７に、ポイント加算処理フローを示す。算出部１６０３は、引数としてビーコンＩＤ及び管理ノードＩＤを得ると（Ｓ２７０１）、当該管理ノードＩＤに対応するブルームフィルタを特定する（Ｓ２７０３）。更に、算出部１６０３は、各ハッシュ関数に当該ビーコンＩＤを入力してｋ個のインデックスを得る（Ｓ２７０５）。

算出部１６０３は、Ｓ２７０５で得たインデックスを１つ特定する（Ｓ２７０７）。算出部１６０３は、Ｓ２７０３で特定したブルームフィルタにおいて当該インデックスで特定されるカウンタの値が１以上であるか否かを判定する（Ｓ２７０９）。

当該ブルームフィルタにおいて当該インデックスで特定されるカウンタの値が１以上であると判定した場合には、算出部１６０３は、カウンタの値を当該管理ノード３０１の合計ポイントに加える（Ｓ２７１１）。

一方、当該ブルームフィルタにおいて当該インデックスで特定されるカウンタの値が１以上でないと判定した場合、つまり当該ビットが０である場合には、算出部１６０３は、当該管理ノード３０１の合計ポイントを変えない。

そして、算出部１６０３は、未処理のインデックスがあるか否かを判定する（Ｓ２７１３）。未処理のインデックスがあると判定した場合には、Ｓ２７０７に示した処理に戻って、上述した処理を繰り返す。一方、未処理のインデックスがないと判定した場合には、ポイント加算処理を終えて、呼び出し元の処理に復帰する。

図２６の説明に戻る。ポイント加算処理を終えると、算出部１６０３は、未処理の管理ノード３０１があるか否かを判定する（Ｓ２６０７）。未処理の管理ノード３０１があると判定した場合には、Ｓ２６０３に示した処理に戻って、上述した処理を繰り返す。

一方、未処理の管理ノード３０１がないと判定した場合には、算出部１６０３は、未処理のビーコンＩＤがあるか否かを判定する（Ｓ２６０９）。未処理のビーコンＩＤがあると判定した場合には、Ｓ２６０１に示した処理に戻って、上述した処理を繰り返す。

一方、未処理のビーコンＩＤがないと判定した場合には、端子Ｅを介して、図２８に示したＳ１９０１の処理に移る。

図２８の説明に移る。Ｓ１９０１乃至Ｓ１９０９の処理は、一次登録処理（Ａ）の場合と同様である。

更新部１６１３は、ブルームフィルタ更新処理（Ｂ）を実行する（Ｓ２８０１）。図２９に、ブルームフィルタ更新処理（Ｂ）フローを示す。Ｓ２００１乃至Ｓ２００５の処理は、ブルームフィルタ更新処理（Ａ）の場合と同様である。

更新部１６１３は、自ら保持するブルームフィルタにおいて当該インデックスで特定されるカウンタの値が０であるか否かを判定する（Ｓ２９０１）。当該カウンタの値が０であると判定した場合には、更新部１６１３は、当該カウンタの値を１に変更する（Ｓ２９０３）。一方、当該カウンタの値が０ではないと判定した場合、つまり当該カウンタの値が１以上である場合には、更新部１６１３は、当該カウンタの値を変更しない。

Ｓ２０１１及びＳ２０１３の処理は、ブルームフィルタ更新処理（Ａ）の場合と同様である。ブルームフィルタ更新処理（Ｂ）を終えると、呼び出し元の処理に復帰する。

図２８の説明に戻る。ブルームフィルタ更新処理（Ｂ）を終えて復帰すると、端子Ｆを介して、図２６に示したＳ１７０１の処理に戻る。

Ｓ１９１３乃至Ｓ１９１９は、一次登録処理（Ａ）の場合と同様である。Ｓ１９１５の処理を終えた場合には、端子Ｆを介して、図２６に示したＳ１７０１の処理に戻る。Ｓ１９１９の処理を終えた場合にも、端子Ｆを介して、図２６に示したＳ１７０１の処理に戻る。

また、本実施の形態における探索装置３０３は、探索処理（Ａ）に代えて、探索処理（Ｂ）を実行する。図３０に、探索処理（Ｂ）フローを示す。Ｓ２３０１及びＳ２３０５の処理は、探索処理（Ａ）の場合と同様である。

Ｓ２３０５において管理ノード３０１を１つ特定すると、判定部２２０３は、ブルームフィルタ判定処理（Ｂ）を実行する（Ｓ３００１）。このとき、判定部２２０３は、図３０のＳ２３０１で受信した蓄積ノード２０１の照会に含まれるビーコンＩＤ及び図３０のＳ２３０５で特定された管理ノード３０１のＩＤを引数とする。

図３１に、ブルームフィルタ判定処理（Ｂ）フローを示す。Ｓ１８０１乃至Ｓ１８０７の処理は、ブルームフィルタ判定処理（Ａ）の場合と同様である。

Ｓ１８０７においてインデックスが１つ特定されると、判定部２２０３は、ブルームフィルタにおいて当該インデックスで特定されるカウンタの値が１以上であるか否かを判定する（Ｓ３１０１）。ブルームフィルタにおいて当該インデックスで特定されるカウンタの値が１以上でないと判定した場合、つまりカウンタの値が０である場合には、判定部２２０３は、引数の管理ノードＩＤで特定される管理テーブルにビーコンＩＤが含まれないと判定する（Ｓ１８１１）。そして、ブルームフィルタ判定処理（Ｂ）を終え、呼び出し元の処理に復帰する。

一方、ブルームフィルタにおいて当該インデックスで特定されるカウンタの値が１以上であると判定した場合、判定部２２０３は、未処理のインデックスがあるか否かを判定する（Ｓ１８１３）。Ｓ１８１３及びＳ１８１５の処理は、ブルームフィルタ判定処理（Ａ）の場合と同様である。

Ｓ１８１５で、引数の管理ノードＩＤで特定される管理テーブルにビーコンＩＤが含まれると判定した場合に、判定部２２０３は、ブルームフィルタにおいて、Ｓ１８０５で得られた各インデックスで特定されるカウンタに１を加える（Ｓ３１０３）。そして、ブルームフィルタ判定処理（Ｂ）を終え、呼び出し元の処理に復帰する。

図３０の説明に戻る。Ｓ２３０９乃至Ｓ２４０１の処理は、探索処理（Ａ）の場合と同様である。

本実施の形態によれば、ブルームフィルタ以外のカウンタを設けなくても済むので、キーが使用された頻度を管理し易くなる。

尚、配列要素であるカウンタのデータサイズは任意であるので、システム情報としてカウンタのデータサイズを設定し、設定されているデータサイズに従ってブルームフィルタの構成を変更できるようにしてもよい。

また、一つのブルームフィルタにおける各カウンタのデータサイズは、一律でなくてもよい。

以上本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上述の機能ブロック構成はプログラムモジュール構成に一致しない場合もある。

また、上で説明した各記憶領域の構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ、処理の順番を入れ替えることや複数の処理を並列に実行させるようにしても良い。

なお、上で述べた蓄積ノード２０１、管理ノード３０１及び探索装置３０３は、コンピュータ装置であって、図３２に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。

以上述べた本発明の実施の形態をまとめると、以下のようになる。

本実施の形態に係るデータ管理方法は、（Ａ）キー及び値を含む組の集合を分散して記憶する複数の記憶部のいずれかに、複数の組を追加する場合に、当該複数の組の各々に含まれるキーについて当該キーが値の探索のために用いられた頻度を特定し、（Ｂ）特定された頻度によって、複数の組の各々に含まれるキーに重みを付けて、複数の記憶部の各々について複数の組に含まれる複数のキーの、当該記憶部における包含度を算出し、（Ｃ）包含度に基づいて複数の組の追加先となる記憶部を選択する処理を含む。

このようにすれば、探索効率が良くなるように、複数のキーを含むデータを配置できる。

更に、上記記憶部毎に設けられた、キーをマッピングするための配列要素が３値以上であるブルームフィルタの当該配列要素を用いて上記頻度をカウントする処理を含むようにしてもよい。

このようにすれば、ブルームフィルタ以外のカウンタを設けなくても済むので、キーが使用された頻度を管理し易くなる。

更に、上記値は、キーに対応付けられた情報の格納場所を示すものであってもよい。

このようにすれば、キーに対応付けられた情報へのアクセス効率が高まる。

なお、上記方法による処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納されるようにしてもよい。尚、中間的な処理結果は、一般的にメインメモリ等の記憶装置に一時保管される。

以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。

（付記１）
キー及び値を含む組の集合を分散して記憶する複数の記憶部のいずれかに、複数の組を追加する場合に、当該複数の組の各々に含まれるキーについて当該キーが前記値の探索のために用いられた頻度を特定し、
特定された前記頻度によって、前記複数の組の各々に含まれる前記キーに重みを付けて、前記複数の記憶部の各々について前記複数の組に含まれる複数のキーの、当該記憶部における包含度を算出し、
前記包含度に基づいて前記複数の組の追加先となる記憶部を選択する
処理をコンピュータに実行させるデータ管理プログラム。

（付記２）
更に、
前記記憶部毎に設けられた、前記キーをマッピングするための配列要素が３値以上であるブルームフィルタの当該配列要素を用いて前記頻度をカウントする
処理を含む付記１記載のデータ管理プログラム。

（付記３）
前記値は、前記キーに対応付けられた情報の格納場所を示す
付記１又は２記載のデータ管理プログラム。

（付記４）
キー及び値を含む組の集合を分散して記憶する複数の記憶部のいずれかに、複数の組を追加する場合に、当該複数の組の各々に含まれるキーについて当該キーが前記値の探索のために用いられた頻度を特定し、
特定された前記頻度によって、前記複数の組の各々に含まれる前記キーに重みを付けて、前記複数の記憶部の各々について前記複数の組に含まれる複数のキーの、当該記憶部における包含度を算出し、
前記包含度に基づいて前記複数の組の追加先となる記憶部を選択する
処理を含み、コンピュータにより実行されるデータ管理方法。

（付記５）
キー及び値を含む組の集合を分散して記憶する複数の記憶部のいずれかに、複数の組を追加する場合に、当該複数の組の各々に含まれるキーについて当該キーが前記値の探索のために用いられた頻度を特定する特定部と、
特定された前記頻度によって、前記複数の組の各々に含まれる前記キーに重みを付けて、前記複数の記憶部の各々について前記複数の組に含まれる複数のキーの、当該記憶部における包含度を算出する算出部と、
前記包含度に基づいて前記複数の組の追加先となる記憶部を選択する選択部と
を有するデータ管理装置。

１０１ ユーザ端末 １０３ ビーコン発信装置
２０１ 蓄積ノード ２０３ アクセスポイント
２０５ スイッチ ２０７ 管理システム
３０１ 管理ノード ３０３ 探索装置
３０５ スイッチ １６０１ 受信部
１６０３ 算出部 １６０５ 判定部
１６０７ 特定部 １６０９ 選択部
１６１１ 追加部 １６１３ 更新部
１６１５ 転送部 １６１７ 受付部
１６１９ 抽出部 １６２１ 送信部
１６３１ 第１ハッシュ計算部 １６３３ 第２ハッシュ計算部
１６３５ 第ｋハッシュ計算部 １６５１ 通知記憶部
１６５３ 管理テーブル記憶部 １６５５ ブルームフィルタ記憶部
２２０１ 受信部 ２２０３ 判定部
２２０５ 照会部 ２２０７ 送信部
２２０９ 計数部 ２２３１ 使用頻度記憶部

Claims (5)

1. キー及び値を含む組の集合を分散して記憶する複数の記憶部のいずれかに、複数の組を追加する場合に、当該複数の組の各々に含まれるキーについて当該キーが前記値の探索のために用いられた頻度を特定し、
   特定された前記頻度によって、前記複数の組の各々に含まれる前記キーに重みを付けて、前記複数の記憶部の各々について前記複数の組に含まれる複数のキーの、当該記憶部における包含度を算出し、
   前記包含度に基づいて前記複数の組の追加先となる記憶部を選択する
   処理をコンピュータに実行させるデータ管理プログラム。
2. 更に、
   前記記憶部毎に設けられた、前記キーをマッピングするための配列要素が３値以上であるブルームフィルタの当該配列要素を用いて前記頻度をカウントする
   処理を含む請求項１記載のデータ管理プログラム。
3. 前記値は、前記キーに対応付けられた情報の格納場所を示す
   請求項１又は２記載のデータ管理プログラム。
4. キー及び値を含む組の集合を分散して記憶する複数の記憶部のいずれかに、複数の組を追加する場合に、当該複数の組の各々に含まれるキーについて当該キーが前記値の探索のために用いられた頻度を特定し、
   特定された前記頻度によって、前記複数の組の各々に含まれる前記キーに重みを付けて、前記複数の記憶部の各々について前記複数の組に含まれる複数のキーの、当該記憶部における包含度を算出し、
   前記包含度に基づいて前記複数の組の追加先となる記憶部を選択する
   処理を含み、コンピュータにより実行されるデータ管理方法。
5. キー及び値を含む組の集合を分散して記憶する複数の記憶部のいずれかに、複数の組を追加する場合に、当該複数の組の各々に含まれるキーについて当該キーが前記値の探索のために用いられた頻度を特定する特定部と、
   特定された前記頻度によって、前記複数の組の各々に含まれる前記キーに重みを付けて、前記複数の記憶部の各々について前記複数の組に含まれる複数のキーの、当該記憶部における包含度を算出する算出部と、
   前記包含度に基づいて前記複数の組の追加先となる記憶部を選択する選択部と
   を有するデータ管理装置。

Images