1 Peer-to-Peer 上のコンテンツに対する全文検索
1.1 研究の背景
電子掲示板やソーシャルネットワークサービスにおけるコミュニケーションやblog，wiki などの普及によって，個人が情報を発信することが増えている．現在，個人が情報を発信する場合，サーバをレンタルして電子掲示板やwiki などを設置したり，blog サービスを利用するなどの方法がある．しかし，これらの方法は容量や表現，帯域などに制限がある場合が多く，またそれらのサービスが停止した場合に情報の発信を続けることが困難になるという問題がある．
このような問題を解決するために，電子掲示板やソーシャルネットワークサービスをPeer-to-Peerネットワーク上に実現するアプローチがある．これらのシステムで情報の取得を行う場合，直接情報の発信元のピアに接続することで取得する．これによって，情報の公開のためにデータを他のホストにアップロードする必要が無く，発信する情報の内容や容量に制限がなくなる．
本研究では，このようなPeer-to-Peer ネットワーク上に構築されたコミュニティに対して全文検索を行うシステムを構築する．ここでは比較的ネットワークへの参加，離脱が頻繁に行われる大量のピアが保持している文書群に対する全文検索を想定している．
1.2 システム概要
本研究で提案するシステム概要を図1 に示す．本システムにおける全文検索は以下の2 つのフェーズによって行われる．
- 全てのピアに対する部分的な検索
- 近隣ピアに対する完全な全文検索
図1: システム概要図
1.2.1 全てのピアに対する部分的な検索
全てのピアに対する検索は，文書を持つ各ピアが全文検索用のインデックスを作成し，Peer-to-Peerネットワーク上に分散させて保持することで行う．インデックスを作成する際の文書解析はN-gram 法[2] を採用する．N-gram 法によって抽出されたトークンに関する出現位置情報や他のトークンとの連接判定情報は分散ハッシュテーブルを用いて保持するピアを決定する．分散ハッシュテーブルを用いることでトークンのハッシュ値が求まれば，そのトークンに関する情報を保持しているピアを得ることが出来る．
しかし，N-gram 法によって得られる全文検索用のインデックスはサイズが巨大になりがちで，単純な実装では対象の文書と同等のサイズのインデックスが作成されることがある．全てのインデックスをネットワーク上で共有することはネットワークのトラフィック量が非常に大きくなってしまうため，そのようなシステムの運用は非現実的である．
本システムでは全ての文書のインデックスをネットワーク上で共有せず，そのピアを代表する部分文書のみのインデックスのみを分散ハッシュテーブルによって管理する．ピアを代表する部分文書の抽出は次節で述べる近隣ピアに対する完全な全文検索の検索結果からフィードバックを得ることでより洗練させることが出来る．
1.2.2 近隣ピアに対する完全な全文検索
あるピアから直接接続しているピアに関しては2.1 節で述べた機構を利用せず，完全な全文検索を行う．より多くのピアに対して完全な全文検索を行うため，文書を持つピアに直接問い合わせを行わず，ピアの持つ文書の特徴を近隣のピアに配布し，その情報に対して検索を行う．
ピアの持つ文書の特徴はBloom フィルタ[3] を用いて抽出する．この情報は1K バイトにも満たないため，より多くのピアに対して完全な全文検索を行う事が出来る．Bloom フィルタを用いた検索では検索結果としてマッチしない情報が提示されることがあるが，マッチする情報は確実に漏れなく提示される．そのため，まずローカルキャッシュの文書の特徴に対して検索を行い，検索結果として提示されたピアに関しては直接接続し，問い合わせにマッチしたかどうかの確認を行う．
1.3 実装
分散ハッシュテーブルはChord[1] のアルゴリズムを用いて実装する．Chord はピアのハッシュ値順にリング上のトポロジーを構成するアルゴリズムで，接続経路維持のための手法がそのままコンテンツのバックアップに利用できるため，本手法を選択した．
全文検索の手法はHyper Estraier[4] で利用されているN.M-Gram 法を採用する．これはトークンの出現位置情報を持つ代わりに後続トークンのハッシュ値をM 個持つことでトークンの連接判定を行う．これによりインデックスのサイズが大幅に縮小できるため，ネットワークの通信量を減らすことが出来る．
2 今後の展望
2.1 Peer-to-Peer 電子掲示板
全文検索システムの応用としてPeer-to-Peerネットワーク上で動作する電子掲示板システムの実装を行う．電子掲示板はweb上の文書群と比較し，追加更新が頻繁に行われる．本研究で提案した全文検索システムでは近隣ピアの更新はBloomフィルタの差分を取得するだけで行えるため，通信コストを抑えたまま近隣ピアの更新に対応することが可能である．
既存の電子掲示板はネットワークの普及により，ユーザが増え，巨大化している．そのため，非常に運用におけるストレージやネットワークのコストが大きい．実際に個々のユーザが必要としている情報量は電子掲示板システムが管理しているコンテンツのうちのごくわずかである．そのため，情報の分散保持が非常に有効である．
2.2 ポータルサイト
電子掲示板システムの延長でPeer-to-Peerネットワーク上にポータルサイトを構築を将来的に考えている．これはユーザが日記やwebサイトを自由にかけたり，巡回するサイトの更新情報を集めたり，限られたユーザ間においてファイルなどの情報共有などが可能な仕組みを提供するものである．ソーシャルネットワークサービスもこのポータルサイトに含まれると考える．
これらのポータルサイトは運用側もストレージ，ネットワークのコストが大きい問題があるが，ユーザ側も情報を運用側に完全に委ねてしまう問題がある．運用側がサービスの提供を中止してしまうと，ユーザの情報がすべて失われる可能性がある．
3 成果
ここで述べたPeer-to-Peerネットワークを対象とした全文検索エンジンに関する発表を3月5日〜3月7日まで那須塩原で行われるSPA2006で「Peer-to-Peerネットワーク上に構築されたコミュニティに対する全文検索システムの提案」という題目でポスター発表を行う．来期以降はシステムの実装・評価を行い、国内・国外の学会で発表を行う．
参考文献
- I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications”, ACM SIGCOMM 2001, August 2001.
- C. E. Shannon, W. Weaver, “The mathematical theory of communication”, University of Illinois Press, 1963.
- B. H. Bloom. “Space/time trade-offs in hash coding with allowable errors”, Communications of the ACM, 1970.
- Hyper Estraier, http://hyperestraier.sourceforge.net