« VoIP Conference 2008 開催概要&参加者募集のお知らせ | トップページ | P2P教科書感想文キャンペーンについて »

2007.12.22

[P2P]DHTにおける部分一致検索の間接参照による解決法の提案

2007年ももう少しで終わりですね。今年は娘の誕生、P2P教科書の出版、総務省支援のP2P実証実験への技術検討メンバ参加など、プライベート・仕事ともに節目の年でした。

来年もP2Pに関する講演等が決まりつつあるので後ほど紹介致します。

さて、2月末にとある団体が主催によるP2P研究会にて講演を行う予定です。その中でDynamoなどのP2Pデータベースの話も触れたいので、少しずつネタをBlogに書いておこうと思います。仕事でP2Pに関する業務が正式に認められましたが、アイデアベースで出せるものは今後もBlogで公開したいと思いますので皆様のコメントを是非お寄せ下さい。

□部分一致検索とDHTの親和性
DHTはご存知の通りハッシュ関数を使います。通常使うハッシュ関数は暗号的ハッシュ関数といわれるもので、これはハッシュ関数H()においてH[A]=Bというときに、BからAを推定できない性質があります。もう少し噛み砕いて言うと、Aにちょっとだけデータが変化したA'とすると、H[A']=B'という値が出力しますが、BとB'は全然違う値になります。

つまり、暗号的ハッシュ関数を使うと完全一致検索は容易ですが、部分一致検索は非常に難しいという事になります。

□部分一致検索への模索
ではどのようにすれば部分一致検索が可能なのでしょうか?
私のBlogでも何回か提案しました。スマートな方法の一つが形態素解析を使う事です。形態素解析を使う事で、文章から単語を抽出して単語ベースでの検索可能とします。

[DHT]DHTによるデータの部分列検索の考察
SkipGraphを利用した部分一致検索の提案

この方法の欠点は形態素解析用の辞書を持つ必要があることです。このため、新しいキーワードに対して検索するのは難しい事が予測されます。(ただし形態素解析自体の技術が向上しているので、この課題は解決できるかもしれません。)

他のアイデアとしては暗号化ハッシュ関数ではないハッシュ関数を使う事です。それは例えばハッシュ関数に線形性を持たせる事です。このようにすることで、あるキーワードKに対して、H(K)=Dとすれば、Dに近いハッシュ値に関連付けられた情報を引っ張る事でキーワードをある程度検索できるかもしれません。ただし、この方法ではキーワード数とハッシュ空間の大きさを慎重に吟味する必要があるでしょう。私は単純なハッシュ関数ではなく、Bloom Filterを使って解決を模索したことあります。先ほど紹介した[DHT]DHTによるデータの部分列検索の考察もBloom Filterを使っています。

どちらの方法にしてもオーバーレイマルチキャストを使う事で、効率的な検索ができることが期待されます。

さて、いずれ方法にしても複数のKeyに対するValueにはデータをそのものを格納していました。ということはかなりの数のノードにデータのレプリカをする必要があり、ノードのストレージに対して相当の負担がかかります。

□DHTにおける間接参照の導入

そこで、DHTにおける間接参照を導入します。
先ほど書いたように今まではKeyとして検索するキーワード、Valueとして検索対象のデータそのものが入っていました。そこで、新たな方法としてValueに格納するものを検索対象データへのポインタとします。

このとき、Get(Key=P2P)とすれば、Valueとして、P2Pという文字列を含むデータへのポインターのリスト(具体的にはデータのハッシュ値)帰ってきます。そこで、実際のデータにアクセスしたければ再度DHTを使ってデータを取得すれば良いのです。

この方法でもAND検索やOR検索も容易です。なぜなら
Get(Key=P2P AND KEY=DHT)=GET(Key=P2P) AND GET(Key=DHT)
Get(Key=P2P  OR KEY=DHT)=GET(Key=P2P) OR GET(Key=DHT)
だからです。

ノードにはポインターの情報が色々とばら撒かれますが、そもそもデータそのものではないので、今までの方法よりもノードに対する(ストレージ的な)負荷は下がると予想されます。そのかわり、実際のデータにたどり着くまでの時間や信号数は増えます。

□通常の検索システムへの置き換えへ

ポインターを導入する事で、ノードへのストレージ負荷を大幅に下げる事に成功しました。となると検索としてわざわざ形態素解析を導入しなくても、通常の検索システムで使うNグラム法でOK!ということになります。これなら通常の検索システムのソースを使ってDHTに簡単に移植できるかもしれません。

全文検索-Wikipedia

□来年に向けて
今考えているのはDynamoのようなP2Pな分散データベースで、どのような適用範囲なら使えるか、あるいはどのような実装なら容易に実現できるかということを考えています。データベースはあまり詳しくないのですが、そのうち講演等でディスカッションさせて頂ければと思います。

今後の予定ですが、
・1月18日:吉田鎌ケ迫へのオフィスツアー
・2月末:P2P研究会で講演(P2Pのアーキテクチャと最新動向について)
・3月上旬:信学会の研究会で招待講演(P2Pのアーキテクチャとユビキタスとの関連)
・3月中旬:信学会の全国大会で講演(NAT越え)

となっています。業務でP2Pの研究会開発が正式に認められたので今まで以上に活動できそうです。また私への講演や技術打ち合わせを御検討されている方はお気軽にメールかMixi経由でご連絡下さい。




|

« VoIP Conference 2008 開催概要&参加者募集のお知らせ | トップページ | P2P教科書感想文キャンペーンについて »

P2P」カテゴリの記事

コメント

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: [P2P]DHTにおける部分一致検索の間接参照による解決法の提案:

« VoIP Conference 2008 開催概要&参加者募集のお知らせ | トップページ | P2P教科書感想文キャンペーンについて »