TCS-TR-A-06-14

Date: Thu May 25 15:47:39 2006

Title: Symmetric Item Set Mining Using Zero-suppressed BDDs

Authors: Shin-ichi Minato

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. In this paper, we propose a method for discovering hidden information from large-scale item set data based on the symmetry of items. Symmetry is a fundamental concept in the theory of Boolean functions, and there have been developed fast symmetry checking methods based on BDDs (Binary Decision Diagrams). Here we discuss the property of symmetric items in data mining problems, and describe an efficient algorithm based on ZBDDs (Zero-suppressed BDDs). The experimental results show that our ZBDD-based symmetry checking method is efficiently applicable to the practical size of benchmark databases.