(57)【要約】【課題】キーワード検索の課題は同一のキーワードにマッチするコンテンツ数が多くなると所望のインデックス情報を効率よく得ることである。この課題は，条件付き検索を行うことで，ある程度解決することができるが，これまでのP2P DHTは2語以上のキーワードを含む検索には対応していない。本発明では，代表的な条件付き検索法であるAND検索をP2P DHT上で効率良く実現するための新しい手法を提案する。【課題を解決するための手段】データベースの効率的な検索手法のリザルトキャッシュを用い，キャッシュされる連言を共有化し，有限のキャッシュ空間を効率よく利用する。またブルームフィルタを応用し，ピア間で交換・共有することで，ある連言がキャッシュ上に存在していないことを，ほかのピアに問合せしなくても，局所的な計算のみによって確かめることが出来，システムに対する無駄な問合せを削減する。【選択図】  なし【特許請求の範囲】
【請求項１】
P2P DHT上で、AND検索を効率良く実現するための、情報検索のための情報処理方法において、
各ピアが過去に行った検索の結果をローカルなディスク上にキャッシュする手段と，
キャッシュされた情報へのインデックス情報をシステム上に別途登録する手段と，
キャッシュ情報の共有化を図る手段と、
を備えたことを特徴とする情報検索のための情報処理方法。
【請求項２】
キャッシュされる連言をコントロールする手段と、
前記連言の共有化を促す手段と、
を備えたことを特徴とする請求項1に記載の情報検索のための情報処理方法。
【請求項３】
キャッシュされた連言に関する情報が書き込まれたブルームフィルタをピア間で交換・共有する手段と，
ある連言がキャッシュ上に存在していないことを局所的な計算のみによって確かめることができる手段と、をさらに備えたことを特徴とする請求項1乃至請求項2に記載の情報処理方法。
【請求項４】
P2P DHT上で、AND検索を効率良く実現するための、情報検索のための情報処理プログラムにおいて、
各ピアが過去に行った検索の結果をローカルなディスク上にキャッシュする手順と，
キャッシュされた情報へのインデックス情報をシステム上に別途登録する手順と，
キャッシュ情報の共有化を図る手順と、
を備えたことを特徴とする情報検索のための情報処理プログラム。
【請求項５】
キャッシュされる連言をコントロールする手順と、
前記連言の共有化を促す手順と、
を備えたことを特徴とする請求項4に記載の情報検索のための情報処理プログラム。
【請求項６】
キャッシュされた連言に関する情報が書き込まれたブルームフィルタをピア間で交換・共有する手段と，
ある連言がキャッシュ上に存在していないことを局所的な計算のみによって確かめることができる手段と、をさらに備えたことを特徴とする請求項5乃至請求項6に記載の情報処理方法。
【請求項７】
請求項1から3に記載の情報処理方法と、
請求項4から6に記載の情報処理プログラムと、
を用いて作成された情報検索のための情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索のための情報処理方法、情報処理プログラム及び情報処理システムに関する。
【背景技術】
【０００２】
P2Pシステム上でインデックスを提供するための方法として，これまでに様々な方法が提案・実現されているが、中でも分散ハッシュテーブル型P2Pシステム(P2P DHT)では，インデックスを管理するための論理空間をオーバーレイネットワークにより構築し，インデックス情報をシステムに参加する全ピアで分散管理するという手法がとられる。
【０００３】
P2P DHTの具体例としては，Chord, CAN (Content-Addressable Network), Pastry, Tapestryなどが知られている。
【０００４】
P2P DHTでは，システム上に蓄積されている各コンテンツに関するインデックス情報が，そのコンテンツに付与された識別名によって分散管理される。
【０００５】
識別名はコンテンツのファイル名等であってもよいが，通常は，そのコンテンツと関連のある複数のキーワードをそれぞれ識別名として登録し，インデックス情報のキーワードによる検索を実現する逆DHT法が用いられる．
【特許文献１】特開２００４−１６３７１８号公報
【特許文献２】特開平１０−１０３９０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
キーワード検索における重要な課題のひとつは，同一のキーワードにマッチするコンテンツ数が多くなると所望のインデックス情報を効率よく得ることである。
【０００７】
この課題は，条件付き検索を行うことで、ある程度解決することができるが，これまでに提案されているほとんどのP2P DHTは2語以上のキーワードを含む検索には対応していない。
【０００８】
本発明では，代表的な条件付き検索法であるAND検索をP2P DHT上で効率良く実現するための新しい手法の提案と評価を行う。
【課題を解決するための手段】
【０００９】
本発明では、P2P DHT 上で効率的なAND 検索を行うために，リザルトキャッシュを利用した効率的なAND 検索手法に加え，ブルームフィルタを用いた，キャッシュ情報の効率的な共有方法の提案を行う。
【００１０】
基本的には，通常のP2P DHTで行われているような単一のキーワードに関する情報のハッシュテーブル上への登録に加えて，検索結果をキャッシュしているピアに関するインデックス情報を，対応するクエリに対してハッシュ関数をかけて得られたポイントに格納するようにすることで，リザルトキャッシュをP2P DHT 上で実現することができる。
【００１１】
ただし本発明では，リザルトキャッシュを用いたAND 検索の効率を向上させるため，以下の2 点に留意して提案手法の設計を行う。
・最大連言長を制限し，メモリの利用効率を高めること
・インデックスナビゲータを導入し，AND 検索の効率化を図ること
【００１２】
リザルトキャッシュ(result cache) とは，システム上で過去に得られた検索結果をキャッシュ上に一時的に保存することで，処理に時間のかかる問合せの無駄な繰り返しを防ぐ技術である。
【００１３】
P2P 上のAND 検索処理にリザルトキャッシュを用いることの利点は以下の二点である。一つはシステムへの問合せ回数の減少である。もう一つは，クエリに対して返されるインデックス量(返送インデックス量) が，連言を重ねれば重ねるほど減少していくことである。
【００１４】
本発明では前述のリザルトキャッシュの工夫に加えて，検索の候補となる連言のうち，どのような連言がキャッシュされていないのかを，ブルームフィルタを用いて各ピアに局所的にチェックさせることを提案する。
【００１５】
要素の全体集合をU とし，集合U の任意の(有限) 部分集合をS とする。ブルームフィルタ(Bloom filter) の目的は，集合Uのある要素z が集合S に含まれているか否かを，長さm (<< |U|) のビット列で可能な限り正確に表現することである。
【００１６】
ブルームフィルタを応用することで，システムに対する無駄な問合せを削減する。
【００１７】
具体的には，キャッシュされた連言に関する情報が書き込まれたブルームフィルタをピア間で交換・共有することで，ある連言がキャッシュ上に存在していないことを，ほかのピアに対する問合せを行うことなく，局所的な計算のみによって確かめることができるようにしている。
【発明の効果】
【００１８】
データベースの効率的な検索手法のリザルトキャッシュを用い，キャッシュされる連言を共有化し，有限のキャッシュ空間を効率よく利用する。またブルームフィルタを応用し，ピア間で交換・共有することで，ある連言がキャッシュ上に存在していないことを，ほかのピアに問合せしなくても，局所的な計算のみによって確かめることが出来，システムに対する無駄な問合せを削減出来、検索することが出来る。
【発明を実施するための最良の形態】
【００１９】
リザルトキャッシュを用いたAND 検索の効率を向上させるため，以下の2 点に留意して提案手法の設計を行う。
・ 最大連言長を制限し，メモリの利用効率を高めること
・インデックスナビゲータを導入し，AND 検索の効率化を図ること
【００２０】
１．最大連言長の設定
提案手法では，システム全体のコストパフォーマンスを向上させるため，各ピアがキャッシュできる連言の長さを適切な値L以下に制限する。
以下ではこの値のことを最大連言長と呼び，記号L で表現する。
最大連言長Lを適切に設定することで，キャッシュに対するヒット率を低下させることなく，メモリの利用効率を大幅に向上させることができる。
もし与えられたクエリの長さがL以下であれば，そのクエリに対する検索結果がキャッシュされている可能性があるため，クエリ全体に対する問合せをシステムに対して直接試みる。
一方、Lよりも長いクエリについては，クエリ全体に対する検索結果がキャッシュされている可能性がまったくないため，与えられたクエリを適切な長さの連言の集合に分割し，それらの連言たちに対する検索結果をすべて得た後でそれらを統合する，という段階的な方法をとる。
したがって本手法では，キャッシュ対象をユーザから出されたクエリに限定せず，もとのクエリの一部としてあらわれる連言のそれぞれに対しても，適宜キャッシュする。
最大連言長Lが3 に設定されているとする．
もし与えられたクエリがQ1 ={a, b} であれば，その長さはL 以下なので，このクエリに対する検索結果をシステムに直接問合せ，もしキャッシュされていればそこからインデックス情報を得ることができる({a, b} が“a ∧ b” をあらわしていることに注意されたい)。
もし与えられたクエリがQ2 = {a, b, c, d} であれば，その長さがL を超えている為，例えばQ''2 = {a, b} とQ''2 = {c, d} のような複数のクエリを生成し，その結果の集合積をとることで，与えられたクエリに対する返送インデックス集合を構成することができる。
【００２１】
２．インデックスナビゲータ
上述の分割された連言を用いたAND検索を効率良く行うため，キャッシュされた連言に関するナビゲーション情報をハッシュテーブル上で提示する。
この事をインデックスナビゲータと呼び、このインデックスナビゲータを実現する。
インデックスナビゲータの目的は，与えられたクエリをどのように分割すれば，求める答えがより早く得られるかを示す指針を与えることである。
具体的には，ハッシュテーブル上に格納される各連言に関するインデックス情報を，以下のように拡張する。
ハッシュテーブル上に登録されている各連言pに対して，
１）C(p)をキャッシュしているピアに関する(通常の)インデックス情報に加え，
２）pをプレフィックスとして持つ連言の中でハッシュテーブル上に登録されている連言のリストも(拡張された)インデックス情報としてハッシュテーブル上に格納する。
以下ではそのような連言のリストをU*(p) と記す。ここでp ∈ U*(p)であることに注意されたい．
またこの拡張に伴って，クエリQを提示したピアから他ピアに対して出される検索要求の中に，現在検索を行っている(長さL 以下の) 連言p に加えて，今後検索が行われる連言q (⊇ p) も含めるよう修正を加える(すでに検索が完了している連言がr のときQ = q ∪ r であることに注意)。
提案システムでは，拡張された検索要求を連言p, q とともに受け取ったピアは，C(p) がハッシュテーブル上に保存されていればそれをキャッシュしているピアのインデックス情報を要求者に対して返し，それとともに，{q’∈ U*(p) | q ∩ q‘} を計算してq’  をキャッシュしているピアのインデックス情報も返送する。
最大連言長Ｌが３のときに、クエリQ2 = {a, b, c, d} が与えられたとする。
Q2 の長さは最大連言長3 を超えているから，Q2 そのものに対する検索結果は(たとえその検索が過去に行われていたとしても) システム上にキャッシュされない。ここではシステム上に，{a, b} と{a, b, d} に対する検索結果がキャッシュされているとする。このとき，もしユーザが連言{a, b} (⊂ Q2) に対する検索結果をシステムに対して問合せた場合，インデックスナビゲータは，C({a, b}) を保持しているピアのリストとともに，連言{a, b, d} (⊃ {a, b}) に対する検索結果がキャッシュされていることをユーザに対して知らせる．その後ユーザは，連言{a, b, d} に対する問合せを行い，C({a, b, d}) を保持しているピアの情報をキャッシュから取得することになる。
【００２２】
３．ブルームフィルタの利用
本手法では前述（最大連言長の設定・インデックスナビゲータ）の工夫に加えて，検索の候補となる連言のうち，どのような連言がキャッシュされていないのかを，ブルームフィルタを用いて各ピアに局所的にチェックさせる。
ブルームフィルタには偽陽性(false positive)があり、ブルームフィルタの偽陽性率は，n(Sの要素数), m, kなどのパラメータに依存していることが，これまでの研究からわかっている。
【００２３】
４．リザルトキャッシュへの応用
ブルームフィルタを提案手法に応用することで，ある連言がリザルトキャッシュ上に存在していないことを，ほかのピアに対する問合せを行うことなく，局所的な計算のみによって確かめることができる。
したがって，もし偽陽性率が十分低く，かつ十分高い精度をもったブルームフィルタを用いることができれば，無駄な問合せを大幅に減少させることができることになる。
以下では，前述の全体集合Uを可能な連言全体の集合とし，Sを現在キャッシュ上に存在する連言の集合とする。
また適切なk個のハッシュ関数を用いてSを記録して得られた長さmのビット列を，Bであらわすことにする。
共有メモリをもたない通常のP2P環境では，各ピアがそれぞれプライベートなブルームフィルタのコピーを所有し，各ピアが実行した連言のキャッシュ履歴は，各自のもつコピーに記録された後で，ほかのピアに対して順次伝播されていくことになる。
提案手法では，そのようなコピーの伝播に，適切に構成された根付木状のオーバーレイネットワークTを用いる。
提案手法におけるコピーの伝播は，以下のような方針で進められる。
【００２４】
コピーの伝播
1) ピアuは，ほかのピアへの情報伝達用に用いられるコピーのほかに，自分が実行した履歴のみを反映したオリジナルのコピーBuを保存する。コピーBuは，ピアuが自身のキャッシュ上に保存した連言集合が変化したときにu自身の手で更新される。特に，保存していた連言がキャッシュから除去された際には，ピアuはBuを0ベクトルに初期化し，その内容を現在のキャッシュ上の連言集合から再構成する。
【００２５】
2) ピアuは，ネットワークT上の各接続リンクごとに，そのリンクの先にあるピア集合全体で保存されている連言集合を反映したコピーを用意する。
そのようなコピーをBu,1,Bu,2, . . . , Bu,k としたとき，ネットワーク全体で保存されている連言集合は，u 自身の局所的な計算により，Bu ∨ (∨ki=1Bu,i)のように求めることができる。
【００２６】
3) コピーBuが更新されたとき，その更新情報は，ネットワークT上のすべての隣接ピアに向けて転送される．ただし更新情報の転送は情報更新後すぐに開始するのではなく，一定間隔で刻まれるクロックに同期して開始される。
【００２７】
4)コピーBu,i に対応する隣接ピアv から更新情報B* を受け取ったとき，ピアu はBu,i をB* で置き換えるとともに，v 以外の隣接ピアに向けて，その更新を反映したコピーを転送する。具体的には，コピーBu,j に対応する別の隣接ピアw に対しては，置き換えられたBu,i を用いてBu ∨ (∨h=jBu,h)を計算し，その結果を更新情報として転送する(同様の処理をv,w 以外のすべての隣接ピアに対しても行う)。
【００２８】
上述の基本アイデアにしたがってAND 検索を行うための具体的な応用手続きを示す。
以下では，
1) リザルトキャッシュを用いた連言検索処理（AND 検索処理）
2) リザルトキャッシュの更新処理，
3) ブルームフィルタの更新手続き
について順に説明していく。
なお以下の説明では，ユーザから与えられたクエリをQとし，検索処理の途中で生成される連言(Qの部分集合) をp, q などの記号を用いてあらわす。また，ブルームフィルタに関する記法は，前節の記法に準じるものとする。
【００２９】
連言検索処理（ＡＮＤ検索処理）
1. q ← Qとする。
2. 変数j をmin{L, |q|} に初期化する(L: 最大連言長)。
3. 連言q の長さj のプレフィックスをp とする。
4. ブルームフィルタを用いて，C(p) がハッシュテーブル上に保存されている可能性があるかどうかをチェックする。保存されている可能性があるときのみ，連言q とともにシステムに対して問合せる。キャッシュされていないと判断した場合はすぐ下の4a へ。
(a) C(p) が保存されていないとき: j = 1ならば検索失敗で終了。そうでなければjの値を1減らして3 へ戻る。
(b) C(p) が保存されているとき: もしC(p) のインデックスとともにシステムから返された集合~ S = {q’∈ S*(p) | q ∩ q’} の要素がp のみであれば，p に関するインデックスを獲得して保存する。そうでなければ第3 章提案手法10集合~S の中で最も長い連言を新たにp とし，p に関するインデックスをキャッシュ先から獲得して保存する。
5. q ← q ｜ p とする。もしq =  ならば，それまでに獲得した集合の積をとったものを検索結果として出力して終了。そうでなければ2 へ戻る．
【００３０】
この手続きの終了条件は，検索に失敗したとき(j = 1でC(p) が保存されていないとき) か成功したとき(q が空になったとき) の2 通りであるが，そのいずれの場合も，検索途中で獲得したインデックス集合が，クエリを提示したピア上に局所的に保存されていることに注意されたい(クエリ中の最初のキーワードに対する検索結果が空である場合を除く)。そのようなインデックス集合を獲得順にC1, C2, . . . , C_ とし，対応する連言をそれぞれq1, q2, . . . , ql とする(手続きの記述よりあきらかに，∪i=1 qi = Qである)。 
【００３１】
なお以下の説明では，獲得された連言の集合をQ = {q1, q2, . . . , qi} とおく。
【００３２】
リザルトキャッシュの更新処理
リザルトキャッシュの更新は，前述の検索手続きの終了直前に実行される。更新処理ではまず最初に，連言集合Qを次の条件を満たすように部分集合Q1,Q2, . . . ,Qxに分割する：
条件1: 各1  i  x について，|∪q∈Qiq| L であること。
条件2: 各1 i < xについて，部分集合Qi+1 に含まれる最も小さい添字をもつ連言をqj としたとき|∪q∈Qiq| + |qj | > Lであること。
【００３３】
この分割が，サイズL のビンの集合にQ に含まれるアイテムたちを貪欲に詰め込んで得られる，一種のビンパッキングになっていることに注意されたい。リザルトキャッシュの更新は，各部分集合Qi ごと独立に．次の手続きに従って行われる：
1. Qi = {qi1, qi2, . . . , qiy } とする。
2. 各1 j  y に対して~qjdef = qi1∪ ・ ・ ・ ∪ qij とする。
3. 各1  j  y に対してC(~qj ) を計算し，その結果を自ピアのリザルトキャッシュ上に局所的に保存するとともに，そのことをハッシュテーブル上に連言~qj をキーとして登録する(~q1 を登録するときのみ，~q2, . . . , ~qy がハッシュテーブル上に登録されていることを~q1 のインデックス情報として追記することに注意)。
【００３４】
ブルームフィルタの更新処理
最後に，各ピアが持つブルームフィルタの更新処理について説明する。
更新処理は，大別すると以下の2つの処理に分けることができる：
１） キャッシュ内に保持する連言集合を修正したときのブルームフィルタBuの更新。
２） リンク先のピアからブルームフィルタの更新情報が送られてきた場合の処理。
前者の処理は，ピアuが保持している連言集合に変化があった場合に直ちに実行される。
具体的には，以下の手続きが行われることになる：
1) 連言を追加したとき： Buに，追加された連言を記録する。
2) 連言を削除したとき： Buを0ベクトルに初期化し削除後の連言集合からBuを再構築する。
一方後者の更新処理は，リンク先のピアからブルームフィルタの更新情報B* が送られてきた場合に，対応するコピーBu,i を最新のものに更新するだけでよい。なお各ピアは，隣接するピアに向けてブルームフィルタの更新情報を一定間隔で送信する。その際，リンク先のピアv へは，ピアv 以外のブルームフィルタの論理和をとったものが送信される。具体的には，ピアv に対応するコピーをBjとすると，送信されるコピーはBu ∨ (∨h≠jBu,h) となる。
【産業上の利用可能性】
【００３５】
これまで本発明の一実施形態について説明したが、本発明は上述の実施形態に限定されず、その技術的思想の範囲内において種々異なる形態にて実施されてよいことは言うまでもない。