よりコンパクトな Bloom filter 的なものを探して

Approximate membership query (AMQ) が実現できるデータ構造としてそれなりに広く使われていそうな Bloom filter ですが、機能性を高めたバリエーションはそこそこ存在する一方で、空間効率を追求した・コンパクトなバリエーションはあんまり見つからないものです。

ここ最近、ふとデータ構造熱が高まってきたこともあったので、オリジナルの Bloom filter よりもコンパクトに表現できる代替データ構造を探してメモしてみました。

Compressed bloom filters

空間効率を追求するといっても、転送・永続化している状態での空間効率なのか、それともルックアップ可能な状態においての空間効率なのかで全然違うわけですが、この Compressed Bloom Filters は前者の転送時・永続化時の空間効率を選択したバリエーションです。

端的に言えば、Bloom filter のビット列における 0 と 1 の出現確率はランダム (1/2 = 0.5) というわけではなく偏りが生じることがあるため、算術符号で符号化すればよりコンパクトになるじゃん、というものです。 ただ、この圧縮はあくまでも転送・永続化時のことしか考えていないようで、Bloom filter が素早くルックアップできる状態にあるためには結局復号した状態で保持する以外に他ないようです。

Golomb-Compressed Sequence (or Golomb-code sets)

Cache-, Hash- and Space-Efficient Bloom Filters という論文で、Space-Efficient な手法として提案されている approximate membership query を提供するデータ構造です (Bloom filter と同じ機能を提供しているが、厳密には Bloom fitler ではない)。

要素のハッシュ値を算出するところまでは Bloom filter と同じですが、そのハッシュ値を

1. 昇順ソートして
2. そのソート順における、左に隣接する値との gap を求めて
3. その gap を Golomb 符号で符号化

することで、Bloom filter よりもコンパクトな表現を実現しています (ハッシュ値は一様分布しているものとして、そのハッシュ値の gap をとると幾何分布になり、幾何分布に従う数値を符号化するには Golomb 符号が都合いい、ということ)。

この方式でのルックアップ操作は、あるハッシュ値が Golomb-Compressed Sequence に含まれるか否かだけを探索により判定すればいいので、Bloom filter のようなビット列への複数回のランダムアクセスは生じません。 とは言えど、この圧縮表現のままでは効率的なランダムアクセスが実現できないため、

1. ハッシュ空間を大きさ $I$ の空間に分割して
2. その分割された空間ごとに Golomb 符号化をし
3. ルックアップの際はハッシュ値から探索先のハッシュ空間を絞り込んでから逐次 Golomnb 符号を復号する

ことで、復号にかかる時間効率を高められるようにしています。 $I$ を大きくすれば大きくするほど、空間効率がよくなるが探索効率は悪くなり、 $I$ を小さくすると空間効率は悪くなるが探索効率が上がる、というトレードオフの関係になっています。

Cuckoo filter

Cuckoo Filter: Practically Better Than Bloom では、Cuckoo hashing を利用して、approximate membership query を提供するデータ構造を提案しています。

Cuckoo hashing の詳細説明は kumagi 先生の資料 に譲るとして、Cuckoo filter では要素から $f$ ビットのフィンガープリント (ハッシュ値の一つだと考えれば OK) と、2 つのハッシュ値を算出し、 Cuckoo hashing に利用します。より具体的には、2 つのハッシュ値を配列で表現されるバケット (複数のフィンガープリントを記録できる入れ物) のインデックス決定に利用し、フィンガープリントをそのバケットに追記する、という使い方になります。

この Cuckoo filter で使われる 2 つのハッシュ関数はちょっとだけ特殊で、$h_1(x) = hash(x), h_2(x) = h_1(x) \oplus hash(x's fingerprint)$ となっています。つまりは、フィンガープリントと一方のハッシュ値がわかっていれば $h_1(x)$ と $h_2(x)$ を算出することができるわけです。

パラメータとしてはフィンガープリントを表現するビット数や、バケットの大きさ (異なるフィンガープリントを格納できる個数)、バケット数と、ちょっと多めなのが気になりますが空間効率も参照性能も Bloom filter より良さそうです。

さて今回はこのぐらいにして、Golomb-Cmpressed Sequence あたりを実装してみようかな…