一般論文

DBSJ Journal, Vol.9, No.2
November 2010

素集合判定に適した Bloom フィル
タの拡張

1.

はじめに

Bloom フィルタ [1] は，ある要素が集合に含まれるかどうかを評価するために提案された，空間効率に優れたビット配列のAn Extension of Bloom Filters for Disjoint Sets Test

データ構造である． Bloom フィルタは様々な分野で利用されている．データベース分野でも問合せ処理，特に結合演算の効率化のために利用されている．Bloomjoin[3] や [4] は分散環境におけ

的野 晃整 ♥
谷村 勇輔 ♠

る通信コストを減らすために実際の結合を行う前に， 不要なタ

スティーブン リンデン ♦小島 功 ♣

Akiyoshi MATONO
Yusuke TANIMURA

プルを削除する Semi-join フェーズで Bloom フィルタを利用している． また Oracle DB 11g[5] でも partition pruning の性能向上のために， 結果を持たない不要な partition を削除する，

Steven LYNDEN
Isao KOJIMA

Bloom フィルタを用いる join-ﬁlter pruning を導入している．
加えて，我々の以前の研究 [6] でも Bloom フィルタを利用して分散環境での結合演算時の転送量を削減する手法を提案した．

Bloom フィルタは集合の各要素をビット配列で表現したダイ

Bloom フィルタは集合内における要素の存在確認のための，空間効率に優れたビット配列のデータ構造である． Bloom フィ

ジェストであるため，複数の集合間に存在する共通集合を表現す
るには，それら配列のビット論理積を行うことで容易に実現できルタによって二つの集合間の共通集合を表現するには，それらに対し論理積を行なうことで容易に実現できる．この仕組みは結合演算の効率化のために広く利用されている手法である．しかし集合が互いに素である場合に，それを示すには，従来では論理積
後のビット列がすべて 0 であればよいが，そうなることはほぼ無い．本論文ではこの問題を解決するために Bloom フィルタを拡張する三つの提案を示した．ビットが 1 である確率の低下と，ハッシュ関数の出力範囲の隔離，他関数の結果を入力とする関数の導入である．評価実験を通して，従来では不可能であった素集合判定が提案手法では可能であることを確認し，かつ最も実用的な提案手法を特定した．

る．[3, 4, 5, 6] はこの特徴を利用した手法で，実際に各タプルでの結合演算を行う前に， Bloom フィルタの論理積を行って，解集合を表現するビット配列を得て，各要素が解に存在するかどうかを判定することで解候補を絞り込んでいる．
一方で，二つの集合が互いに素である場合，すなわち共通する
元が一切存在しない場合を考える．このような場合，二つの集合が素集合であるかどうかの判定が容易に可能になれば，本来必要であった，その後の各要素の存在判定が不要になり，大幅な性能向上が期待できる．素集合判定の応用としては，結合演算，積集合，差集合など広範囲での応用が考えられる．
素集合判定の最も素朴な方法は，まず論理積を行ない，その結

Bloom ﬁlter is a space-eﬃcient data structurethat had been proposed to test whether a set contains an element. In order to represent an intersection of two sets, the bitwise AND operation between
their Bloom ﬁlters is performed. The mechanism
is widely used to improve the performance of somejoin operations. Assuming the two sets are mutually
disjoint, if the bit array after the AND operation
are set all the bits to 0, then we can determine it.
However such a situation is next to nothing if using the conventional Bloom ﬁlters. In this paper, toaddress this issue, we proposed three extensions for
Bloom ﬁlters; keep the probability which a certain
bit is set to 1 is low, isolate the output ranges ofhash functions, and introduce functions that input
the results of other hash functions. Through a series of experiments, we evaluated our approach cansupport disjoint sets test eﬃciently, and we foundthe most practical patterns of the extended Bloom
ﬁlters.
♥

正会員
非会員
♠
非会員
♣
正会員
♦

果のビット配列の全ビットが 0 であるかどうかを判定する方法である．しかしながら，二つの Bloom フィルタの論理積の結果のビット配列が 1 を含まないことは，従来の Bloom フィルタではほぼ無い．その理由は，従来の Bloom フィルタでは，任意のビットが 1 である確率は 1/2 になるように最適化されているためで，論理積後の配列での確率は 1/4 と非常に高い．そのため，実際には素集合であるにもかかわらず，共通集合が存在するという判定結果が下され，すなわち擬陽性が頻出し，各要素の存在チェックを逐一行うことになってしまう．
本論文では，この問題を解決するために， Bloom フィルタを拡張する次の三つの提案をする．

