DEIM Forum 2013 F10-2

ゼロサプレス型二分決定木を用いた集合間類似結合
白井康之†,††

高嶋宏之†

鶴間 浩二†††

小山聡††† JST-ERATO 湊離散構造処理系プロジェクト 〒 060-0814 札幌市北区北 14 条西 9 丁目††† 日本電気 (株) 〒 211-8666 川崎市中原区下沼部 1753†† 北海道大学大学院情報科学研究科 〒 060-0814 札幌市北区北 14 条西 9 丁目
E-mail: †{shirai,takashima}@erato.ist.hokudai.ac.jp, ††k-tsuruma@ak.jp.nec.com,†††oyama@ist.hokudai.ac.jp
あらまし

近年，データベース分野やデータマイニング分野において，集合間類似結合 (Set Similarity Joins) に関する研究が注目を集めており，購買履歴からの類似データ抽出や文字列照合等への応用が期待されている．集合間類
似結合の方法論としては，データエントリに着目したフィルタリング手法に基づくものが多いが，本稿では，疎な大規模データ集合を効率的に表現する手法であるゼロサプレス型二分決定木 (ZDD : Zero-suppressed Binary Decision

Diagrams) を用いた手法を提案する．ZDD を用いて表現されたアイテム集合間の類似結合アルゴリズムを示すとともに，他の手法との比較結果や実データを用いた実験結果を示す．
キーワード

集合間類似結合, 情報推薦, ゼロサプレス型二分決定木

Similarity Joins on Item Set Collections Using Zero-Suppressed Binary
Decision Diagrams
Yasuyuki SHIRAI†,†† , Hiroyuki TAKASHIMA† , Koji TSURUMA††† , and Satoshi OYAMA††† JST-ERATO Minato Discrete Structure Manipulation System Project††† NEC Corporation†† Graduate School of Information Science and Technology, Hokkaido University
E-mail: †{shirai,takashima}@erato.ist.hokudai.ac.jp, ††k-tsuruma@ak.jp.nec.com,†††oyama@ist.hokudai.ac.jp
Abstract In this paper, we propose a new approach to similarity joins based on Zero-suppressed Binary Decision
Diagrams (ZDDs) for general item set collections, such as purchase history data, research keyword data, and soon. ZDDs are special types of Binary Decision Diagrams (BDDs), and suitable for implicitly handling large-scale
combinatorial item set data. We show, in this paper, the algorithms for similarity joins between two data collections
represented as ZDDs and the experimental results for performance comparison with other systems and the results
using real huge data collections.
Key words similarity joins, recommendation, zero-suppressed binary decision diagram

1. は じ め に

数は膨大になることから，いかに効率的に与えられた条件を満たすペアを発見できるかが課題となっている．こうした集合間

近年，データベース分野や自然言語処理分野，あるいはデー

類似結合は，実データベースにおいて幅広い応用分野を持ってタマイニング分野において，アイテム集合を要素とする異なるいる．たとえば，特許検索，データクリーニング，類似研究の集合（トランザクションデータベース）間での類似結合 (Set

発見，不正検知（Fraud detection），誤り検出，優良（不良）Similarity Joins) 手法が注目を集めている [1], [2], [4], [6], [13]〜顧客の発見などへの応用が期待されている．

[15], [17]〜[19]．集合間類似結合は，余弦や Jaccard 係数，編集合間で類似したトランザクションを正確にすべて列挙する

集距離といった尺度に基づき，2 つの大規模なトランザクショ

問題は，集合間の組み合わせ処理を必然的に内包するため，よンデータベースから類似したトランザクションのペアを正確にり効率的なマッチングアルゴリズムが求められる．本稿では，すべて抽出・列挙する手法であり，一般に要素間の組み合わせ

購買履歴データや研究キーワードといったトランザクション

データベースに対する類似結合に対して，ゼロサプレス型二な追加アイテム数と削除アイテム数に関する制約を扱うものと分決定木 (Zero-suppressed Binary Decision Diagrams，以下する．編集距離はシーケンスデータを対象とした場合には，編ZDD) [8], [10], [12] を用いた効率的な実装方式を提案する．ZDD

集コストという観点から有意性を持っているが，一方，購買履

