« [科学]星がない銀河があるなんて。 | トップページ | [音楽]シュトックハウゼンが来日するぞ! »

2005.04.09

[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(データ),データ}とします。
単語1、単語2を含むデータを検索したい場合、次の手順を踏みます。

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

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

■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] 単語1、単語2を含まれるデータを探したい場合、上位x bitがhash(単語1)、下位y bitがBloom_Filter_Array[単語1.単語2]となるハッシュ空間Hに含まれるハッシュ値Hash(単語1,単語2)にアクセスします。

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

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

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

|

« [科学]星がない銀河があるなんて。 | トップページ | [音楽]シュトックハウゼンが来日するぞ! »

P2P」カテゴリの記事

コメント

> > bloom filterのビット数というのは、通常数百ビット以上にする

> 確かにそうなのですが、今回データというのはファイル名など文字数が少ないもの名のを考慮してハッシュ関数を数を調整すると数10bitで十分と認識してます。

1つのコンテンツが持つ検索対象語の数は、せいぜい数個程度を想定しているんですね。
今回、文書の全文検索のようなことは考えてなくて、検索の手がかりは、コンテンツの表題、作者名、くらい、と。

> > 単語1,単語2,単語3をキーとする値を登録する際、「単語1 and ...」だけでなく、「単語2」や「単語2 and 単語3」といったqueryに対応するためには、やっぱり、全単語を(primary)キーとして値を登録しておく必要がある。

> これは、単語1が含まれるかどうか判断するには、単語1 and 単語2 and ...とすればすくなうくとも、(単語1がない)ことは判断できます。そこから絞った方が良いと思います。なにせ、含まれている文字数が少ないデータを想定していますから。

単語1をまったく含まないquery、例えば「単語2」や「単語2 and 単語3」といったqueryに応えるため、ということを書いたつもりでした。
具体的には: 単語1,単語2,単語3という3つの単語によって検索可能なコンテンツの場合、hash(単語1)なノード周辺にだけ登録したのでは、「単語2」というqueryではそのコンテンツは見つからない、と。

と言っても、ここでは、コンテンツあたりの検索対象語は数語程度、という前提を置いているので、単語1について行った登録作業を単語数分繰り返すというのも許容され得るわけですね。

投稿: しゅどう | 2005.04.14 11:26

しゅどう様:
コメントありがとうございます。

>bloom filterのビット数というのは、通常数百ビット以上にする

確かにそうなのですが、今回データというのはファイル名など文字数が少ないもの名のを考慮してハッシュ関数を数を調整すると数10bitで十分と認識してます。そもそも絞るためのもので、Filterの確率をものすごく上げる必要はないと考えています。

>「単語1」というqueryに対して値が得られないことが即座に判明しない。ハッシュ関数(単語1)というIDを持つノードから、周辺(近いIDを持つノード群)をwalkしないといけない?

それはそのとおりで、STEP2にその懸念点を書いてあります。そのためにどのようにして効率よくリクエストするかの方法を書いてあります。

>単語1,単語2,単語3をキーとする値を登録する際、「単語1 and ...」だけでなく、「単語2」や「単語2 and 単語3」といったqueryに対応するためには、やっぱり、全単語を(primary)キーとして値を登録しておく必要がある。

これは、単語1が含まれるかどうか判断するには、単語1 and 単語2 and ...とすればすくなうくとも、(単語1がない)ことは判断できます。そこから絞った方が良いと思います。なにせ、含まれている文字数が少ないデータを想定していますから。

もし、TXTファイルなどのデータを考えるのであればしゅどう様が指摘しているようにハッシュ値を大きくする等の工夫が必要です。

よろしくお願い致します。

投稿: Tomo | 2005.04.11 00:22

上記アイディアに、芽はあると思うんですが、いくつかの問題が思いつきます。
(内容を誤解してたらごめんなさい。)

・bloom filterのビット数というのは、通常数百ビット以上にする → IDの下位に押し込めるのは苦しいかも。
・「単語1」というqueryに対して値が得られないことが即座に判明しない。ハッシュ関数(単語1)というIDを持つノードから、周辺(近いIDを持つノード群)をwalkしないといけない?
・単語1,単語2,単語3をキーとする値を登録する際、「単語1 and ...」だけでなく、「単語2」や「単語2 and 単語3」といったqueryに対応するためには、やっぱり、全単語を(primary)キーとして値を登録しておく必要がある。

サーベイしないと。
と言っても、実はあんまり見つからないんですが。

投稿: しゅどう | 2005.04.10 21:12

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/3624100

この記事へのトラックバック一覧です: [DHT]DHTによるデータの部分列検索の考察:

« [科学]星がない銀河があるなんて。 | トップページ | [音楽]シュトックハウゼンが来日するぞ! »