A) ビットが 1 である比率の抑制
B) 各関数の出力範囲を隔離C) 他の関数の結果を入力する関数の導入
提案手法の性能を評価するため実験を実施した．実験では，三つの提案を施した 13 種類の Bloom フィルタと従来の Bloom
フィルタとを比較した．比較内容は Bloom フィルタ本来の機能を保持できているかどうかの評価，素集合判定での誤判定の発生

産業技術総合研究所
産業技術総合研究所
産業技術総合研究所
産業技術総合研究所

a.matono@aist.go.jp
steven.lynden@aist.go.jp
yusuke.tanimura@aist.go.jp
kojima@ni.aist.go.jp

率の評価，素集合判定処理に要する時間の三つである．これらの評価の結果，従来法では不可能であった素集合判定が，提案手法では可能であることを確認した．また，評価した 13 種類の拡張

1
日本データベース学会論文誌 Vol.9, No.2

2010 年 11 月

一般論文

DBSJ Journal, Vol.9, No.2
November 2010

Bloom フィルタのうち， 2 個のハッシュ関数と，一つあるいは代入して，以下のように得ることができる．

二つの「他の関数の結果を入力とする関数」を持つ Bloom フィk≈

ルタが最も実用的であることを特定した．

m
ln 2.
n

(4)

偽陽性確率 q と要素数 n が与えられたとき，最短のビット配2.

Bloom フィルタの定義

列の長さ m は，式 (2) と 式 (4) より次のように決定できる．

Bloom フィルタは，長さ m のビット配列と，k 個のハッシm=−ュ関数を用いる．ハッシュ関数はビット配列の位置，すなわち[0, m) の範囲の整数を出力する1 ．実装としては SHA-1 や MD5などの通常のハッシュ関数の結果を m で割った剰余を用いる
ことが一般的である． 空の Bloom フィルタはすべてのビッ
ト が 0 で ある長 さ m のビット 配 列で あ る ．あ る 要素 x を
Bloom フィルタに追加するには，x を k 個のハッシュ関数に入力し，k 個の結果を得る．その結果が示す配列の位置のビット
array[f1 (x)], array[f2 (x)], . . . , array[fk (x)] をすべて 1 にする．なお，array[a] はビット配列 a 番目のビットを示す．ある要素 y の検索，すなわち，y が集合に含まれるかどうかを調べるには， y を k 個のハッシュ関数に入力して得られた k 個の位置の配列のビット array[f1 (y)], array[f2 (y)], . . . , array[fk (y)]のうち一つでも 0 であれば，その要素は集合に含まれない．逆にすべてが 1 であれば，その要素は集合に存在するか，あるいは実際には存在しないが，他の要素を追加したときに偶然全部 1n ln q(ln 2)2(5)

従来の Bloom フィルタを使った素集合判定の手法として，最も素朴な手法は論理積後のビット列すべてが 0 であるかどうかである．また，ほぼ精度に違いはないが，ハッシュ関数を k 個使
うことを利用した判定法が考えられる．その手法は，論理積後のビット列において，1 であるビットの数が k 以上であるかどうかである．k より少ない場合は，確実に共通の元が一つも存在しないことを保証できる．

3.

Bloom フィルタの拡張

互いに素な集合であるかどうか判定できるように，次の三つのBloom フィルタに対する拡張を提案する．
A) 1 であるビットの比率を下げる．
B) 各関数の出力範囲が重複しないようにする．
C) 他の関数の結果を入力する関数を導入する．

になったために誤判定したかのいずれかである．後者のように擬A) については自明ではあるが，従来はビットが 1 である確率

陽性による誤検出はあり得るが，偽陰性はない．また，要素の削が 1/2 では高すぎるため，関数の数を減らすことで，その確率除はできない．ただし， Counting Bloom フィルタ [2] は，ビッを下げる．それによって論理積後のビット配列の 1 である確率を

トの代わりに整数を用いたものであるため，削除も可能になる．

低下できる．従来は p = 1/2 で最適になるよう，擬陽性確率 q

ハッシュ関数が配列の各位置を同じ確率で出力する前提を置くと要素数 n を入力とし，関数数 k やビット長 m を決定していと，要素をひとつ追加したとき，あるビットが選択される確率はたが，提案手法では，擬陽性確率 q ，要素数 n に加え，関数数 k1/m で，逆に選択されない確率は 1−1/m である． したがって，k 個のハッシュ関数を用いて，n 個の要素を追加した後のあるビットが未だに 0 である確率は次のようになる．

