Research for Efficient Algorithms of Large-Scale Database Analysis Based on Binary Decision Diagrams

点击翻译按钮获取中文摘要

Binary Decision Diagrams (BDDs) are the efficient data structure for representing Boolean functions on the main memory. The techniques of BDD manipulation have been developed in the area of VLSI logic design since 1990's. Recently, we found that the BDD-based techniques can also be applied effectively to the problems of data mining and knowledge discovery. Especially, Zero-suppressed BDDs, a type of BDDs, are suitable for handling sets of sparse combinations that often appear in the real-life database analysis. In this research, we have developed efficient ZBDD-based techniques for large-scale database analysis, as follows.(1) We proposed a fast algorithm for generating very large-scale all/closed/maximal frequent itemsets, "LCM over ZBDDs." This algorithm is based on one of the most efficient state-of-the-art algorithms proposed thus far. Not only does it enumerate/list the itemsets, but it also generates a compact output data structure on the main memory.(2) We proposed a new method for discovering hidden information from large-scale transaction databases by considering a property of "cofactor implication." Cofactor implication is a generalization of "symmetric itemsets," which is well-known in VLSI CAD area. We developed an efficient algorithm of extracting all non-trivial item pairs with cofactor implication.(3) We presented VSOP program developed for calculating combinatorial itemsets specified by symbolic expressions. Based on ZBDD techniques, VSOP can efficiently handle large-scale sum-of-products expressions with a number of item symbols. VSOP supports not only Boolean set operations but also numerical arithmetic operations based on "Valued-Sum-Of-Products" algebra, such as addition, subtraction, multiplication, division, numerical comparison, etc. VSOP will facilitate research and development for various database analysis problems.