Abstract
Zero-suppressed decision diagrams (ZDDs) are a data structure for representing combinations over item sets. They have been applied to many areas such as data mining. When ZDDs represent large-scale sparse datasets, they tend to obtain an unbalanced form, which results performance degradation. In this paper, we propose a new data structure three-way indexing ZDD, as a variant of ZDDs. We furthermore present algorithms to convert between three-way indexing ZDDs and ordinary ZDDs. Experimental results show the effectiveness of our data structure and algorithms.
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
Similar content being viewed by others
Notes
- 1.
A frequent itemset with support threshold \(n\) is an itemset \(X\) such that the number of rows containing all items in \(X\) is more than or equal to \(n\). A frequent itemset is maximal if it is not contained in any other frequent itemset with the same support threshold.
References
Goethals, B.: Survey on frequent pattern mining. Technical report (2002)
Minato, S.: Zero-suppressed BDDs for set manipulation in combinatorial problems. In: DAC ’93: Proceedings of the 30th International Design Automation Conference, pp. 272–277. ACM, New York (1993)
Minato, S., Uno, T., Arimura, H.: LCM over ZBDDs: fast generation of very large-scale frequent itemsets using a compact graph-based representation. In: Washio, T., Suzuki, E., Ting, K.M., Inokuchi, A. (eds.) PAKDD 2008. LNCS (LNAI), vol. 5012, pp. 234–246. Springer, Heidelberg (2008)
Minato, S.: A fast algorithm for cofactor implication checking and its application for knowledge discovery. In: Proceedings of IEEE 8th International Conference on Computer and Information Technology, July 2008, pp. 53–58 (2008)
Minato, S.: Finding simple disjoint decompositions in frequent itemset data using zero-suppressed BDDs. In: Proceedings of IEEE ICDM 2005 Workshop on Computational Intelligence in Data Mining, November 2005, pp. 3–11 (2005)
Minato, S., Ito, K.: Symmetric item set mining method using zero-suppressed BDDs and application to biological data. Trans. Jpn. Soc. Artif. Intell. 22(2), 156–164 (2007)
Coudert, O.: Solving graph optimization problems with ZBDDs. In: Proceedings of the 1997 European Conference on Design and Test, March 1997, pp. 224–228 (1997)
Loekito, E., Bailey, J.: Fast mining of high dimensional expressive contrast patterns using zero-suppressed binary decision diagrams. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 307–316. ACM (2006)
Minato, S.: Techniques of BDD/ZDD: brief history and recent activity. IEICE Trans. Inf. Syst. E96-D(7), 1419–1429 (2013)
Minato, S.-I.: Z-Skip-Links for fast traversal of ZDDs representing large-scale sparse datasets. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 731–742. Springer, Heidelberg (2013)
Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: Proceedings of 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’97), January 1997, pp. 360–369 (1997)
Knuth, D.E.: The Art of Computer Programming, vol. 4a. Addison-Wesley Professional, New Jersey (2011)
Bentley, J.L., Saxe, J.B.: Algorithms on vector sets. SIGACT News 11(2), 36–39 (1979)
Toda, T.: Fast compression of large-scale hypergraphs for solving combinatorial problems. In: Fürnkranz, J., Hüllermeier, E., Higuchi, T. (eds.) DS 2013. LNCS, vol. 8140, pp. 281–293. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Aoki, H., Toda, T., Minato, Si. (2014). Three-way Indexing ZDDs for Large-Scale Sparse Datasets. In: Peng, WC., et al. Trends and Applications in Knowledge Discovery and Data Mining. PAKDD 2014. Lecture Notes in Computer Science(), vol 8643. Springer, Cham. https://doi.org/10.1007/978-3-319-13186-3_41
Download citation
DOI: https://doi.org/10.1007/978-3-319-13186-3_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13185-6
Online ISBN: 978-3-319-13186-3
eBook Packages: Computer ScienceComputer Science (R0)