データベース解析の ための ゼロサプレス型二分決定グラフの 簡単化に 関する考察
Considerations of Optimizing Zero-Suppressed Binary Decision Diagrams for Database Analysis
岩崎 玄弥 †Haruya Iwasaki

湊 真一 †ツォイクマン トーマス †Shin-ichi MinatoThomas Zeugmann

Abstract: Recently, an efficient method of database analysis using Zero-suppressed Binary Decision
Diagrams (ZBDDs) has been proposed. BDDs are graph-based representation of Boolean functions, now
widely used in system design and verification area. Here we focus on ZBDDs, a special type of BDDs,
which are suitable for handling large-scale combinatorial itemsets in transaction databases. The ZBDD
size greatly depends on variable ordering. In this paper, we investigate the property of ZBDD variable
ordering for the histogram of item sets in the database, and consider good ordering methods.

は じめに

1.

近年，大規模記憶装置の 発展な ど に よって ，大規
模な データベースの 中から有用な 規則を発見する
データマイニングの 研究が盛んに な って いる．頻出パタンマイニング (Frequent Pattern Mining)
は ，最も基本的な データマイニング問題で あり，Agrawal 等 [1] に よる Apriori アルゴリズムの 研
究に 始まり，現在まで に 様々な アルゴリズムが提案されて いる [7, 3]．
本稿で は ，VLSI CAD の 分野で 大規模論理関数データの 表現法と して 広く用いられて いる二分決定グラフ (BDD: Binary Decision Diagrams)[2] ，その 中で も「 ゼロサプレス型 BDD」 (ZBDD: Zerosuppressed BDD)[4] と 呼ば れるデータ構造を用いて ，トランザクションデータベースに おけるアイ
テムセットの 頻度表を効率よく生成する手法 [6] に関して ，実験と 考察を行った．ZBDD は 大規模な組合せ集合データを非明示的に 列挙し，効率よく演算処理を行うこと がで きる．また，数式に より組合せ集合の 演算を記述し，これを ZBDD を用いて 計算するプログラム「 VSOP」 [5] を用いた．
これまで ，ZBDD に おけるアイテムの 順序付けが，生成される ZBDD の 大きさに 顕著な 影 響を与えること は 知られて いたが，実際に ど の ような 場合に 顕著な 影 響があるの かは は っきりと は 調べられて いな かった．そこで ，ZBDD の データベースの 頻度表表現に 特有の 順序付けの 性質に ついて 調べた．また，データベース中に あまり出て こな い非頻出アイテムの 削除の 影 響に ついて も実験を行った．さらに ，データベースの 特徴に 基づ くアイテ
ム変数の 順序付け法の 考察に ついて も述べる．
†北海道大学 大学院 情報科学研究科

図 1: 二分決定木と BDD,ZBDD

2.

ZBDD に よるデータベース表現

2.1

BDD

BDD[2] は ，図 1 に 示すような 論理関数の グラフに よる表現で ある．一般に ，論理関数の それぞれの 変数に 0,1 の 値を代入した結果を，二分岐の 枝（ 0-枝/1-枝） で 場合分けし得られる論理関数の 値を，2 値の 定数節点（ 0-終端節点/1-終端節点） で表現すると ，図 1 の ような 二分木状の グラフに なる．この と き，場合分けする変数の 順序を固定し，冗長な 節点の 削除と 等価な 節点を共有すると いう
2 つの 縮約規則を可能な 限り適用すること に より，「 既約」 な 形が一意に 得られること が知られて いる．
複数の 論理関数を表す BDD の 間に おいて も，変数順序を固定すれば グラフを共有すること がで きる．
BDD は ，多くの 実用的な 論理関数を比較的少ない記憶量で 一意に 表現すること がで きる．また，2つの BDD を入力と し，それらの 二項論理演算の 結果を表す BDD を直接生成するアルゴリズムが考案されて いる．この アルゴリズムは ハッシュテー
ブルを巧みに 用いること で ，データが計算機の 主記憶の 範囲に 収まる限りは ，その 記憶量に ほぼ比
例する時間内で 論理演算を効率よく実行で きる．

