無印吉澤（※新エントリはhatenablogに掲載中）

■[P2P]Bloom filterの解説文

最近、アリエルエリアのホームページがリニューアルされたのをきっかけにサイト内のドキュメントをいろいろ覗いていたら、チーフアーキテクト井上氏によるBloom filterの解説文がありました。去年の11月には既に公開されていたようなので今更ですけど、参考になりそうなのでご紹介します。

Bloom filterの説明(アリエルエリア)
http://dev.ariel-networks.com/modules/xfsection/article.php?articleid=18

前半はBloom filterの分かりやすい動作イメージの話で、後半はこの技術がどのように役立つかという応用の話です。前半については原文を読んでもらうとして、後半部分を一部引用します。

Bloom filterには、以下の特性があります。

• 少ないデータを転送するだけで、存在チェックのヒントを相手に渡せる
• Bloom filterの和は、ビット和を取るだけでできる
• 秘密を保ったまま、自分の手札をさらせる
• Bloom filterを比較(同じビットが立っているか否か。つまりXOR演算)することで、近さの判定ができる

去年の9月に開催された第1回P2P勉強会での福冨氏の講演にて「TapestryというDHTアルゴリズムがBloom filterを用いて検索を最適化している」というコメントがあったのですが、1番目の特性はそれに相当するものですね（2番目の特性も多少関係するのかも）。

一方、3番目と4番目の特性はだいぶ毛色が違って、大雑把にまとめると「自分が持つ情報の具体的な内容は秘密にしたままで、その情報との類似性を判定するための材料を提供できる」という特性です。

例えば、文中で取り上げられているLOAFは、アドレス帳（メールアドレスの集合）をBloom filterにかけた結果を友達の間で共有することで、初めて送られてきたメールの送り主が「友達の友達」かどうかを判定できるというもののようです。それでFOAFに似た名前が付けられているのか、と。

僕は今まで、こういう類似性の判定は信頼できる第三者が居なければ不可能なことだと思っていたのですが、第三者に頼らずBloom filterでこういうことが出来るなら、P2Pソフトウェアの幅も広がりそうですね。