(

1−

1
m

も与えられるよう拡張する．q および n，k が与えられビット長m を求める式は式 (1) と式 (2) より次のように得られる．

)knm0 = −

(

1
m

)kn

kn

(6)

法が考えられる．一つ目は，演算時に両者のビット配列を最小公倍数になるよう両ビット列を延長する手法である．二つ目は，あらかじめ両ビット配列の長さをm → ∞ と仮定すると，テイラー展開より，以下に近似できる．
p ≈ 1 − e− m1

また，論理積を行うビット配列の長さが異なる場合，二つの手

逆に，任意のビットが 1 である確率 p は次のようになる．

p=1− 1−kn
ln(1 − q k )0

m00 = 2blog2 m +0.5c

(7)

(1)
を満足するように縮小あるいは延長するよう初期化しておいて，ある要素の検索時に，擬陽性が発生する確率 q は以下である．
k

q=p .

要素を追加した後，演算時に短いビット配列のみを長い方に一致するように延長する手法である．いずれの延長方法も，関数の実(2)

装方法に確認するが，一般的なハッシュ値の剰余を用いた関数で式 (1) と 式 (2) より，以下の式を導くことができる．

n≈−m
ln p ln (1 − p)ln q

あれば，ビット列を繰り返して延長する．

(3)B) については，式 (6) によって決定した長さ m のビット配
列を k 個の長さ m/k の部分ビット配列に分割し，各関数の出力範囲が重複しないようにする手法である．具体的には，i 番目の関数が出力する範囲は，[0, m) ではなく [im/k, (i + 1)m/k) にする (0 ≤ i ≤ k − 1).

したがって， q や m に関わらず，p = 1/2 の時 n が極大となる．
ビット配列の長さ m と要素数 n が与えられたとき，擬陽性の確率が最小となるハッシュ関数の数 k は，p = 1/2 を 式 (1) に
1[a, b) は {x|a ≤ x < b} を意味する左閉右開区間である．

2
日本データベース学会論文誌 Vol.9, No.2

2010 年 11 月

一般論文

DBSJ Journal, Vol.9, No.2
November 2010

C) について，従来の Bloom フィルタではハッシュ関数のみる関数を導入する．具体的には，関数 fa と fb が従来のハッシュ

1. Bloom フィルタとしての性能
2. 素集合判定処理時の擬陽性による誤検出発生率
3. 素集合判定処理の時間関数であると仮定すると，例えば mod(fa (x) + fb (x), m/k) やmod(fa (x) × fb (x), m/k) などがある2 ．本論文では，このよう関数は MD5 を用い，複数のハッシュ関数の場合，i 番目のハッな関数を共起検査関数と呼ぶ．

シュ関数は入力要素に i − 1 を加えたものを入力する．

を用いていたが，提案手法では複数の他の関数の結果を入力とす実験で用いた Bloom フィルタは次の 14 種類である．ハッシュ

共起とは，ある Bloom フィルタにおいて，任意の二つのビッ

HK*1 従来の Bloom フィルタで，関数数 k とビット長 m は式 (4) と 式 (5) によってそれぞれ決定する．素集合判定は論理積後ビット列に 1 であるビットが k より少ないかどう

トが一つの要素によって同時に 1 に設定されることを言う．例えば，要素 x を追加したとき，ハッシュ関数 fa と fb に入力した
結果，i = fa (x) 番目のビットと，j = fb (x) 番目のビットが 1かで行なう．

に設定されるため，i 番目のビットと j 番目のビットは要素 x にH1*1 ハッシュ関数が一つで，m は 式 (6) によって決定する．
以降すべて，m は 式 (6) で決定する．
H2*1 2 個のハッシュ関数を用い，出力範囲は分割しない．
H4*1 4 個のハッシュ関数を用い，出力範囲は分割しない．
H1*2 2 個のハッシュ関数を用い，出力範囲は m/2 の長さに 2おいて共起していると言う．
共起検査関数は，従来のハッシュ関数と同様にある要素のメン
バ判定の役割以外に，ある二つのビット位置が共起しているかど
うかを検査するための関数としての役割も持っている．二つのビット位置 i と j を入力したとき，その結果の位置のビットが 1

