Zero-suppressed BDDs and recent applications for data mining and knowledge discovery

Shin-ichi Minato, Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan

Abstract: Binary Decision Diagrams (BDDs) are an efficient data structure for representing Boolean functions.  Much research has been done on BDD manipulation in VLSI logic design since 1990's. After 2000's, we found that BDD-based techniques can also be applied effectively to data mining and knowledge discovery. Especially, Zero-suppressed BDDs (ZDDs) are suitable for handling sets of sparse combinations that often appear in many practical database analyses.  In this talk, we will show our recent activities in BDD-based knowledge discovery techniques. First, we describe the ``LCM over ZDDs'' algorithm, which achieves very fast frequent itemset mining. Then, we present some useful post-processing methods for analyzing the results of the frequent itemset mining.

About the speaker: Shin-ichi Minato is an Associate Professor of Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan. He also serves as Director of ERATO (Exploratory Research for Advanced Technology) MINATO Discrete Structure Manipulation System Project, executed by Japan Science and Technology Agency. His research topics include efficient representations and manipulation algorithms for large-scale discrete structure data. He received the B.E., M.E., and D.E. degrees in Information Science from Kyoto University in 1988, 1990, and 1995, respectively. He had been working in NTT Laboratories since 1990 until March 2004. He was a Visiting Scholar of Stanford University in 1997. He joined Hokkaido University in 2004. He started the ERATO Project from 2009. He published "Binary Decision Diagrams and Applications for VLSI CAD" (Kluwer,1995). His original data structure "ZDD" is minutely discussed in the Knuth's book "The Art of Computer Programming" (Vol. 4, Fascicle 1, 2009). Minato serves a TPC Sub-Topic Chair of ASPDAC 2008 to 2011. He is a member of IEEE-CAS, IEICE, IPSJ, and JSAI.

 

More info