Abstract
Manipulation of large-scale combinatorial data is one of the important fundamental technique for web information retrieval, integration, and mining. Recently, we proposed a new approach based on Zero-suppressed BDDs (Binary Decision Diagrams) for efficient database analysis. In this paper, we present VSOP program developed for calculating combinatorial item sets 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Imielinski, T., Swami, A.N.: Mining Association rules between sets of items in large databases. In: Buneman, P., Jajodia, S. (eds.) Proc. of the 1993 ACM SIGMOD International Conference on Management of Data. SIGMOD Record, vol. 22(2), pp. 207–216. ACM Press, New York (1993)
Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35(8), 677–691 (1986)
Goethals, B.: Survey on Frequent Pattern Mining (Pdf) Manuscript (2003), http://www.adrem.ua.ac.be/~goethals/publications/survey.ps
Goethals, B., Javeed Zaki, M. (eds.): Frequent Itemset Mining Dataset Repository, Frequent Itemset Mining Implementations (FIMI 2003) (2003), http://fimi.cs.helsinki.fi/data/
Han, J., Pei, J., Yin, Y., Mao, R.: Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach. Data Mining and Knowledge Discovery 8(1), 53–87 (2004)
Minato, S.: Zero-suppressed BDDs for set manipulation in combinatorial problems. In: Proc. 30th ACM/IEEE Design Automation Conf. (DAC-1993), pp. 272–277 (1993)
Minato, S.: Binary Decision Diagrams and Applications for VLSI CAD. Kluwer Academic Publishers, Dordrecht (1996)
Minato, S.: Zero-suppressed BDDs and Their Applications. International Journal on Software Tools for Technology Transfer (STTT) 3(2), 156–170 (2001)
Minato, S., Arimura, H.: Efficient Method of Combinatorial Item Set Analysis Based on Zero-Suppressed BDDs. In: Proc. of IEEE International Workshop on Challenges in Web Information Retrieval and Integration (WIRI-2005), April 2005, pp. 4–11 (2005)
Minato, S.: VSOP (Valued-Sum-Of-Products) Calculator Based on Zero-Suppressed BDDs, TCS Technical Report Series A of Division of Computer Science, Hokkaido Univ., TCS-TR-A-05-3 (May 2005), http://www-alg.ist.hokudai.ac.jp/tra.html
Minato, S.-i.: VSOP (Valued-Sum-of-Products) Calculator for Knowledge Processing Based on Zero-Suppressed BDDs. In: Jantke, K.P., Lunzer, A., Spyratos, N., Tanaka, Y. (eds.) Federation over the Web. LNCS (LNAI), vol. 3847, pp. 40–58. Springer, Heidelberg (2006)
Baeza-Yates, R., Ribiero-Neto, B.: Modern Information Retrieval. Addison-Wesley, Reading (1999)
Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM Monographs on Discrete Mathematics and Applications 4 (2000)
Zaki, M.J.: Scalable Algorithms for Association Mining. IEEE Trans. Knowl. Data Eng. 12(2), 372–390 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Minato, Si. (2006). Efficient Database Analysis Using VSOP Calculator Based on Zero-Suppressed BDDs. In: Washio, T., Sakurai, A., Nakajima, K., Takeda, H., Tojo, S., Yokoo, M. (eds) New Frontiers in Artificial Intelligence. JSAI 2005. Lecture Notes in Computer Science(), vol 4012. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11780496_20
Download citation
DOI: https://doi.org/10.1007/11780496_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35470-3
Online ISBN: 978-3-540-35471-0
eBook Packages: Computer ScienceComputer Science (R0)