2.2

ZBDD

BDD は 元々は 論理関数を表現するために 考案されたもの だが，これを用いて 組合せ集合データを表現・操作すること もで きる．組合せ集合と は ，「 n個の アイテムから任意個を選ぶ組合せ」 を要素とする集合で ある．
これを BDD で 表現すると き，類似する組合せが多ければ ，部分的に 共通する組合せがグラフ上で 共有されて ，記憶量や計算時間が大幅に 削減される場合がある．さらに ，組合せ集合に 特化した
ZBDD[4] を用いると ，より簡潔な 表現が得られ，一層効率よく扱うこと がで きる．
ZBDD で は ，冗長な 節点を削除する簡約化規則が通常の BDD と は 異な る．ZBDD で は 1-枝が 0終端節点を直接指して いる節点を取り除く，と いう規則に な って いる．これに より，ZBDD で は 図
1 の ように ，組合せ集合に 一度も選ば れること のな いアイテムに 関する節点が自動的に 削除される
こと に な り，BDD よりも効率よく組合せ集合を表現・操作すること がで きる．
2.3

VSOPVSOP(Valued-Sum-Of-Products)[5] は ，数式により組合せ集合の 演算を記述し，これを ZBDD を用いて 計算するプログラムで ある．VSOP は 非常に 多数の アイテム変数の 組合せを要素と する積和集合を扱うこと がで き，また，単な る集合演算だ
けで な く，集合の 各要素に 整数値（ 係数あるいは重み） を定義し，加減乗除や大小比較な ど の 算術演算を含む数式を処理で きること を特徴と する．
ここで ，ZBDD を用いて 重み付き積和集合を非明示的に 表現する方法に ついて 述べる．ZBDD は組合せ集合を表すこと しかで きな いため，その ままで は 重みを表現で きな い．これの 解決法と して ，
本稿で は 整数値を 2 進数に 分解する方法を用いる．
n 個の ZBDD{F0 , F1 , . . . , Fn−1 } をベクトル状に 並べると ，最大 (2n − 1) まで の 重みを表現することがで きる．すな わち，整数値の 重みを 2 進数で 符号化し，最下位ビットが 1 に な る組合せ集合を F0 ，次の ビットが 1 に な るような 組合せ集合を F1 ，という形で Fn−1 まで 並べること に より，図 2 の ように ，各項の 重みを非明示的に 表すこと がで きる．
2.4

ZBDD に よるデータベース表現

VSOP を用いること で ，トランザクションデー
タベースに おいて 頻度表の 生成を効率よく行うこと がで きる．本稿で は ，タプル頻度表と パタン頻

図 2: (5abc + 3ab + 2bc + c) の 2 進ベクトルに よる表現
度表に ついて 実験，考察を行う．
タプル頻度表と は ，トランザクションデータ中に 同じアイテムの 組合せ（ タプル） が何回出現したかを数えて 表に したもの で あり，パタン頻度表とは ，各タプルの 中に 出現するアイテムの 部分集合（ パタン） の 出現回数を数えて 表に したもの で ある．
通常の 組合せ集合で は ，組合せパタンの 有無の みに 着目し重複は 考慮しな いが，実際の データベー
スで は 同じタプルやパタンが複数回出現することがしば しば あり，その 出現回数を数えること が必要な 場合がある．この ような 場合に 重み付き積和集合を用いると 頻度表を効率的に 生成すること がで きる．また，一般に k 個の アイテムからな るタ
プルは 2k 個の パタンを含んで いるの で ，パタン頻度表は タプル頻度表よりもは るかに 大きな もの にな り，小規模な 場合を除いて 完全な パタン頻度表を生成すること は 困難で ある．しかし，ZBDD を用いる場合，多数の 類似するパタンをグラフで 共有して コンパクトに 表現で きるの で ，ある程度の規模まで パタン頻度表を現実的に 生成で きる可能性がある．

