[DHT]DHTによるデータの部分列検索の考察

DHTは部分列検索が容易ではないのだが、これについてどのように実現するのか考察してみよう。これが実現すればあいまい検索やフレーズ検索にも繋がっていくかもしれない。

つまり、「バッハ　バイオリン協奏曲第2番」というデータについて「バッハ」、「バイオリン」としても検索できるようにしたいということだ。

まず基本技術としては、データを各要素に分解することから始まる。つまり、「バッハ」「バイオリン」「協奏曲」「第2番」と分解する。この技術は形態素解析という技術を使えば実現可能だ。
詳しくはここを参照して下さい。
日本語形態素解析入門

この各単語の要素のハッシュを取って、{hash(単語）、データ}というペアをNode_ID=hash(単語）に登録すれば良いわけだ。

逆に、例えばある単語が含まれるデータ（例えばファイル名）を検索するならNode_ID=hash(単語）に格納しているデータからサーチすれば良い。

ところが、この技術だと少し困った事がある。それは主に2点だ。

[1]特定ノードNode_ID=hash(単語）にたどり着いてからさらに絞り込むのに時間がかかる
[2]ある特定の単語のハッシュ値を管理するノードにデータが集中しすぎる

これについて考察してみましょう。

まず[1]については、ある程度簡単に克服できる。それはBloom Filterという技術を使う事だ。
Bloom Filterはハッシュ値を使って、データがある単語を含んでいる「かもしれない」ことを高速に判別する技術だ。詳細は
[P2P]Bloom filterの解説文～無印吉澤
を見てほしい。

Bloom Filterにおいて、あるデータの要素が格納しているかどうか判別するハッシュ列をBloom_Filter_Array()としよう。
今、あるノードNode_ID=hash(単語）に格納するデータを
{hash(単語）、Bloom_Filter_Array(データ）,データ}とします。
単語１、単語2を含むデータを検索したい場合、次の手順を踏みます。

[手順１] Node_ID=hash(単語１）にアクセスする。
[手順２] 単語１、単語2がデータに存在するか確認するため、　Bloom_Filter_Array[単語１,単語2]を計算する
[手順３] Bloom_Filter_Array(データ）AND Bloom_Filter_Array[単語1,単語2]=0ならデータに単語１、単語２は含まれてないが、0以外なら含まれている「かもしれない」。

ただし、Bloom_Filter_Array[単語１、単語２]はBloom_Filter_Array（単語1) XOR Bloom_Filter_Array(単語２）を表わします。
これで高速に単語の絞込みをすることができました。

■STEP2
これではまだ、[2]が改善されていません。そこで次のような事を考えます。

ハッシュ空間H(z bit=x bit + y bit)を次のように構成します。
　・上位x bit は　hash（単語）
　・下位y bit は　Bloom_Filter_Array(データ）

今、あるデータに対してHに含まれるハッシュ値を返す関数をHash(単語、データ）とします。
まず有るデータをDHTに登録するには形態素解析をして、データに含まれる単語についてNode_ID=Hash(単語、データ）に対して{Hash(単語、データ）、データ｝を登録します。これで準備ができました。

[手順1]　単語１、単語２を含まれるデータを探したい場合、上位x bitがhash(単語１）、下位y bitがBloom_Filter_Array[単語1.単語2]となるハッシュ空間Hに含まれるハッシュ値Hash(単語1,単語2）にアクセスします。

[手順2]ChordなどのDHTは隣接ノードとリンクをしています。そこで、Node_ID=Hash(単語１、単語２）となるノードから上位x bitがhash(単語１)＋1,下位 y bitが0となるNode_IDのノードまでデータBloom_Filter_Array[単語１、単語２]をバケツリレーで渡します。ただし、Node_IDが管理するハッシュ空間がBloom_Filter_Array[単語１、単語２]とANDを取った時に0ならすぐにデータをBloom_Filter_Array[単語１、単語２]を次の隣接ノードに渡して手順3に行く必要はありません。あるいは更に高速化するには、自分のNode_IDよりも大きくてBloom_Filter_Array[単語１、単語２]が０でない一番小さいハッシュ空間Hを管理するノードにBloom_Filter_Array[単語１、単語２]を投げるとすればもっと良いですね。トラフィックが増えてしまいますが、上記の範囲で自分とリンクしているノード全てのデータを渡してしまうのも手です。（あるノードに対して同じデータが2回以上来たら、そのデータを無視して終了とする）
（※リクエストスピードを２倍にするなら、hash(単語１)＋1,下位 y bitが0からHashが小さくなる方向にも要求をかけるのもアリです。）

[手順3]ノードが保持しているデータについて単語２があるかどうか計算します。

DHTによる部分列検索について考察しました。STEP２については一部バケツリレーを使っているので、もう少し検討すると処理スピードが高速になるかもしれませんね。なお、今回は検索した単語は２つですが、3つ以上でも同じような方法で実施できます。