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

二进制决策图（bdd）是在主存上表示布尔函数的有效数据结构。自20世纪90年代以来，BDD操纵技术在超大规模集成电路逻辑设计领域得到了发展。最近，我们发现基于bdd的技术也可以有效地应用于数据挖掘和知识发现问题。特别是，作为bdd的一种，Zero-suppressed bdd非常适合处理现实数据库分析中经常出现的稀疏组合集。在本研究中，我们开发了高效的基于zbdd的大规模数据库分析技术，如下所示。(1)提出了一种快速生成大规模全/闭/最大频繁项集的算法“LCM over zbdd”。该算法是基于目前提出的最有效的最先进的算法之一。它不仅枚举/列出项目集，而且还在主内存上生成一个紧凑的输出数据结构。(2)提出了一种利用“协因子隐含”的特性发现大规模事务数据库中隐藏信息的新方法。协因子隐含是“对称项集”的泛化，在超大规模集成电路CAD领域是众所周知的。提出了一种高效的带协因式的非平凡项对提取算法。(3)提出了用符号表达式表示组合项集的VSOP程序。基于ZBDD技术，VSOP可以高效地处理包含多个项目符号的大规模乘积和表达式。VSOP不仅支持布尔集合运算，还支持基于“值积和”代数的数值算术运算，如加、减、乘、除、数值比较等。VSOP将促进各种数据库分析问题的研究和开发。

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.