3.

データベース表現に おける ZBDD の 簡単化

前述の ように ，ZBDD を用いること で 頻度表を効率よく生成で きる可能性があるが，データベースが大規模に な ると ，頻度表を生成すること が困難に な る．これを改善する手法と して ，本稿で は ，「 非頻出アイテムの 削除」 と 「 アイテム変数の 順序付け」 と いうこと を考える．

3.1

非頻出アイテムの 削除

実際の データベースに おいて は ，アイテムの 出現頻度に 大きな 偏りがある場合が多く見られる．この と き，出現頻度の 低いアイテムを取り除くことに よって ，ZBDD の データ構造を小さくしようというの が「 非頻出アイテムの 削除」 で ある．その方法と して ，適当な しきい値 α を指定して ，それより多く出現するアイテムだけを用いて 頻度表を生成する，と いうこと を行う．本稿で は ，しきい値をある値に 定めたと きに ，ど の 程度の データの縮約効果があるの か，また，演算処理に かかる時間がど う変化するの かに ついて 調べた．結果は 4章に 示す．

3.2 アイテム変数の 順序付けの 影 響
本稿で 使用した VSOP プログラムで は ，データベースに 含まれるをアイテムをアイテム変数と して 最初に 宣言する．宣言されな かった変数は ，その 変数が算術式中で 使用されたと きに ，その 場で新たに 宣言したもの と して ，最上位に 追加される．
アイテム変数の 順序付けは ，生成される ZBDD のサイズに 影 響を与える．と ころで ，ZBDD の 性質上，最悪な 順序付けを用いて も節点数は パタンを羅列したと きの 総文字数を超えること がな い [6] ため，総文字数が少な け
れば ど の ような 順序付けで も，ZBDD の サイズが膨らむこと は な い．この こと から，アイテム変数の 順序付けに より指数関数的な 効果が表れるために は ，最悪な 場合が指数関数的な 節点数に な る必要があるの で ，データ中に は パタンを羅列したと
きの 総文字数が非常に 多くな ければ な らな いと いうこと がいえる．一般的に ，パタンは アイテム数の 指数個あるの で ，アイテム変数の 順序付けに より，大きな ZBDD の 簡単化効果が得られると 期待
で きる．
3.3

データベースの 特徴を用いた発見的手法による順序付け法

前述の こと を踏まえて ，アイテム変数の 順序付
けに 関して ，データベースを読み込んで アイテムが初めて 現れた順や，アイテム変数の 出現頻度の降順，または 昇順に 並べた場合に おいて 実験した．
結果は 4 章に 示す．ここで 出現頻度に 関する順序付けを行うの は ，出現頻度が高いアイテム変数は多くの アイテムと 関係して いる可能性が高いからで ある．
また，LSI 論理設計分野の BDD の 変数順序付け法を応用した手法に ついて も後述する．

4.

4.1

非頻出アイテムの 削除

