最速インターフェース研究会

9/15日にMozilla 24 出張Shibuya.js 24でしゃべってきました。
http://shibuyajs.org/articles/2007/08/24/Shibuya-js-24

資料はこちら。
http://ma.la/files/shibuya.js/mozilla24.html

JavaScriptでBloom　filterのデモ。今のところ実用性が無い。仕組みを理解するのには良いかも。
http://la.ma.la/misc/js/bloomfilter/

Bloom Filterについてはここら辺が詳しい。
http://chasen.org/~taku/blog/archives/2006/01/bloom_filter_1.html
http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AB%E3%83%BC%E3%83%A0%E3%83%95%E3%82%A3%E3%83%AB%E3%82%BF
http://dev.ariel-networks.com/modules/xfsection/article.php?articleid=18

以前書いたとおり、livedoor ReaderのFeed Discover APIの中で使っています。存在する可能性が著しく低いキーを大量に問い合わせる場合に有効だと思う。Squidで使われたりしてるみたいですね。

memcachedは存在するデータをキャッシュするのに使えるけれど、ヒットしないことを判別するためにキャッシュを作るようにしてしまうと大量のゴミクエリをキャッシュすることになってしまう。Bloom filterを使うとDBに問い合わせる前にキーが存在するかどうかをオンメモリでチェックすることができます。検索に応用したりもできるみたいで、シグネチャ法という全文検索の手法があります。CPANモジュールのText::Bloomというのがbloom filterを使った実装。古いのであんまり使えないと思うけど。

解説を読むと分かりますが、存在しないキーでもtrueを返す可能性があります。データをコンパクトにできる代わりに、正確じゃなかったりする。そういうアルゴリズムは面白いですね。