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を生成する 実験を行うことで,この手法の有効性を確認することができた.さらに,動的 重み付けを行うプログラムを改良し高速化を行った.

©Copyright 2008, 電子情報通信学会
Valid HTML 4.1