分割する．

であれば i と j は共起している可能性があるが，ビットが 0 でH1*4 4 個のハッシュ関数を用い，出力範囲は m/4 の長さに 4あれば共起していないことを保証できる．

分割する．

関数は，他の関数との間に相関がない関数でなければ，Bloom
フィルタとしての機能が失なわれる．相関するとは，二つの関数

H2*1 F1*1 2 個のハッシュ関数と，それらの和を出力する共起検査関数を用い，出力範囲は 2m/3 と m/3 の長さに 2 分に同じ要素を入力したとき，それらの結果に何らかの関係がある

割し，前者をハッシュ関数，後者を共起検査関数の出力範囲と予想できることを言う．例えば，mod(fa (x) + fb (x), m/k) ととする．

mod(fa (x) + fb (x) + 1, m/k) は，常に隣合う二つビットを出力する強く相関した関数である．一方，hash(x) と hash(x + 1)

H1*2 F1*1 2 個のハッシュ関数と，それらの和を出力する共起検査関数を用い，出力範囲は m/3 の長さに 3 等分し，各関はハッシュ関数を介するため相関はない．

数が各部分ビット列を担当する．

これら三つの拡張を施した Bloom フィルタを用いることで，

H1*2 F1*2 m/4 の長さに 4 等分する．2 個のハッシュ関数とそれを入力とする和と積の 2 個の共起検査関数を用いる．

従来の Bloom フィルタではほぼ実現できなかった素集合判定を行なうことができるようになる．例えば，関数の数が 4 で，ビッ

すなわち，前節の最後に示した例と同じである．

ト長が 1024 であるとき，関数 fa は [0, 256)，fb は [256, 512) のH1*4 F1*2 4 個のハッシュ関数と 2 個の共起検査関数を用い，m/6 の長さに 6 等分する．共起検査関数は総和と総積で範囲を出力するハッシュ関数で，他の関数は fc = mod(fa (x) +fb (x), m/k) と fd = mod(fa (x) × fb (x), m/k) であると仮定すある．

る．部分ビット列 [0, 256) のうち，1 であるビットの位置の集合

H1*2 F1*4 2 個のハッシュ関数と 4 個の共起検査関数を用い，m/6 の長さに 6 等分する．共起検査関数は和と積，差，商{a|array[a] = 1, 0 ≤ a < 256} と， [256, 512) のうち，1 であるビットの位置の集合 {b|array[b] = 1, 256 ≤ b < 512} を求めである．

る．これらの集合に対し，各組合せで和と積が示す位置のビット

H1*2 F1*6 m/8 の長さに 8 等分する．2 個のハッシュ関数と，和，積，差，商，とビット論理和，ビット論理積の 6 個の共array[mod(ai + bj , m/k)] ， array[mod(ai × bj , m/k)] を評価する．もし，任意の組合せで和と積の両方が 1 であれば，共起検査関数を用いる．

通集合が存在する可能性があることを示し，すべての組合せで和H1*2 F1*8 m/10 の長さに 10 等分する．2 個のハッシュ関数と積の少なくとも一つが 0 であれば共通集合が一切存在しないと，和，積，差，商，とビット論理和，ビット論理積，ビッことを意味する．なお素集合判定でも偽陽性による誤検出はある

ト排他的論理和，ビットシフトの 8 個の共起検査関数を用が，偽陰性はないすなわち，共起検査関数は従来のハッシュ関数

いる．

としての役割だけでなく，任意の 2 ビットが同じ要素によって立H1*2 F1*10 m/12 の長さに 12 等分する．2 個のハッシュ関数

てられたかどうかを検査するために利用する．

4.

と，和，積，差，商，とビット論理和，ビット論理積，ビッ
ト排他的論理和，ビットシフト，及びハッシュ値を更にハッ実験による性能評価

シュした値の和と積の 10 個の共起検査関数を用いる．

本論文では，実験を通して提案手法の性能を評価する．実験は4.1

次の 3 種類を行った．
2

Bloom フィルタとしての性能提案手法は，互いに素であることを特定できるよう Bloom
フィルタを拡張したものである．しかしながら，そもそものmod 関数は剰余演算を意味する．

3
日本データベース学会論文誌 Vol.9, No.2

2010 年 11 月

一般論文

DBSJ Journal, Vol.9, No.2
November 2010

1.E-01

1.E+10

1.E-02

1.E+09

率生発性1.E-03
陽擬1.E-04の際
実1.E-05