は Bryant による二分決定木（Binary Decision Diagrams，以歴データ等の順序のないデータセットにおいては，アイテム集

下 BDD）[3] の変種であるが，大規模な組み合わせデータ集合

合間の相違をより細かいレベルで指定可能な追加アイテム数なに対してより圧縮効果の高いデータ構造である．

らびに削除アイテム数に関する制約を与える方が適していると

本稿の構成は以下のとおりである．2. 章では，関連する既存研究を概観し，3. 章で，基本的定義ならびに ZDD を用いた類似結合アルゴリズムを示す．4. 章では，実行効率評価として，考えられる．

3. ZDD を用いた集合間類似結合

トライ構造を用いた実装 [6], [17] との比較結果を示す．また，5.

本研究では，トライ構造ではなく，ゼロサプレス型 BDD

章では，DBLP や NSF の実データを用いた解析結果を紹介す（ZDD) [8], [10], [12] を用いたアルゴリズムを提案する．ZDD

る．6. 章では，本稿のまとめと今後の課題を示す．

は部分構造を共有することにより，疎なデータ構造をコンパク

2. 関 連 研 究
類似ペアをすべて正確に列挙する集合間類似結合に関して，近トに表現することが可能な無閉路有向グラフ（DAG）である．
本章では，基本的定義ならびに本論文で扱う類似結合について説明し，ZDD を用いた類似結合手法について記す．

年，さまざまな取り組みが報告されている [1], [2], [4], [6], [13]〜3. 1 準[15], [17]〜[19]．

以下，いくつかの用語と記法を定義する．

Chaudhuri と Arasu ら [1], [4] は，SSJoin と呼ばれる一般的備

定義 1 [アイテム] : アイテムは，小文字 a, b, c, . . . などを使っな演算を導入し，編集距離や Jaccard 係数，ハミング距離等さて表わす．また，アイテムとして使用する文字集合を Σ で表

まざまな尺度へ拡張可能な集合間類似結合技術を提案している．

わす．

SSJoin を用いた PartEnum や WtEnum といったアルゴリ
ズムは，データの分割とシグネチャの生成・比較といった処理に基づき，効率的なフィルタリングを行う手法である．

Bayardo ら [2] は，与えられた閾値以下の関連度を持つトラ
ンザクションの組み合わせを効率的に除外するフィルタリング手法を示した．彼らの提案する All-Pairs アルゴリズムは，大規模なレコードサイズに対してもスケーラブルであることが示されている．

定義 2 [トランザクション] : アイテムの集合をトランザクショ
ンと呼ぶ．すなわち，トランザクションはアルファベットの集合で表わされる（以下，D で表わす）．また，トランザクショ
ンの集合をトランザクションデータベースと呼び，S あるいはT などの記号を用いて表わす．
トランザクションデータベースを単に “データベース” と呼ぶこともある．

Xiao [18] らは，ミスマッチの個数に着目した Ed-Join アル
ゴリズムを示し，効率的な候補の絞り込み手法を提案している．
これらのアプローチは，いずれも不要なマッチングを可能な限り回避するためのフィルタリング手法である．すなわち，条件を満たさないペアを早期に枝狩りし，可能性のあるペアについては，テストフェーズとして検証が行われる．

定義 3 [追加・削除制約] :トランザクションに追加または削除するアイテム数の上限をそれぞれ N + , N − で表わす．
たとえば，以下のようなトランザクションデータベース S ，T があったとする：

こうした枝狩り手法は，アルファベットの個数やレコード長S = {{a, b}, {a, c}, {c}}(1)に対して，一般にセンシティブであり，うまくパラメータを設

T = {{a, d}, {a, b, c}, {b}}(2)定できる問題に対しては有効であるものの，例えば，比較的長= N− = 1 に お け る T の S

さの短いストリングに対しては，オーバーヘッドとなることもこ の と き ，条 件 N +指摘されている [6], [17]．

に対する類似結合は以下の 6 つのペアから構成さ