まず，ZBDD の 簡単化の ための 実験と して ，代表的な トランザクションデータベースに ついて ，非頻出アイテムの 削除を行って ，タプル頻度表と パタン頻度表を生成する実験を行った．それぞれの結果を表 1,2 に 示す．今回，タプル頻度表に 関しては 6 つの データベースを，パタン頻度表に 関して はZBDD の サイズが膨大な もの に な って しまうの で ，3 つの データベースを用いた．ここで α は しきい
値，#R は データ中の アイテムの 削除率，size は 節点数，count は 式に 現れる組合せの 個数，time(s)は VSOP の 処理時間（ 秒） で ある．
この 結果を見ると ，タプル頻度表，パタン頻度表の 両方の 場合と も，データベースに より差は あ
れど ，大きな 縮約効果が見て 取れる．
処理時間に 関して 見ると ，タプル頻度表に ついて は 多くの 場合，しきい値を上げるに つれて 処理時間が増加して いる．これは ，非頻出アイテムを削除して いくに つれて 同じもの を表すタプルが増えて いき，VSOP で 計算する際の 重みの 数値を表
す 2 進数の 桁数が増えて いったこと に よるもの と考えられる．これと 同じこと がパタン頻度表に ついて も言えると 思われるの だが，パタン頻度表では 処理時間が減少して いく傾向に ある．これは ，桁数増大の 影 響以上に 非頻出アイテムの 削除に よって パタンの 数が激減して いるためと 思われる．
これに より，VSOP に よるデータベース解析の際に ，非頻出アイテムの 削除が非常に 大きな 影 響を与えると いうこと がわかった．特に ，パタン頻度表を生成する際に ZBDD がメモリ溢れを起こして ，頻度表を生成すること がで きな かった場合でも，非頻出アイテムの 削除を行うこと で ，現実的な 範囲で 有用な タプル頻度表を生成で きる場合がある．実際の データベース解析に おいて ，その 程度の 頻度を設定するかに よって ，ZBDD の データの 削減量が左右される．

4.2

人工的な 例題に おけるアイテム変数の 順序付けの 影 響

実験と 考察本 実 験 に お い て 使 用 し た PC は Pentium4，3.0GHz，SuSE Linux 9.3，主記憶 512Mbyte でZBDD の 最大節点数は 1,000 万個と した．

次に VSOP の アイテム変数の 順序付けの 効果に関して ，顕著な 効果が現れる場合を示す．以下に示すような データと アイテム変数の 順序付けを用表 1: 非頻出アイテムの 削除を行ったタプル頻度表の 生成
BMS-WebView-1
α #R00700 52.0
2,800 90.4
3,659 100size

BMS-WebView-2

count time(s)46,148 18,473
8,998 5,561
5216101

α #R

23.9
18.0
26.0
28.3

00
250 49.4
1,300 89.7
3,767 100count time(s)

α #R

pumsb
α #R

size

size

mushroom
size

count time(s)0513,762

5,574,930,438

303.5

3,600 48.8
7,900 87.2
8,125 100

7,915
19
7127,5168
1

43.5
35.1
35.0

α #R

size

BMS-WebView-1
00

count time(s)Memory Overflow

700 52.0 1,860,766 1,366,686,814,614,193

124.2

2,800 90.4

5416

28.8

3,659 100

10128.3

α #R

size

T10I4D100K
00

count time(s)Memory Overflow

1,900 50.1 2,560,170
4,400 90.3
2,759
7,829 100
10

15,144,453
2,845
1

748.7
193.9
187.0

いる．

a2 b2 a3 b3
a1 b1 a3 b3
a1 b1 a2 b2..
.
a1 b1 a2 b2

size

α #R

size

185.8
0051.7 3,600 48.8
61.2 7,900 87.2
66.7 8,125 100

8,006370
197

a4 b4 · · ·anbn
a4 b4 · · ·anbn
a4 b4 · · ·anbn..
..
.
.
a3 b3 · · · a(n − 1) b(n − 1)

順序付け 1: a1 b1 a2 b2 a3 b3 · · · an bn
順序付け 2: a1 a2 · · · an b1 b2 · · · bn

count time(s)
8,124
141
4
1

1.1
17.6
30.6
35.1

T10I4D100K

count time(s)162.8
00 1,324,502 48,474
331.9 21,000 49.5
27,867 10,856
620.4 36,000 89.6
114
39
673.7 38,750 10071

表 2: 非頻出アイテムの 削除を行ったパタン頻度表の 生成

0count time(s)198,471 48,684
60,520 24,4852,188 2,265
10
1
pumsb star

00 1,750,883 48,474
26,000 47.2
29,324 10,044
48,000 92.0
681448,945 100
7
1

α #R

mushroom

α #R

size