HK*1
H2*1
H1*2
H2*1_F1*1
H1*2_F1*2
H1*2_F1*4
H1*2_F1*8
H1*2_F1*1_C1*1

1.E-06
1.E-07

HK*1
H1*1
H2*1
H4*1
H1*2
H1*4
H2*1_F1*1
H1*2_F1*1
H1*2_F1*2
H1*4_F1*2
H1*2_F1*4
H1*2_F1*6
H1*2_F1*8
H1*2_F1*10

1.E-06

1.E-05

1.E-04

理想の擬陽性確率

長トッ
ビ1.E+08のタル
ィ1.E+07
フ

H1*1
H4*1
H1*4
H1*2_F1*1
H1*4_F1*2
H1*2_F1*6
H1*2_F1*10

m
ool
B

1.E+06

1.E+05

1.E-03

1.E-020.000001

0.00001
0.00010.001
Bloomフィルタの擬陽性確率0.01

図 2 偽陽性確率に対する拡張 Bloom フィルタのビット長

図 1 拡張 Bloom フィルタにおける理想の擬陽性確率に対す

Fig. 2 Bit length of extended Bloom filters.

る実際の偽陽性発生率

Fig. 1 False positive probability of extended Bloom filters.

が integer の最大値からあふれたため，10−5 以下は評価できな

Bloom フィルタとしての機能，すなわちある要素が集合のメン

かった．その他のものは，理想値にほぼ沿っているため，提案手

バであるかどうか評価できる機能が低下しては本末転倒である．

法の A）B) C) とも基本的に従来の利用に耐えうることが確認したがって，本節では Bloom フィルタとしての機能が低下するできる．ただし，関数の数が非常に小さい時にはビット列の長さかどうかを評価するために，まず擬陽性発生率を実験によって求が問題になる．また共起検査関数はより相関の無いものを採用すめた．実験は，空の Bloom フィルタに集合 S を追加した後，S

るか 4 より小さくする必要がある．

の元でない要素 x ∈/ S がその Bloom フィルタに存在しているか

次に Bloom フィルタのビットの長さを調べる．長すぎるとどうかを評価する．要素 x は集合 S の元でないため，もし存在オーバーフローが発生したり，処理速度が低下したりするなど問すると判定した場合は擬陽性による誤検出が発生したことを意味

題が発生するため，短い方がよいことは自明ではあるが，われわする．このテストを何度か繰り返して，擬陽性発生率を求める．

れは応用によってはある程度の長さは許容できると考えている．
図 2 は擬陽性確率に対する Bloom フィルタのビット長を示した

集合 S は一様乱数によって生成する．

図である．追加要素数は 100, 000 とした．

図 1 は Bloom フィルタの擬陽性発生率を示したグラフである．横軸は Bloom フィルタを初期化する際に与えた理想の擬陽

この図から，いずれも Bloom フィルタの擬陽性確率に比例し性確率で，縦軸は実際に計測した擬陽性発生率である．したがっているのがわかる．また，図 1 で述べたように， H1*1 は 10−5て，横軸の値から外れると性能が低下していることになる．な

以下では桁あふれし，計測できていない．追加要素数が大きく，

お，実験は Bloom フィルタへの追加要素数は 100, 000 で，評

擬陽性確率が小さい時は，H1*1 は利用は難しいことがわかった．

−6

価回数は各 10, 000, 000 回である．すなわち，10

ビット長の増加の割合は，関数の数の累乗に比例しているようにの場合に許見える．すなわち，ビット列が長い場合，関数を一つ追加すると，容される擬陽性発生回数は 10 回である．

長さは半分になる．ビット数の長さが問題になるような場合は，

ま た ，共 起 検 査 関 数 が 他 の 関 数 と 相 関 が あ る 場 合 に 偽
陽 性 発 生 率 が ど う な る か を 評 価 す る た め ，本 実 験 に 限 り，関数の数を一つでも増やすと，長さは大幅に短縮できる．

H1*2 F1*1 C1*1 を 追 加 し た ．H1*2 F1*1 C1*1 は ，関 数 の出 力 範 囲 分 割 は 4 で ，二 つ の ハッシュ関 数 と 二 つ の 共 起 検

4.2

査 関数 で構成 され，共 起 検査関 数 とし て ，ハッシュ関数 の 和することが本研究の目的である．素集合判定の擬陽性発生率の評