以上のようなフィルタリング手法に対して，Feng，Wang
ら [6], [17] はトライ構造を用いて，Trie-Join と呼ばれる探索手法と枝狩り手法を提案している．また，Trie-Join を改良した
より効率的なアルゴリズムも提案されている [7]．
本稿では，Trie-Join [6], [17] 同様に，フィルタリング手法ではなく，データの表現方法とこれに基づく類似データの探索手法を検討するものとする．ただし，Trie-Join では，文字列等れる :{{a, b}, {a, d}}, {{a, c}, {a, d}}, {{a, b}, {a, b, c}},{{a, c}, {a, b, c}}, {{a, b}, {b}}, {{c}, {b}}．
もしここで条件が N + = 1, N − = 0 であったとすると，{{a, b}, {b}} のみが条件を満たすペアである．
3. 2 ゼロサプレス型 BDD (ZDD)
本節では，二分決定グラフ（BDD）ならびにゼロサプレス型
二分決定グラフ（ZDD）について概説する．

の系列シーケンスを対象としているのに対し，本稿では，アイ

BDD [3], [8] は，大規模なブール関数を効率的に表現する無テム集合（以下，トランザクション）を扱うものとする．また，

閉路有向グラフである．縮約ルールは，ノード削除ルール（2Trie-Join では，編集距離を制約としているが，本稿では，順

つのエッジがともに同じノードを指しているようなノードを冗序のないトランザクションに対してより詳細な条件を指定可能

長なものとして削除する）ならびにノード共有ルール（等価なサブグラフを共有する）からなる．一方，ZDD [8], [10], [12] は，同様に，ボックス (2) は (1) の結果に基づき生成される．ボッ大規模な組み合わせアイテム集合を効率的に取り扱うことがでクス (4) を生成するためには，(2) の結果と同様に，(3) の結果

きるように改良された BDD の変種である．ZDD の縮約ルーも必要である．我々のアルゴリズムでは，各ノードに対する探ルは，BDD のそれとは若干異なっている．

索プロセスは，すべての親エッジが処理されたのちに起動する．

•

等価なノードを共有する（BDD と同様）．(図 1 の (1)).

ボックス (3) の計算後，ボックス (2)(3) の結果に基づき，ボッ•1-edge が直接 0-ターミナルノードを指しているようなクス (4) が生成される．

ノードを削除し，0-edge の到達先に直接接続させる．(図 1 のS において，d を追加するボックス (6) については，親である (4) と (5) におけるすべての追加カウントに 1 を追加しなけ(2)).
図 1 は，3. 1 で示した S に対する ZDD の縮約例である．

ればならない．なぜなら，T のトランザクションはいずれも d

ZDD は，BDD と比較して，購買履歴データなどのような疎をその要素として持たないからである．

なデータ構造に対してより効率的であることが知られている．

結果として，(6) のカウントは制約 N + を満たさない．もし

たとえば，1000 アイテムから 10 アイテムを選択するようなボックスのすべての要素が条件 N + もしくは N − を満たさな組み合わせ集合の表現においては，ZDD は BDD と比較して，い場合には，その枝上の探索プロセスは停止する．このため，100 倍程度簡潔に表現できる例もある．

ボックス (6) は φ となり，以降の探索は枝狩りされる．



D




⁊

E



E









F

F

F

F

I

 

 















%LQDU\'HFLVLRQ7UHH

Algorithm 1 ZDD 構造上の探索アルゴリズム

D

⁊

J

I

n0 is a top node of the ZDD S;





E


J



 











⁊


search zdd(n0 );


F

⁊





I




I

=''5HGXFWLRQ5XOHV

n0 .cand = {{+0 − 0 : 0}};

function search zdd(n)=''5HSUHVHQWDWLRQ

if all of other ancestors of node n have not been processed
then returnend if

図 1 ZDD による二分決定木の縮約

if n is a terminal node then return cand;// output candidates

3. 3 ZDD に基づく類似結合

else

我々の手法においては，まず与えられた 2 つのトランザク

n1 = n.edge1 .dest; // n1 : destination of 1 edge of n

ションデータベースは，ZDD パッケージ [11] を介して，ZDD

n0 = n.edge0 .dest; // n0 : destination of 0 edge of n構造に変換される．我々のシステムにおける入力データは，変n1 .cand = update candidate(n.edge1 , n.cand, n1 .cand);

換された ZDD 構造ならびに制約記述である．以下では，2 つの ZDD 構造に対する集合間類似結合方法について述べる．

ZDD 構造上での探索アルゴリズムの概要をアルゴリズム 1