count time(s)118.900 552,429 89,135
238.1 1,900 50.1 151,202 78,855
414.5 4,400 90.3
2,074 1,908
457.4 7,829 100
10159.0
109.5
172.0
187.1

この データは ，各レコードに おいて ak bk (k =1, ..., n) が抜けて いるもの で ある．また，2 つの 順
序付けは ，1 つ目は データと 同じように ak と bk が隣り合うように ，2 つ目は ak と bk が離れるように な って いる．今回は n = 6 と n = 10 の 場合の 実
験結果を表 3，図 3 に 示す．
この 結果を見ると ，特に パタン頻度表に 関して ，2 つの 順序付けに よる ZBDD の データ構造の 大きさの 差が顕著で あること がわかる．1 つ目の 順序付けで は n に 比例して ，2 つ目の 順序付けで は nに 対して 指数関数的に 増えて いくもの と 予想で きる．つまり，1 つ目の 順序付けの 方がよいと いう傾向があると いうこと がわかった．また，タプル頻度表に 関して も同様な 簡単化効果が認められるが，パタン頻度表と は 違い ZBDD の サイズが指数関数的に 大きくな ること は な いの で ，差がそれほど 大
きな もの に は な らな かった．処理時間に 関して は ，今回用いたデータが小規模で あったの で 大きな 差は 生まれな かったが，大規模な データを扱ったと
きに は 同様に 指数関数的な 差が生じるの で ，膨大な 時間がかかって しまう場合がある．
この ように ，VSOP を用いて データベースの 頻度表を表す ZBDD を生成する際に ，アイテム変数の 順序付けが，最悪の 場合，指数関数的な 影 響を与えると いうこと が確認で きた．

4.3

ベンチマーク例題に おける順序付けの 影 響

最後に ，実際の トランザクションデータベースにおけるアイテム変数の 順序付けの 効果を計るために ，アイテムの 出現頻度の 降順と 昇順，また，データベースを読み込んで アイテムが初めて 現れた順に 関して ，生成される ZBDD の 大きさを比較する

(a) 順序付け 1(b) 順序付け 2n = 6 の 場合(a) 順序付け 1(b) 順序付け 2n = 10 の 場合

図 3: 人工的例題（ パタン頻度表） に おける順序付けの 効果

表 3: 人工的な 例題に おける頻度表作成結果
タプル頻度表nパタン頻度表

順序付け 1 順序付け 2 順序付け 1 順序付け 224477381016264121830755162853215

6204081531

72454

123

1,245

82870

165

2,826

93288

213

6,287

1036108261

13,747

1140

130

317

29,6171244154373

62,945

実験を行った．この と き，非頻出アイテムの 削除も同時に 行うこと で ，アイテムを削除すること でアイテム変数の 順序付けの 効果が変化するか実験した．結果を表 4 に 示す．ここで ，down は 降順，
up は 昇順，default は データベースを読み込んでアイテムが初めて 現れた順に アイテムを並べた場
合で ある．
この 実験結果からもわかるように ，それぞれのトランザクションデータベースに おけるアイテム
変数の 順序付けの 効果に 関して ，一様に 縮約効果が得られる順序付けは 得られな かった．今回は 単純な 順序付けで しか実験を行わな かったが，アイテム変数の 順序付けの 効果は データベースの 状態に 大きく左右されること が示された．

4.4

考察

以上の 実験結果を受けて ，よりよい ZBDD の 簡単化を実現するために ，LSI 論理設計分野の BDDの 変数順序づ け法と して 知られる深さ優先探索 [8]と 動的重みづ け法 [9] をこの データベース処理に 応用すること を考えて いる．深さ優先探索は ，論理式（ または 回路） の 出力側から深さ優先順に たど って いき，先に 到達した入力の 変数から上位に 並べると いうもの で ある．これに より，関連の 強いア表 4: ベンチマーク例題に おける順序付けの 効果
mushroom
タプル頻度表1,000down
2,358up default down1,717

