« 「分散ハッシュのP2Pアプリへの応用その1」アップしました! | トップページ | [P2P]オーバーレイネットワークでのマルチキャスト(案) »

2004.05.03

[P2P]分散ハッシュとあいまい検索(DHT)

旅行から帰ってきてまだ調子が悪いです。。。今日も家でゆっくりしたいと思います。
久しぶりに朝からBLOG書いているので、どうもまだ頭が回らない。。

さて、分散ハッシュにおいてハッシュ関数はSHA-1などを使う。ハッシュ関数の場合、a~b(~はほぼ似ている文字としよう)だとしても hash(a) not ~ hash(b) であるから、あいまい検索などにはこのままでは使用しにくい。

例えば 「桜」というコンテンツと「桜坂」というコンテンツがあっても両者をハッシュ関数に掛けると関連性がほとんどなくなるのだ。これが分散ハッシュにおいてあいまい検索がしにくい理由である。

あいまい検索を可能とさせる一つの解はコンテンツについてキーワードを何個か設定し、それをハッシュ化して分散ハッシュネットワークに格納することである。しかしこれはユーザに大きな負担を強いる。有力な方法として、nameに関する語を自動的に区切って(例えば「桜坂」なら「桜」と「坂」)これらをハッシュ化してノードに登録する事も考えられる。

ここではローテクで解決する方法を考えてみよう。
ノードXが持っているコンテンツ名nameについてはご存知のとおり、Node_ID=hash(name){これをノードAとする}にnameとIPAdress_X格納する。すなわち、ノードAはコンテンツ名nameについて知る事ができる。さて、掲示板だとトップページがあって、そこにスレッドの一覧がある。そこで、分散ハッシュネットワークに対してそのようなメタデータを格納するノードを複数設け、そこにnameデータの一覧を格納しておく。このようなノード群をノード群Pとしよう。(ノード群Pは各ノードと違ってnameに関する最小限のデータしか保持しないとする。)

各ノードはノード群Pと通信して、ノードの生死についての情報を送っておく。ノードが死んでいる場合にはそのノードに関する情報をノード群Pから削除する。ノード群Pは素のnameを格納しているからあいまい検索が可能である。(データ格納について0<Node_ID<10000についてはノードP1に格納、10000<Node_ID<20000についてはノードP2に格納ということも考えられそうだ。。あまり効率は上がらないが。)

このようにすれば確かにあいまい検索が可能だが、これだとノード群Pに負荷がかかるし、何よりも分散ハッシュのメリットがあまり活かされてない。残念ながら上の手段はあまりエレガントな方法ではないが、実装は簡単そうだ。

nameを適宜区切ってハッシュ化し登録する方法(方法1)と上記の方法(方法2)はどちらが良いのだろうか?方法1は、あいまい検索のキーワード分だけノードにアクセスする必要がある。またノードに対する負担は平等である。方法2は最低で一つのノードで検索可能だが、ノードに対する負担は不平等でノード群Pに大きな負荷がかかる。ただし、方法2では素のnameを保持しているので例えば「桜坂」を探す場合、「花」とか「道」などのnameに含まれている語彙以外のキーワードでもヒットできる可能性を秘めている。つまり意味の近いキーワードでヒットできるかも。(あくまでも可能性を述べただけで実装は大変。こうなるともうSIONetの概念に近くなるなぁ。)基本的には方法1の方がスマートだがもう少し考えてみたいと思う。

|

« 「分散ハッシュのP2Pアプリへの応用その1」アップしました! | トップページ | [P2P]オーバーレイネットワークでのマルチキャスト(案) »

P2P」カテゴリの記事

コメント

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: [P2P]分散ハッシュとあいまい検索(DHT):

« 「分散ハッシュのP2Pアプリへの応用その1」アップしました! | トップページ | [P2P]オーバーレイネットワークでのマルチキャスト(案) »