A Method of ZBDD Variable Ordering for Frequent Pattern Mining

Authors: Haruya Iwasaki, Shin-ichi Minato, and Thomas Zeugmann

Source: The IEICE Transactions on Information and Systems (Japanese Edition) (電子情報通信学会論文誌) Vol. J91-D, No. 3, 2008, 608 - 618.

Abstract. Recently, an efficient method of database analysis using Zero-suppressed Binary Decision Diagrams (ZBDDs) has been proposed. BDDs are a graph-based representation of Boolean functions, now widely used in system design and verification. 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 the variable ordering used. In this paper, we propose a new method of ZBDD variable ordering for itemset mining of large-scale transaction databases, and show experimental results.

あらまし 近年，ゼロサプレス型二分決定グラフ(ZBDD: Zero-suppressed Binary Decision Diagrams)を 用いたデータベースの効果的な解析手法が提案されている．二分決定グラフ (BDD)は大規模論理関数データの 表現方法として広く用いられている．今回はトランザクションデータベースに 関して，大規模なアイテムの 組合せ集合を処理するのに適したZBDDを用いる．ZBDDのデータ構造は変数の順 序に大きく影響を受ける． 我々は，ZBDDを生成する前処理としてアイテム変数の順序付けを行うことで， 生成されるZBDDのサイズを 小さくする研究を行ってきた．本稿では，VLSI設計の分野で開発された「動的 重み付け法」をトランザクションデータベースの 変数順序付けに応用する手法を提案する．動的重み付け法は，トランザクショ ンデータベースの構造情報を用いることで， よりよい順序付けを行う手法である．我々は，様々なトランザクションデータ ベースに対してこの手法を適用してZBDDを生成する 実験を行うことで，この手法の有効性を確認することができた．さらに，動的 重み付けを行うプログラムを改良し高速化を行った．