n0 .cand = update candidate(n.edge0 , n.cand, n0 .cand);// update candidates for edge 1 and 0
n1 .cand = reduce(n1 .cand);n0 .cand = reduce(n0 .cand);に示す．図 2 は ZDD を用いた類似結合の例である．この図で// reduction of the candidate set

は，N + = N − = 1 の制約のもとで S (左) と T (右) において// and check the constraints

類似したトランザクションを見つけることを目的としている．

if n1 .cand is not NULL then return search zdd(n1 );探索プロセスは，トップノードである S 上の a より開始される（アルゴリズム 1 における search zdd(n)）. 各エッジ上のボックスは，探索結果，すなわち T 上のパス（枝の系列）と，それに対応するアイテム追加数と削除数からなるリストである．

end if
if n0 .cand is not NULL then return search zdd(n0 );end ifend ifend function

たとえば，S 上のボックス (1) は，a の否定を表わすエッジにつけられている．ボックス (1) の +0 − 1 : 2 は，現状の制約がT 上のエッジ 2 に対して，“追加アイテムなし (+0) かつ 削除
アイテム数 1 (−1)” であることを表わしている．同様に，ボックス (1) の +0 − 0 : 1 は T 上のエッジ 1 に対して，“追加アイテムなし (+0) かつ 削除アイテムなし (−0) ” であることを表わしている．
ア ル ゴ リ ズ ム 中 の update candidate は 現 状 の 候 補 集 合

図 2 で示した例では，制約を満たす解は存在しないが，図 3で示した例では，2 つの結果，すなわち，{a, d} ({a, c, d} から

c を削除) ならびに {b, c, d, e} ({b, c, d} への e の追加) を得る．
以下，本節で示した ZDD に基づく集合間類似結合を ZDD-

Join と呼ぶ．ZDD-Join は，既存の ZDD パッケージを利用して ZDD データ構造を構築し，それらをもとにした類似結合アルゴリズムを C++ により実装したものである．

n1 .cand と n0 .cand に対して，新しい候補を追加するものである．また，reduce は候補集合を縮約し，制約検査を行う
ものである．

4. Trie-Join との比較評価
既に述べたように，Trie-Join [6], [17] は，順序づけられたス6 ^^DEFGH`^EFGH`
^DFGH`^DEGH``
+

7 ^^DH`^EH`^FH``

N = 1, N - = 1  



E





F




F



G



図2





F

G

G







H

H





ZDD を用いた集合類似検索の例 (1)7 ^^DFG`^EFG``

N + = 1, N - = 1




D





D



E

E




F

F
G

H

H

E

^DFG`^F`

図3





F



















E





G






E

F



G

6 ^^DEFGH`^DG`^EFGH``






̪

  



G






E

F

̪

  

D





E

  




D



G
H





^EFG`^H`

ZDD を用いた集合類似検索の例 (2)トリングデータを対象としているが，本論文のアプローチと目

SUSE Linux Enterprise Server 11 上で，32 Intel Xeon CPUs

的ならびに手法が類似している．対象とするデータ構造や制約(2.66 GHz) ならびに 1.024 TB RAM を用いて実行したものの与え方が異なっているため，精緻な比較は困難であるが，本である．

節では，人工的なデータを利用した比較実験結果について記す

また，図 4 は，表 2 に示した結果の中からいくつかをプロッこととする．本実験で使用したデータは以下のとおりである :トしたものであり．ここで，横軸は出力された結果数を表わし，•トランザクションは，Trie-Join においてはアルファベッ

ト順（“a”–“z”）に生成され，ZDD-Join においても同様に“x01”–“x26” を対応させて生成する．
•

各トランザクションに含まれるアイテム個数（トランザ

縦軸は実行時間（単位：秒）を表わす．
表からみられるように，より大規模な問題に対しては，少な
くとも Trie-Join と同等のパフォーマンスを持っていることがわかる．たとえば，1,000,000 トランザクションで編集距離がクションの長さ）は 10 とする．ただし，重複が発生した場合

2 の制約の場合には，Trie-Join の実行時間は，約 149 百万個には，これを削除するものとする．

の結果に対して，436.6 (秒) を要している．一方，ZDD-Join

表 1 に，Trie-Join との比較実験で使用したデータの例を表においては，同じく 1,000,000 トランザクションを対象とし，

