Bloom Filter をせこく使って、せこく処理時間を省く

先日、Bloom Filter を利用して重複部分をフィルタすることで処理を簡潔にする、という記事を書きました。実際、3, 4秒の改善が図れたということも書きました。でも、普通の設計方法では、std::setより遅くなります。ご注意ください。

原因は、２つあります。ハッシュ値の計算 (std::string → size_t) が遅い。ハッシュ関数の個数が多い。std::set は、平衡二分木で実装されています。dblp.xml 内の著者数は、だいたい72万なので木の高さは19くらいになります。一方で、Bloom filter では、false positive probability を1%にするとハッシュ関数の個数は7、0.1%にすると10程度になります。std::setでの「最大19回の分岐処理」と Bloom filter での「いつも10回ハッシュ値計算」だと、totalでみて前者の方が軽いようです。これは、O-notation の abuse の一例です。規模が小さいので、log n と隠れている定数の大小関係が逆転しています。

実際のハッシュ値の計算は、ここで記述されているような Rotavie Hashing によります。アルゴリズムを見て頂ければ、木の分岐判定より計算コストがかかるであろうことがお分かりになると思います。ハッシュ関数自体を換えるのも手だとは思うのですが、できるだけハッシュ関数の個数を減らす方向で考えた方が簡単です。

今日は、どのようにBloom Filterを設計したか、についての覚書を残しておきたいと思います。それから、「あんた... せこいよ...」という評価も享受できればと思っています。よろしくお願いします。

Open Bloom Filter の使用例

まずは、Open Bloom Filter (OBF) の API を見ておきます。bloom_filter のコンストラクタは、集合のサイズの上限値、偽陽性判定確率、乱数シードの３つの引数を必要とします。下記の例は、要素数 $10^6$ 以下で偽陽性判定確率を1%以下に設定している例です。

size_t predicted_element_count = 1 * 1000 * 1000;
double false_positive_probability = 1.0 * 0.01;
size_t random_seed = 0;
bloom_filter bf(predicted_element_count,
      false_positive_probability, random_seed);

それから、メンバシップクエリとメンバ登録の様子は、例えば次のようになります。

typedef struct {
  bloom_filter* bf;
  std::string name;
  std::vector<std::string> cs_list;
} cs_author;

void cs_insert(cs_author* p)
{
  if (!p->bf->contains(p->name)) {
    p->cs_list.push_back(p->name);
    p->bf->insert(p->name);
  }
}

Bloom filterの基本的な設計

ここでは、OBF bloom_filter のコンストラで何をやっているのか、について簡単に確認しておきます。ちょっと説明を省いていたり、分かりにくい箇所があるかもしれません。Bloom filter の基本的なアイディアや、なぜ広く利用されているのか、などは wikipedia:jp:ブルームフィルタやいろいろな文献にあたってみて下さい。ちなみに、私はこの書籍を読んで理解を深めたんじゃなかったかと思います。

Bloom filterは、以下の記号を用いて解析されます。

- - $m$ : ビット列のサイズ
  - $k$ : ハッシュ関数の個数
  - $p$ : false positive probability (fpp)
  - $n$ : 集合のサイズの上限値

このとき、fpp は次のように表せます。

- - $p = \left(1 - e^{-k\frac{n}{m}}\right)^k \cdots (1).$

上記の通り、OBFでは、集合のサイズの上限値 $n$ と fpp $p$ を指定して初期化します。残りの記号 $k$ と $m$ の値は、式 (1) をもとに、次のように算出されます。

- - $k = \frac{m}{n} (\ln 2) \cdots (2).$

式(２)は、式(1)において $n$ と $m$ を定数と見たときに、 $p$ を最小にする $k$ を求めることで得られます。「久しぶりに、微分がしてぇ!!」という方は、確認してみて下さい。式(2)を式(1)に代入することで、ビット列のサイズ $m$ が求められます。

- - $m = \frac{\log_{\frac{1}{2}} p}{\ln 2} n \cdots (3).$

式(3)を式(2)に代入することで、ビット列のサイズ $m$ を排除した形でのハッシュ関数の個数 $k$ が求められます。

