TCS-TR-B-08-3

Date: Sat Mar 22 06:45:05 2008

Title: Master Thesis: Studies on Variable Ordering of Zero-suppressed Binary Decision Diagrams for Database Analysis (in Japanese)

Authors: Haruya Iwasaki

Contact:

First name: Haruya
Last name: Iwasaki
Address: Division of Computer Science, Hokkaido University, North 14, West 9, Sapporo 060-0814, Japan
Email: iwsk@ist.hokudai.ac.jp

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. Moreover, we consider the effieciency of this new method by comparing with frequency-based methods.