TCS-TR-B-10-7Date: Fri Jul 2 10:13:06 2010 Title: Recent and Future Work on Decision Diagrams and Discrete Structure Manipulation Authors: Shin-ichi Minato Contact:
Abstract. Binary Decision Diagram (BDD) is an efficient data structure for representing Boolean functions. Techniques of BDD manipulation have been developed in the area of VLSI logic design since 1990's. We found that BDD-based techniques can also be applied effectively to problems of data mining and knowledge discovery. Especially, Zero-suppressed BDDs (ZDDs), a type of BDDs, are suitable for handling sets of sparse combinations that often appear in many problems of database analysis. Recently, we have been working on ZDD-based large-scale data processing for such applications. In most of our research work, we can observe that discrete structure manipulation is a key technique to solve many kinds of real-life problems. In this article, we discuss the basic techniques of discrete structure manipulation using BDDs, ZDDs, and more extended decision diagrams. We also show some interesting applications of those decision diagram-based techniques. Finally we present a plan of our new research project on discrete structure manipulation systems. ©Copyright 2010 Authors |