« [Mixi]IDを利用したマーケティング戦略の提案 | トップページ | [P2P][DHT]ゼロ知識証明によるP2P認証方法の提案 »

2006.10.29

[P2P]SkipGraphを利用した部分一致検索の提案

□はじめに
最近Structured P2Pの一種であるSkipGraphが注目されている。SkipGraphの特徴の一つとして、ある範囲のNodeIDを保有するノードに対して一斉に各種クエリーを届ける事が出来る事が挙げられる。

SkipGraphのわかりやすい解説は後日として、今回はこのSkipGraphの特徴を利用した部分一致検索を提案する。

□定義
今ハッシュ空間をXとし、ハッシュ空間のノルム(大きさ)を|X|としよう。Xを出力するハッシュ関数をHash()とする。
Xにおいて、prefix1()、prefix2(),prefix3(),prefix4()を定義する。これはp=|X|/4の桁に対して、
prefix1(A)=Aの上位p桁を抽出する関数
prefix2(A)=Aの上位p+1~2p桁を抽出する関数
prefixn(A)=Aの上位(n-1)p+1~np桁を抽出する関数

とする。なお、|prefixn(A)|=|X|/4であることに注意。いま、prefixn(A)が覆う空間をX(n)として、そのハッシュ関数をhash(X(n))とする。
また、A=sum(prefix1(A),prefix2(A),prefix3(A),prefix4(A))となるsum関数を定義する。

□部分一致検索の方法

☆Skipgraphへの情報P登録

ある情報PをSkipgrapghに登録するために、まず、Pを形態素解析で単語pに分解し、更にハッシュ関数hash(p))を掛ける。

今、Pに含まれる単語が4つしかないとすると、p={p1,p2,p3,p4}となる。
ここで、p(n)=hash(pn)とする、更にp(n)の大きさ順にpをソートする。例えばp1>p2>p3>p4としよう。
次にRの計算をする。
R1=sum(p(1),p(2),p(3),p(4))
R2=sum(p(2),p(1),p(3),p(4))
R3=sum(p(3),p(1),p(2),p(4))
R4=sum(p(4),p(1),p(2),p(3))

Rnにおいて、sum(pn,pnを含まない残りの元でp(n)の大きい順にソート)となる。
Pについては、NodeID=Rnとなるノードに格納することになる。

☆情報Pの検索

今、Pを構成する単語Sがあった場合、Pは見つけられるのだろうか?答えはYesである。
まず、s=hash(S)とする。
この際、Skipgraphを使ってsum(s+1,0,0,0)>NodeID≧sum(s,0,0,0)となるノードに検索クエリをPush型でマルチキャストすれば良い。

では、単語S,TのAND検索はどうすればよいか?
この時には
[手順1]s=hash(S)、t=hash(T)を計算する。
[手順2]t>sの場合、Skipnetを使ってsum(s+1,0,0,0)>NodeID≧sum(s,t,0,0)となるノードに検索クエリをPush型でマルチキャストすれば良い。

更に複数単語のAND検索も同様である。

prefixnにおいてn=4としたが、nを大きくすると検索計算量と情報登録するための処理数が大きくなる。nをどの程度にするかはAND検索の頻度や単語数を考慮する必要があるだろう。

□終わりに
部分一致検索をSkipgraphを利用して解決した。Skipgraphの特徴であるPush型マルチキャストを利用してたP2Pシステムは今後増えるだろう。

|

« [Mixi]IDを利用したマーケティング戦略の提案 | トップページ | [P2P][DHT]ゼロ知識証明によるP2P認証方法の提案 »

P2P」カテゴリの記事

コメント

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

トラックバック


この記事へのトラックバック一覧です: [P2P]SkipGraphを利用した部分一致検索の提案:

« [Mixi]IDを利用したマーケティング戦略の提案 | トップページ | [P2P][DHT]ゼロ知識証明によるP2P認証方法の提案 »