Master Thesis Abstract (in Japanese)
修士論文要旨

複数キーワード検索に対応した分散ハッシュ型P2Pネットワーク

佐藤 一帆
2007年2月

P2Pネットワークは,参加するコンピュータ (ノード) がオーバーレイネットワーク上で協調動作し,コンテンツ配信,コンテンツ共有,ネットワーク中の資源の発見などのサービスを実現するものである.クライアント・サーバシステムにおけるサーバのように,ネットワーク全体を集中的に管理する機構が存在しないため,ネットワーク帯域・ストレージ容量・計算処理などの負荷分散を実現でき,また耐障害性が高いという特徴を持っている.

P2Pネットワークは,コンテンツの所在の検索方法によっていくつかの方式に分けられるが,近年では分散ハッシュ (Distributed Hash Table,DHT) 型P2Pネットワークが盛んに研究されている.DHT型P2Pネットワークは,ハッシュ関数によって各ノード・コンテンツにIDを割り当て,IDを元にネットワークの構造化とコンテンツの管理・検索を行う方式である.この方式の利点は,ネットワークの規模に関わらず,目的のIDを持つコンテンツを高速に検索できることである.一方で,この方式はキーワード検索には不向きである.これはコンテンツのIDが一つの規則によって定められ,キーワードを反映することが困難であることが原因である.

DHT型P2Pネットワークにおいてキーワード検索を可能にするために,従来の研究ではコンテンツIDにキーワードを反映させる手法を用いている.しかし,キーワードによってはコンテンツの所在に偏りが起こる可能性がある.このため,本研究ではDHT型P2Pネットワークの従来の方法により,コンテンツの所在をキーワードに関係なく決定した上で,コンテンツのキーワード表す構造をIDとは別に管理することとした.

提案手法では,DHT型P2Pネットワークの代表的なプロトコルの一つであるChordを基礎とし,通常のChordプロトコルによってネットワークの構造化と,コンテンツ配置を行う.また,キーワード検索に対応するため,各ノードが管理するコンテンツのキーワードをBloom Filterを用いて表現する.Bloom Filterは,ハッシュ関数を用いて,与えられた要素 (キーワード) をある限られたビット幅に要約するものであり,複数個の要素が存在しても,それらのBloom Filterの論理和で得られる.この性質を利用し,提案手法では各ノードが管理するコンテンツのキーワード群を表すBloom Filterと,Chordにおける探索空間に含まれるコンテンツのキーワードとを表すBloom Filterとをそれぞれ管理する.そして,各ノードは与えられた検索キーワードとBloom Filterとを比較しながら,合致するBloom Filterを持つノードに検索を転送することで,検索を行う.

提案手法の検証のため,シミュレータによって動作を確認した.その結果,提案手法により,複数の検索キーワードを指定した検索メッセージが,キーワードに合致するコンテンツを保持するノードに到達し,キーワード検索を効率的に実現できることを確認した.


論文題目一覧