N + = N − = 2 の条件のもとでは，約 809 百万個の結果に対しわす．
表 1 比較実験に使用したデータ例
Trie-Join input
aegklorstw
bcegjmtvxyﬁlmrsux
dijkmqrt
aeinprst
kqrvwyaefghlqvx
acgknoruxy

ZDD-Join input
x01 x05 x07 x11 x12 x15 x18 x19 x20 x23x02 x03 x05 x07 x10 x13 x20 x22 x24 x25
x06 x09 x12 x13 x18 x19 x21 x24x04 x09 x10 x11 x13 x17 x18 x20x01 x05 x09 x14 x16 x18 x19 x20x11 x17 x18 x22 x23 x25x01 x05 x06 x07 x08 x12 x17 x22 x24x01 x03 x07 x11 x14 x15 x18 x21 x24 x25て，1039.0 (58.5 + 980.5) (秒) を要している．N + = N − = 2の条件は，編集距離 2 の条件と比較して明らかに緩く（実際，ZDD-Join の結果は Trie-Join の結果の真部分集合となっている），出力される結果数は Trie-Join の場合と比較しておよそ5 倍となっている．
以上のように，2 つのシステムは，データセットに関する異なる前提を置いているうえ，制約の与え方も異なっているために，精緻な比較は困難であるが，生成される解の個数（すなわ

データは 100000，500000，1000000 トランザクションからち問題のサイズ）と計算時間の関係をみる限り，少なくとも同なる 3 セットを用意した．Trie-Join （注 1） ならびに ZDD-Join

等レベルのパフォーマンスを達成できていると考えられる．

による実行結果を表 2 に示す．なお，以降の実験は，いずれも

5. 応 用 実 験（注 1）：Trie-Join プログラムは以下にあるものを使用した．

http://dbgroup.cs.tsinghua.edu.cn/wangjn/codes/triejoin.tar.gz

本章では，DBLP の論文タイトルや NSF の研究概要データ

表 2 ZDD-Join と Trie-Join との実行比較
ZDD-JoinSize of DB1

Size of DB2

Search Condition

Num. of Results

Exec.Time(sec)ZDD Setting

100,000

100,000

500,000

500,000

1,000,000

1,000,000

Size of DB1

Size of DB2

100,000

100,000

500,000

500,000

1,000,000

1,000,000

add <= 1,delete <
= 0
add <
= 0,delete <= 1<<
add = 1,delete = 1<<
add = 2,delete = 0
add <= 0,delete <
= 2
add <
= 2,delete <= 1<<
add = 1,delete = 2<<
add = 2,delete = 2
add <
= 0
= 1,delete <add <= 0,delete <= 1<<
add = 1,delete = 1<<
add = 2,delete = 0
add <= 0,delete <
= 2
add <
= 2,delete <
= 1
<
add <
1,delete
=
= 2
<
add <
2,delete
=
= 2
add <
= 1,delete <
= 0
add <
= 0,delete <
= 1
add <
= 1,delete <
= 1
add <
= 2,delete <
= 0
add <
= 0,delete <
= 2
add <
= 2,delete <
= 1
add <
= 1,delete <
= 2
add <
= 2,delete <= 216,624
16,664
244,675
68,53068,775
1,293,882
1,295,137
8,713,274
401,823
405,813
5,922,847
1,649,671
1,681,117
31,163,852
31,554,584
210,967,890
1,532,292
1,563,436
22,695,485
6,312,234
6,524,292
119,123,804
121,636,513
809,214,292

5.4

27.9

58.5

Search
1.8
1.6
4.8
3.1
2.5
11.1
10.7
37.2
12.6
10.2
31.5
19.2
16.4
84.4
86.1
368.7
27.6
23.1
67.7
40.0
36.2
210.6
208.0
980.5

(Z1-1)(Z1-2)(Z1-3)(Z1-4)(Z1-5)(Z1-6)(Z1-7)(Z1-8)(Z2-1)(Z2-2)(Z2-3)(Z2-4)(Z2-5)(Z2-6)(Z2-7)(Z2-8)(Z3-1)(Z3-2)(Z3-3)(Z3-4)(Z3-5)(Z3-6)(Z3-7)(Z3-8)

Trie-Join
Search Condition

Num. of Results