- - $k = \log_{\frac{1}{2}} p \cdots (4).$

式(4)から、ハッシュ関数の個数は、集合のサイズによらず、fpp $p$ のみによって決まることが分かります。

Bloom filter のフィルタサイズと偽陽性判定確率

以下では、ハッシュ関数は一様分布に従うことを仮定します。

上記のパラメータの下で設計された Bloom filter を用いると、集合のサイズの上限値 $n$ 個の要素が登録されても、fpp は $p$ 以下であることが確率的に保証されます。ある時点で登録されているメンバ数が $n$ よりも小さければ、その時点でのfpp は設定値より低くなることは容易に想像されるのではないでしょうか？

Bloom filter の fpp は、ビット列内の１の個数に依存します。 $n$ 個の要素を登録した時点でのビット列内にある１の個数の割合（占有率） $r$ は、次のように表せます。

- - $r \le \frac{kn}{m} = \frac{kn}{(kn/\ln 2)} = \ln 2.$

ここの式展開は、 $m = \frac{kn}{\ln 2}$ を使っています。 $\ln 2 \simeq 0.69$ なので、占有率が約70%以下であれば、fpp は設定値 p 以下であることが保証されます。70%って結構な割合だと思いますが、それでもfppが低く抑えられているのは、ハッシュ関数の個数が十分多く用意してあるからです。k個のハッシュ関数のうち少なくとも一つは、30%の0の位置を指すことが高く保証されているということを言っています。

せこい Bloom Filter の設計

「Bloom filter の fpp を低く保ちつつ、より効率的にクエリに応答したい。その目的のためであれば多くのメモリを費やすこともいとわない。」という気持ちでお話を続けます。このように考える理由は、２つあります。上記の計算式で得られた値の下でのOBFは、std::set よりも約1秒くらい遅くなった。std::setを利用した場合、OBFを利用した場合のメモリの使用量と比べて約20MB多く使用していた。

実際に期待するfpp の値 $p_1$ とOBFに与えるfpp $p_2$ の値を分けて考えます。また、実際の集合のサイズ $n_1$ とOBFに与える集合のサイズの上限値 $n_2$ も同様に考えます。

- - $p_1 < p_2$ とすることで、ハッシュ関数の個数が減らせます。
  - $n_1 < n_2$ とすることで、実際に期待するfpp $p_1$ の値に近づけることができます。

ユーザが指定するパラメータは、ハッシュ関数の個数 $k$ と実際に期待するfpp $p_1$ です。また、 $n_1$ の値もできるだけ正確に見積もれていると幸せです。今回は72万ということで $n_1$ の値は分かっています。これを使います。せこいですね。さらに、 $n_2$ は、20MB分だけ増やすことができることとします。これもせこいですね。こういうことから、 $k = 5$ で $p_1 = 0.001$ を考えます。fpp を0.1%にすると偽陽性判定は発生しなかったので、この値を使います。せこいですね。

上記の背景から、OBFへ渡す引数の値を求めます。式(3)より $p_2 = \left(\frac{1}{2}\right)^k$ で容易に求められます。

こっからちょっと適当になります。 $n_2$ の算出ですが、まず $n_2$ を設定したときのビット列のサイズ $m$ と占有率 $r$ の確認をします。ビット列のサイズは $m = \frac{k}{\ln 2} n_2$ (式(3)と式(4)より)、そして占有率は $r \le \frac{kn_1}{kn_2 / \ln 2} = \frac{n_1}{n_2} \ln 2$ となります。このとき、 $p_1 = \frac{n_1}{n_2} \ln 2$ となるように $n_2$ を設定することで、 $n_2 = \frac{n_1}{p_1} \ln 2$ を得ます。

これらの値を指定して、OBFを利用するとstd::setを利用する場合と同程度のメモリ使用量で、約3〜4秒近くの効率化が図れました。どうでしょうか、長々と書き連ねた割に、せこい改善だと思いませんか？「std::setと比べんな」的な感想もおありのことと思います。時間ができたら、他のコンテナとの比較をしてみようと思います。私の中では既に、OBF の敗色がほんのりと灯っていますが...