ブロックチェーン ビットコインとブルームフィルター：軽量化で広がる可能性
- 革新的なデータ構造皆さんは、「ブルームフィルター」というデータ構造をご存知でしょうか？これは、ある要素が膨大なデータの集合に含まれているかどうかを、驚くほどの速さで、しかも少ないメモリ消費量で判定できる、画期的な技術です。この技術のポイントは、「確率的」という部分にあります。これはどういうことかというと、もしブルームフィルターを使って「このデータは集合に含まれていません」という結果が出た場合は、それは確実に正しいと言えます。しかし逆に、「このデータは集合に含まれています」という結果が出た場合でも、実際には含まれていない可能性もあるのです。例えるなら、蔵書数百万冊という巨大な図書館を想像してみてください。もしあなたが探している本が、その図書館の蔵書検索システムで見つからなかったとします。その場合、その本はほぼ確実に図書館に所蔵されていないでしょう。しかし逆に、システム上は存在すると表示されても、実際に書庫を探しに行ってみたら、棚から誰かに借り出された後だった、なんてこともあるかもしれませんよね？ブルームフィルターは、まさにそんなイメージの技術なのです。このように、100%の正確さが必要な場面には向きませんが、多少の間違いが許容されるような状況であれば、ブルームフィルターは非常に強力なツールとなります。例えば、膨大なウェブサイトの中から、特定のキーワードを含むページを高速に検索したり、キャッシュメモリに、どのデータが保存されているかを効率的に管理するといった用途に利用されています。
