「Winnyの技術」とクラスタリング

「Winnyの技術」を読みました。発売前から結構話題になっていて、著者自信がWinnyでpdfを流すなんて話もありましたが個人的にはp2pの実装面にそれほど興味も無かったので買うつもりは無かったけど本屋で立ち読みして買ってしまいました。200ページくらいで具体的なコードやアルゴリズム実装解説とかは無いのでそういうのを期待しているとこの本はハズレということになるけど逆に言うとそれほど詳しくプログラムとか知らなくても読める内容かもしれません。1，2章あたりはp2p解説書としても読みやすいと思います。
買うきっかけとなったクラスタリング技術の説明が「4章 実装」編にあります。Winnyでは転送速度(光・ADSL・ISDN等)によって上流・下流ノードという概念を決定していて、各ノードは上流2,下流5ノードに接続可能です。実際にファイル検索する際にキーワードを隣接ノードに問い合わせるわけですがこのとき問い合わせる隣接ノードにファイルがあるとは限らない。無い場合は問合せ先ノードがそのノードの隣接ノードに検索クエリを投げて・・・と繰り返していってそのうち見つかります。検索クエリのホップ数は限定されているけど上流にはクエリがたまりやすい性質があるので大抵は見つかるようです。
見つかったノードは検索クエリ発行元ノードが欲しいファイルも持っている可能性が強く、このノード分類のためにクラスタリングが使われています。Winnyには自動ダウンロード機能というものがあり、キーワードを3つ指定すると勝手に関連ファイルを検索してダウンロードしてくれます。この自動ダウンロードに指定したキーワードがクラスタリングに利用されています。検索クエリを発行するノードは隣接ノードの自動ダウンロードキーワードと文字列比較し、一致文字数の多いものを所属クラスタとするわけです。このとき隣接ノードに一致するキーワードが無くてもある程度転送してくれるのでいずれ一致するノードが見つかり、そのノードが所属クラスタに登録することで次回検索から効率よく検索可能になります。
Winnyではネットワークトラフィックを減らすために導入されている「上流・下流」と「隣接ノード」「クラスタリング」という概念ですが、一般的な検索アルゴリズムやクラスタリングにも応用できそうです(既にあって知らないだけの可能性がありますが)。まったく期待してなかったけどこの概念を得られたことは収穫でした。

Winnyの技術