edit distance=1
edit distance=2
edit distance=1
edit distance=2
edit distance=1
edit distance=2

Exec.Time(sec)

78,315
1,746,849
1,827,303
40,789,678
6,701,562
149,904,112

1.1
19.8
8.2
159.1
23.1
436.6

(T1-1)(T1-2)(T2-1)(T2-2)(T3-1)(T3-2)

500
450

Execution Time (sec)

400
350
300

ZDD-Join
250

Trie-Join
200
150
100
50
0
0

50000000

100000000

150000000

200000000

Number of Results
図 4 ZDD-Join と Trie-Join のパフォーマンス比較•

DS 2 (1998 年〜2007 年, 348882 トランザクション),

5. 1 DBLP 論文タイトル•

DS 3 (2008 年以降, 355992 トランザクション)

ここでは，DBLP に含まれる論文タイトルを対象とする

ここで各トランザクションのアイテムは，出現するキーワー（DBLP のデータは，http://dblp.uni-trier.de/xml で xml

ドを表わすものとする．ただし，本実験では，頻度が 10 未満形式で公開されており，このうち，“article” または “inproceed-のキーワードを削除した．

を用いたいくつかの実験結果を示す．

ings” のタグがついた 863,580 件のデータを対象とする）．
データセットから，発行年（publish year）を抽出し，発行
年に応じてデータセットを以下のように三分割する．

•

DS 1 (1997 年以前, 158706 トランザクション),

表 3 は，実験結果として，DS1 と DS2，また，DS2 と DS3の類似結合の結果を記したものである．たとえば，1-a と 1-bは互いに類似であるとして検出されたものであり，1-a の発行
年は 1987 年，また，1-b の発行年は 2001 年である（また互いに異なる著者による）．しかしながら，前者の論文は実数列用することは自然であり，かつ効率上の利点も大きい．

に対する計算複雑性を扱っているのに対して，後者はバイナリ

今後の課題は以下のとおりである．

シーケンスに対する記述計算量を扱ったものであるため，この•他の手法で取り込まれている枝狩り手法やフィルタリン

場合の直接的な関連は高くはない．一方，6-a，6-b は，ともにグ方法 [1], [2] あるいは Trie-Join におけるいくつかの枝狩り手

極大平面グラフの検出方法に関する論文であり，後者から前者

法 [6], [17] （長さによる枝狩りや，単一枝による枝狩りなど）への論文中での直接的な参照はないものの，相互に関連の深いは，本アプローチでも取り入れることが可能である．

研究であると考えられる．

•

現実的な応用を考えた場合には，編集可能なアイテムや以上のように，実応用を考えた場合には，単にタイトルだけ

本質的なアイテムなど，アイテムに関する特徴付けが必須であでなく，アブストラクトを含めた特徴付けが必要であるが，集り，こうした特徴付けに基づいたアイテムの置き替え（追加ま合間の類似結合により，関連の高い研究論文を検出することがたは削除）が必要である．これらの拡張は，実応用においては可能であると考えられる．

非常に有益であると考えられる．

5. 2 NSF 研究概要•

ZDD はアイテムの集合を扱うことができるが，順序付

次に 1990〜2003 年までの NSF 研究概要データを用いた実けられたストリングを扱うことができない．一方，Sequence験結果を記す．データベースは，合計で 129,000 エントリ (タBDD [5], [9] は系列集合を扱うように拡張された無閉路有向グ

イトル，期間，予算，概要，分野コード, . . .) からなり，タイラフである．文字列照合への応用として，Sequence BDD をトル，概要に含まれる単語の頻度データもともに提供されていベースにしたアルゴリズムを検討中である．

る．（注 2）
実験では，“1996 年未満” と “1996 年以降” にデータを分割した．また，本実験では，“computer” を概要に含むエントリーを対象とした．各トランザクションは，タイトルまたは概要に出現するキーワードから構成されている．
実験結果の一部を表 4 に示す．ここで，N + = 3, N − = 3 である．実験結果より，先に示した DBLP での結果同様，関連する過去の研究アクティビティが抽出されていることがわかる．
たとえば，1-a (1992) は並列アルゴリズムに関する基本的技術に関する研究ミーティングであるが，一方，1-b (1999) は，並
列計算の応用，すなわち，流体力学での並列計算に関するワー
クショップである．
一般に，プロジェクトの遂行やマネジメント，あるいはプロジェクト評価といった局面において，過去の類似したプロジェ
クトの成果を参考にすることは有意義であり，本実験のように膨大な過去データの中から類似したペアを検出することは応用面においても有用性が高いと考えられる．

