TCS-TR-A-04-1

Date: Wed Dec 8 21:12:47 2004

Title: Combinatorial Item Set Analysis Based on Zero-Suppressed BDDs

Authors: Shin-ichi Minato and Hiroki Arimura

Contact:

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

Abstract. Manipulation of large-scale combinatorial data is one of the important fundamental technique for web information retrieval, integration, and mining. In this paper, we propose a new approach based on BDDs (Binary Decision Diagrams) for database analysis problems. BDDs are graph-based representation of Boolean functions, now widely used in system design and verification area. Here we focus on Zero-suppressed BDDs (ZBDDs), a special type of BDDs, which are suitable for handling large-scale sets of combinations. Using ZBDDs, we can implicitly enumerate combinatorial item set data and efficiently compute set operations over the ZBDDs. We present some encouraging experimental results of frequent item set mining problem for practical benchmark examples, some of which have never been generated by previous method.