mod(fa (x) + fb (x), m/k) と，それに明らかに相関する，単に 1

価実験は，二つの Bloom フィルタを用意し，それらに互いに素を加算した mod(fa (x) + fb (x) + 1, m/k) を用いた．

な集合 R と S を追加し，この Bloom フィルタ同士で素集合判

素集合判定の擬陽性発生率

素集合判定の擬陽性発生率は最も重要な指標で，この値を改善

図 1 から判断できることは，H1*2 F1*1 C1*1 が終始，理想定処理を行う．実際には共通集合が存在しないため，共通集合がの偽陽性発生率から外れていることが確認できる．すなわち，共あると判定された場合は擬陽性による誤検出が発生したことにな

起検査関数にはできる限り，互いに相関がないものを利用しなける．一定回繰り返して，擬陽性が発生した回数を求め，その比率ればならないことが判る．その他は， H1*2 F1*4， H1*2 F1*6，を擬陽性発生率とする．論理積を行う二つの Bloom フィルタは，

H1*2 F1*8，H1*2 F1*10 が外れていることが確認できる．これ同じタイプの Bloom フィルタで，追加要素数，擬陽性確率も等

らは完全に相関関係のない共起検査関数が用意できなかったためしい値を用いたため，ビット配列の長さも等しい．

3

素集合判定の擬陽性発生率の評価は， 2 種類の実験を行った．
Bloom フィルタの擬陽性確率をパラメタとした場合と， Bloom
フィルタに追加する要素数をパラメタとした場合の 2 種類であと考えられる ．また図からは分かりづらいが，H1*1 はビット長3

本論文では，われわれは完全に相関のない共起検査関数を用意できなかったが，探せば存在する可能性は十分ある．

4
日本データベース学会論文誌 Vol.9, No.2

2010 年 11 月

一般論文

DBSJ Journal, Vol.9, No.2
November 20101

用する H1*2 F1*4，H1*2 F1*6，H1*2 F1*8，H1*2 F1*10 は

0.9

Bloom フィルタの擬陽性確率が低い場合でも，素集合判定の擬

率生0.8
発性0.7
陽擬0.6
の定0.5
判合0.4
集素0.3
0.2

HK*1
H1*1
H2*1
H4*1
H1*2
H1*4
H2*1_F1*1
H1*2_F1*1
H1*2_F1*2
H1*4_F1*2
H1*2_F1*4
H1*2_F1*6
H1*2_F1*8
H1*2_F1*10

0.1
0
1.E-07図3

陽性発生率が 0 にならない．これは関数の数が多くなると 提案

1.E-06

1.E-05
1.E-04
1.E-03Bloomフィルタの擬陽性確率

1.E-02の A) 「 1 であるビットが比率を下げる」ことに反するためである．これらから現時点でも最も優れた拡張 Bloom フィルタは
H2*1 F1*1，H1*2 F1*1， H1*2 F1*2 の三つが通常の Bloom
フィルタとしても，素集合判定の擬陽性の面でも安定して優れた性能である．
図 4 でも同様に，提案の B) 「各関数の出力範囲が重複しない
ようにする」方法や C) 「他の関数の結果を入力する関数を導入

1.E-01

する」方法が効果的であることが確認できる．また図 3 とほぼ同様の結果になっている．すなわち，最も優れた手法が H1*1 で，Bloom フィルタの擬陽性確率に対する素集合判定の擬陽性発生率

最も悪い手法が HK*1 であることや， H1*2 F1*4，H1*2 F1*6，

Fig. 3 False positive probability of intersections for thatH1*2 F1*8，H1*2 F1*10 は要素数が少ない場合でも素集合判
定の擬陽性発生率が 0 にならないことは一致した結果である．
異なった結果としては，図 4 では H1*2 F1*2 が H2*1 F1*1，
H1*2 F1*1 より，やや優れていることを示した点が異なる．

of Bloom filters.
1

HK*1
H1*1
H2*1
H4*1
H1*2
H1*4
H2*1_F1*1
H1*2_F1*1
H1*2_F1*2
H1*4_F1*2
H1*2_F1*4
H1*2_F1*6
H1*2_F1*8
H1*2_F1*10

0.9

率生0.8
発性0.7
陽擬0.6
の定0.5
判合0.4
集素0.3
0.2
0.1
0
1

図4

10

100

Bloomフィルタの要素数

1000

なお，ラインがジグザグになっているのは，共起検査関数を多く用いた場合で，共起検査関数同士が相関しているために起こると考えられる．