6. まとめと今後の課題
本稿では，集合間類似結合に対して，疎なデータ集合に対す
る効率的な表現方法ならびに演算手法を提供するゼロサプレス
型 BDD（ZDD）を用いた新しい方法論を提案した．
また，集合間類似結合において効率的な実装として知られている Trie-Join との比較結果を示し，ZDD を用いた方法がTrie-Join による方法と少なくとも同等程度であることを示した．特に，アイテム数が限定されたデータにおいては，重複する部分構造を如何に効率的に管理できるかが鍵である．また，

Trie-Join においても，共有すべき部分構造へのリンクを貼る
ことにより，実質的に ZDD と同様なデータ管理を行っている．
その意味においても，集合間類似検索において ZDD 構造を利

（注 2）：本データセットは，UCI Machine Learning Repository において公開されているものである．
（NSF Research Award Abstracts in UCI Machine

Learning Repository : http://archive.ics.uci.edu/ml/datasets.html）

文

献[1] A. Arasu, V. Ganti, R. Kaushik : Eﬃcient Exact SetSimilarity Joins, In Proc. of 32nd International Conference
on Very Large Data Bases (VLDB 2006), 2006
[2] R. J. Bayardo, Y. Ma, R. Srikant : Scaling Up All Pairs
Similarity Search, In Proc. of 16th international conferenceon World Wide Web, 2007
[3] R. E. Bryant : Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, Vol.
35 Issue 8, 1986
[4] S. Chaudhuri, V. Ganti, R. Kaushik : A Primitive Operator for Similarity Joins in Data Cleaning, In Proc. of 22ndInternational Conference on Data Engineering (ICDE ’06),
2006[5] S. Denzumi, R. Yoshinaka, S. Minato, H. Arimura : Efﬁcient Algorithms on Sequence Binary Decision Diagramsfor Manipulating Sets of Strings, Hokkaido University, TCS
Technical Reports, TCS-TR-A-11-53, 2011[6] J. Feng, J. Wang, G. Li : Trie-join: a trie-based method
for eﬃcient string similarity joins, The VLDB Journal
21:437.461, 2012
[7] K. Gouda, M. Rashad : PreJoin: An Eﬃcient Trie-based
String Similarity Join Algorithm, The 8th International
Conf. on Informatics and Systems (INFOS), 2012[8] D. E. Knuth : The Art of Computer Programming, Vol.
4, No.1, Bitwise Tricks & Techniques, pp.117-126, AddisonWesley, 2009[9] E. Loekito, J. Bailey, J. Pei : A Binary decision diagram
based approach for mining frequent subsequences, Knowledge and Information Systems, 24(2), 2010[10] S. Minato : Zero-Suppressed BDDs for Set Manipulationin Combinatorial Problems, In Proc. of 30th ACM/IEEE
Design Automation Conference (DAC’93), 1993.
[11] S. Minato : VSOP (Valued-Sum-of-Products) Calculator
for Knowledge Processing Based on Zero-Suppressed BDDs,
Federation over the Web, LNAI 3847, 2006.
[12] S. Minato : Implicit Manipulation of Polynomials Using
Zero-Suppressed BDDs, In Proc. of IEEE The European
Design and Test Conference, 1995.
[13] M. Neuhaus, H. Bunke : An Error-tolerant Approximate
Matching Algorithm for Attributed Planar Graphs and its
Application to Fingerprint Classiﬁcation, In Proc. of Joint
IAPR International Workshops, SSPR 2004 and SPR 2004,
2004[14] K. Oﬂazer : Error-tolerant Finite-state Recognition with

表 3 DBLP データベースに対する実験結果
Experiments for articles on DBLP (1) (-1997 : 1998-2007)
Num.
1-a
1-b
2-a
2-b
3-a
3-b
4-a
4-b
5-a
5-b
6-a
6-b

Year
1987
2001
1982
2004
1979
2005
1993
2006
1989
2006
1981
2004