パタン頻度表

3,000
3,765

428

1,000

up default
463

down

up

695 1,090,600

157,998

3,000
default

down

up default

376,465 38,346 19,239 34,854

T10I4D100K
tuple
1,800
down

up default down

pattern
4,300

1,800

up default

152,020 151,548 151,202 2,773 2,697

5.

down

2,717 3,566,721 2,662,778 3,020,963

3,918

おわりに

本稿で は ，データベース解析に おいて 生成される ZBDD の 簡単化に 関して 種々の 実験を行った．
その 結果，非頻出アイテムの 削除の 効果やアイテ
ム変数の 順序付けの 与える影 響に ついて 考察した．
さらに ，アイテム変数の 順序付けに より指数関数的な 効果が生じる典型的な 事例を初めて 示した．非頻出アイテムの 削除は ，ど の ような 場合に おいてもある程度の 縮約効果が得られるが，アイテム変数の 順序付けに 関して は ，顕著な 効果が得られる場合を示すこと は で きたもの の ，実際の データベー
スに おいて 一様に 縮約効果を得られる順序付けを見つけるの は 難しいと 思われる．しかし，ある種の 特別な 性質を持ったデータベースの 場合を考えれば ，よい順序付けを見つけること がで きるかもしれな い．今後も考察を続けて いく予定で ある．

参考文献[1] R. Agrawal, H. Mannila, R. Strikant, H. Toivonen and A. I.. Verkamo, Fast Discovery of Association Rules, In Advances in Knowledge Discovery and Data Mining, MIT Press, 307-328, 1996.

up

4,300
default

イテム変数が近くの 順位に な りやすくな る．
また，動的重みづ け法は 出力側から重みを入力側から伝えて いき，重みが最も大きい変数を最上位に する．そして ，その 変数に 関係する線を取り除き，再度重みを計算すると いうこと を繰り返すこと で ，アイテム変数の 順序付けを行う方法で ある．これに より，出力に 対して 強い制御力があり，その 前に 選択された変数と 関連の 強い変数が選ばれること と な る．
これらの 手法を，データベースの 特徴抽出に 応用して ZBDD の 順序付けを行う方法に ついて 現在研究を進めて いる．

downup default
3,890

3,918

[2] Bryant, R. E., Graph-based algorithms for
Boolean function manipulation, IEEE Trans.
Comput., C-35, 8 (1986), 677-691.
[3] J. Han, j. Pei, Y. Yin, R. Mao, Mining Frequent Patterns without Candidate Generation:
A Frequent-Pattern Tree Approach, Data Mining and Knowkedge Discovery, 8(1), 53-87, 2004.
[4] Minato, S., Zero-suppressed BDDs for set manipulation in combinatorial problems, In Proc. 30th
ACM/IEEE Design Automation Conf. (DAC93), (1993), 272-277.
[5] 湊真一, VSOP: ゼロサプレス型 BDD に 基づ く「 重み付き積和集合」 計算プログラム, IEICE Technical Report COMP2005-13(2005-5)[6] 湊真一, 有村博紀, ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの 効率的解析手法, 電子情報通信学会論文誌, Vol.J89-D,
No2, pp．172-182, 2006.
[7] M. J. Zaki, Scalable Algorithms for Association
Mining, IEEE Trans. Knowl. Data Eng. 12(2),372-390, 2000.
[8] M. Fujita, H. Fujisawa and N. Kawato. Evaluation and improvement of Boolean comparison
method based on binary decision diagrams. InProc. of IEEE/ACM International Conference on
Computer-Aided Design (ICCAD-88), pp. 2-5,
Novenber 1988.
[9] S. Minato, N. Ishiura and S. Yajima. Shared binary decision diagram with attributed edges for
efficient Boolean function manipulation. In Proc.
of 27th ACM/IEEE Design Automation Conference (DAC’90), pp. 52-57, June 1990.