4.3

素集合判定の処理時間

最後に，提案した拡張 Bloom フィルタで素集合判定処理を行った場合の処理時間を評価する．いくら擬陽性が発生しないとしても処理コストが非常に高いようであれば，その Bloom フィ
ルタは実用的でないため，処理時間を評価する必要がある．

10000

実験に用いた計算機は CPU が Intel Core2 Quad Q9450(2.66 GHz) ，メインメモリが 4 Gbytes, OS が Ubuntu Linux
10.04 (kernel 2.6.32) であった．実験は，Bloom フィルタはディ

追加要素数に対する素集合判定の擬陽性発生率

Fig. 4 False positive probability of intersections for the

スク上に構築し，素集合判定はオンメモリで行なった．

number of inserted elements.

実験は 図 4 の実験の際に同時に素集合判定処理時間を計測し，る．それぞれの実験結果を図 3 と図 4 に示す． いずれも縦軸は

平均処理時間 (ミリ秒) を求めた．その結果を図 5 に示す．横軸

素集合判定の擬陽性発生率である．横軸は，図 3 が Bloom フィは追加要素数で，縦軸は素集合判定処理の 1 回に要する処理時

ルタの擬陽性確率で，図 4 が Bloom フィルタへの追加要素数で，間の平均である．
図 5 から H1*4 が最も高速で，それに次いで H4*1 が速い．

いずれも対数スケールである．すなわち，いずれも素集合判定の擬陽性発生率が 0 から離れるのが遅ければ遅いほど良いことを

このことから，精度の面だけでなく，速度の面でも，提案の B)意味している． 図 3 では要素数を 100 とし， 図 4 では Bloom「各関数の出力範囲が重複しないようにする」方法が有効な手段

フィルタの擬陽性確率を 0.00001 として，実験を実施した．

であることが確認できる．また，共起検査関数を多く用いた場

図 3 から，H1*1 が最も優れており， HK*1 が最も劣っている

合は処理性能が低下することも確認できる．H1*1 は処理内容はことから，提案の A) 「1 であるビットの 比率を下げる」方法が単純であるが，ビット長が長いため，その読み込みに時間を要す

有用であることが確認できる．また，H4*1 より H1*4 が優れてると考えられる．これまでの結果から最も実用的で優れた性能

おり，H2*1 より H1*2 が優れていることがわかる．このことかの H1*2 F1*2 や H2*1 F1*1， H1*2 F1*1 は，H1*2 F1*2 がら，提案の B) 「各関数の出力範囲が重複しないようにする」方やや遅いが，十分実用的な速度で処理できることがわかる．

法が有効な手段であることが確認できる．また，H4*1 や H1*4の関数の結果を入力する関数を導入する」方法も大変効果的であこ れ ら の 実 験 結 果 よ り，提 案 手 法 の う ち ，H1*2 F1*2，
H2*1 F1*1，H1*2 F1*1 の 3 手法が最も優れた手法であることが確認できた．H2*1 F1*1 と H1*2 F1*1 の特性は，本実験ることが確認できた．

ではほぼ同じであったため，さらなる詳細な実験を行なう必要がより H1*1 F1*2 が非常に優れていることから，提案の C) 「他

各 Bloom フィルタは，最も優れた手法が H1*1 ではあったある．また H1*2 F1*2 は図 4 の要素数に対する疑陽性発生率にが，H1*1 は 4.1 節での実験で Bloom フィルタ自体の性能が十関しては，H2*1 F1*1 と H1*2 F1*1 より優れた結果をであっ分とは言えないことを確認している．次に共起検査関数を多く利た．一方処理時間では H2*1 F1*1 と H1*2 F1*1 の方が高速で

5
日本データベース学会論文誌 Vol.9, No.2

2010 年 11 月

一般論文

DBSJ Journal, Vol.9, No.2
November 2010