Title
On The Complexity of Computable Real Sequences.
Descriptive complexity of computable sequences
Approximations for the waiting time distribution of the M/G/c queue.
Mean Waiting Time Approximations in the G/G/1 Queue.
On the connectivity of cayley graphs.
Parameters of connectivity in (a, b)-linear graphs.
An Aﬃnity-Based Dynamic Load Balancing Protocol for Distributed Transaction Processing Systems.
Dynamic Load Balancing Protocol for Locally Distributed Systems.
Eﬃcient monotone circuits for threshold functions.
Monotone circuits for monotone weighted threshold functions.
The reconstruction of maximal planar graphs. I. Recognition.
A simple recognition of maximal planar graphs.

Num.
1-a
1-b
2-a
2-b
3-a
3-b
4-a
4-b
5-a
5-b
6-a
6-b

Year
2005
2008
2006
2008
2006
2011
2006
2008
2005
2009
2006
2008

Num.

Year

1-a

1992

Design of Parallel Algorithms• support for postdoctoral associate,• experimental computer science• developed for idealized parallel computers on real parallel computers,• load balancing techniques

1-b

1999

WORKSHOP: Parallel CFD’99 International Conference• computational ﬂuid dynamics research on parallel computers,• parallel software system,• case studies from ﬂuid dynamics,• early experiences on teraﬂops-class computers

2-a

1993

Constructing, Maintaining, and Searching Geometric Structures• construction and maintenance of geometric structures,• eﬃciently searching in such structures,• computational geometry unsolved problems,• dynamic maintenance of geometric structures,• computer graphics and computer vision,• sequential and parallel computation models

2-b

1999

Towards Simpler Algorithms in Computational Geometry• design and analysis of algorithms for large amounts of geometric data,• eﬃcient algorithms for fundamental problems in computational geometry,• computer graphics and computer vision,• geometric optimization,• construction of basic geometric structures,• randomization, approximation, and techniques for correcting pessimistic worst-case analyses

3-a

1991

Undergraduate Computer Integrated Design Laboratory• establishment of an undergraduate computer integrated design laboratory,• development of a uniﬁed education program,• computer graphic simulation that gives insight into complex phenomena

3-b

1998

The Development of a Communication Networks Laboratory at Queens College• computer communication networks laboratory,• design and implementation of the Token Ring and Ethernet Local Area Networks,• undergraduate laboratory and an associated laboratory manual

Experiments for articles on DBLP (2) (1998-2007 : 2008-)
Title
k-Center problems with minimum coverage.
Asymmetric k-center with minimum coverage.
On complexity of multistage stochastic programs.
On Stability of Multistage Stochastic Programs.
A remote laboratory for electrical engineering education.
Developing a remote laboratory for engineering education.
Arboricity and tree-packing in locally ﬁnite graphs.
Locally ﬁnite graphs and embeddings.
Transforming semantics by abstract interpretation.
Abstract interpretation of resolution-based semantics.
PolicyUpdater: a system for dynamic access control.
A privacy-aware access control system.

表 4 NSF データベースに対する実験結果

[15]

[16]

[17]

[18]

Title and Abstract

Applications to Morphological Analysis and Spelling Correction, Computational Linguistics, 22(1), 1996
K. Oﬂazer : Error-tolerant Tree Matching, In Proc. of 16th
conference on Computational Linguistics (COLING ’96),
1996
Y. Shirai, K. Tsuruma, Y. Sakurai, S. Oyama, S. Minato: Incremental Set Recommendation Based on Class Diﬀerences, In Proc. of 16th Paciﬁc-Asia Conference on Knowledge Discovery and Data Mining, LNAI 7301, 2012
J. Wang, J. Feng, G. Li : Trie-Join: Eﬃcient Trie-based
String Similarity Joins with EditDistance Constraints, In
Proc. of the VLDB Endowment, 3(1-2), 2010
C. Xiao, W. Wang, X. Lin : Ed-join: an eﬃcient algorithm
for similarity joins with edit distance constraints, In Proc.

of VLDB Endowment, 1(1), 2008[19] C. Xiao, W. Wang, X. Lin, J. X. Yu : Eﬃcient Similarity
Joins for Near Duplicate Detection, In Proc. of 17th International Conference on World Wide Web, 2008