Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

Bloom Filters

Dennis Gosnell

code borrowed from Bill Mill

ブルームフィルタとは

  • 空間効率の良い確率的データ構造。
  • 要素が集合のメンバーであるかどうかのテストに使われる。
  • 偽陽性（ぎようせい：False Positive）による誤検出の可能性があるが、 偽陰性（ぎいんせい：False Negative）はない。

・・・ん？

簡単に説明する

ビットベクター

ハッシュの関数

２つか３つが必要

例えば：md5とsha1

単純に

  • ハッシュしたい文字列をハッシュ関数に渡して
  • 結果を14にmodして
  • ビットベクターに入れる

例

Enter a string:

md5:
sha1:

Your set: []

ブルームフィルターどこで使える？

使えるところ

  • DBに通信する前に、探しているデータがあるかどうか高速にチェック

本来のPXサーバ

  • a8matが渡される
  • a8matをデコード
  • a8matの中の広告素材IDを使ってMongoにqueryを投げる
  • 該当するデータがなかったらcoredaに飛ばす

PXサーバ +
ブルームフィルター 1

  • a8matが渡される
  • a8matをデコード
  • a8matの中の広告素材IDをハッシュしてブルームフィルターでチェック

PXサーバ + ブルームフィルター 2

  • ビットが立っていなければ、該当するデータはかならずMongoにないので即座にcoredaに飛ばす
  • ビットが立っていれば、該当するデータがMongoにあるかもしれないのでMongoにqueryを投げる

要するに

  • Mongoに通信しなくても探しているデータが入っているかどうかはすぐ分かる

fin

Use a spacebar or arrow keys to navigate