1.E+00tocol. IEEE/ACM Trans. Netw., 8(3):281–293, 2000.
[3] L. F. Mackert and G. M. Lohman. R* optimizer validation and performance evaluation for distributed queries.
In W. W. Chu, G. Gardarin, S. Ohsuga, and Y. Kambayashi eds., VLDB, pp. 149–159. Morgan Kaufmann,
1986.
[4] L. Michael, W. Nejdl, O. Papapetrou, and W. Siberski. Improving distributed join eﬃciency with extended
bloom ﬁlter operations. In AINA, pp. 187–194. IEEE
Computer Society, 2007.
[5] Oracle Corporation.
Data warehousing on oracle
rac best practices, October 2008. An Oracle White
Paper, http://www.oracle.com/technology/products/
database/clustering/pdf/bp_rac_dw.pdf.
[6] 的野, 小島. 分散 rdf 問合せ処理時の転送量減少のためのブルームフィルタの拡張. 情報処理学会論文誌 データベース（TOD）［電子情報通信学会データ工学研究専門委員会共同
編集］, Vol.2(No.1):33–45, 3 月 2009 年.

HK*1
H1*1
H2*1
H4*1
H1*2
H1*4
H2*1_F1*1
H1*2_F1*1
H1*2_F1*2
H1*4_F1*2
H1*2_F1*4
H1*2_F1*6
H1*2_F1*8
H1*2_F1*10

1.E-01間時1.E-02
理処
定判1.E-03
合集
素1.E-04
1.E-05
1.E-06
0

2000

4000
6000
Bloomフィルタの要素数

8000

10000

図5

追加要素数に対する素集合判定の処理時間

Fig. 5 The processing times of a disjoint sets test for thenumber of inserted elements.

あるという結果となった．
また実装の面から考えると，H2*1 F1*1 と H1*2 F1*1 はビッ
ト列を 3 で割ることになる．そのため，式 (7) で示した，異なる長さのビット列で論理積を行うための方法を採用する場合に，的野 晃整 Akiyoshi MATONO

3 で割る必要のある H2*1 F1*1 と H1*2 F1*1 より 4 で割ることができる H1*2 F1*2 の方が 2 進数である計算機と相性がよい

産業技術総合研究所情報技術研究部門研究員．2005 奈良先端科
学技術大学院大学 情報科学研究科博士後期課程修了，工学博士．

実装である．

RDF データベースの研究に従事．情報処理学会，ACM，日本

5.

まとめ

データベース学会各会員．

スティーブン リンデン Steven LYNDEN

本論文では，Bloom フィルタを拡張し，異なる集合が互いに素

産業技術総合研究所情報技術研究部門特別研究員．2004 カー

であるかどうかを容易に判定できる三つの拡張手法を提案した．

ディフ大学 (UK) にて Ph.D. 取得．マルチエージェントシステ

A) 1 であるビットの比率を下げるB) 各関数の出力範囲が重複しないようにする
C) 他の関数の結果を入力する共起検査関数を導入する

ムおよび，データインテンシブ分散システムの研究に従事．OGF

DAIS Working Group Secretary．

谷村 勇輔 Yusuke TANIMURA

提案手法の性能を評価するため 3 種類の実験を行った． Bloom

産業技術総合研究所情報技術研究部門研究員． 2004 同志社大学

フィルタ自体の性能を評価と，素集合判定の精度評価，素集合判

大学院工学研究科知識工学専攻博士課程修了，工学博士．グリッ

定の速度評価である．実験結果から，従来の Bloom フィルタでドコンピューティング，クラウドコンピューティングの基盤シスは不可能であったが，提案手法は素集合判定に非常に適した拡張

テムに関する研究に従事． USENIX，情報処理学会，各会員．

であることを確認した．また， 2 個のハッシュ関数と 2 個の共小島 功 Isao KOJIMA

起検査関数を用いた H1*2 F1*2 と 2 個のハッシュ関数と 1 個

産業技術総合研究所情報技術研究部門サービスウェア研究グルーの共起検査関数を用いた H2*1 F1*1 と H1*2 F1*1 の三つが優プグループ長．データグリッドの研究に従事．情報処理学会，れた性能で，速度面では H2*1 F1*1 と H1*2 F1*1 の方が優れ，

ACM，IEEE 各正会員． OASIS メンバ．OGF DAIS Working
Group Co-Chair．

精度面と実装面では H1*2 F1*2 が優れていることがわかった．

[謝辞]
本研究の一部は，総務省戦略的情報通信研究開発推進制度(SCOPE) 092103006 の助成を受けたものである．

[文献][1] B. H. Bloom. Space/time trade-oﬀs in hash coding withallowable errors. Commun. ACM, 13(7):422–426, 1970.
[2] L. Fan, P. Cao, J. M. Almeida, and A. Z. Broder. Summary cache: a scalable wide-area web cache sharing pro-6
日本データベース学会論文誌 Vol.9, No.2

2010 年 11 月