DenseZDD: a compact and fast index for families of sets. (English) Zbl 1458.68045
Summary: In this article, we propose a succinct data structure of zero-suppressed binary decision diagrams (ZDDs). A ZDD represents sets of combinations efficiently and we can perform various set operations on the ZDD without explicitly extracting combinations. Thanks to these features, ZDDs have been applied to web information retrieval, information integration, and data mining. However, to support rich manipulation of sets of combinations and update ZDDs in the future, ZDDs need too much space, which means that there is still room to be compressed. The paper introduces a new succinct data structure, called DenseZDD, for further compressing a ZDD when we do not need to conduct set operations on the ZDD but want to examine whether a given set is included in the family represented by the ZDD, and count the number of elements in the family. We also propose a hybrid method, which combines DenseZDDs with ordinary ZDDs. By numerical experiments, we show that the sizes of our data structures are three times smaller than those of ordinary ZDDs, and membership operations and random sampling on DenseZDDs are about ten times and three times faster than those on ordinary ZDDs for some datasets, respectively.
MSC:
| 68P05 | Data structures |
References:
| [1] | Bryant, R.E.; Graph-Based Algorithms for Boolean Function Manipulation; IEEE Trans. Comput.: 1986; Volume 100 ,677-691. · Zbl 0593.94022 |
| [2] | Minato, S.; Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems; Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence: ; ,1058-1066. |
| [3] | Minato, S.; Uno, T.; Arimura, H.; LCM over ZBDDs: Fast Generation of Very Large-Scale Frequent Itemsets Using a Compact Graph-Based Representation; Proceedings of the Advances in Knowledge Discovery and Data Mining (PAKDD): ; ,234-246. |
| [4] | Minato, S.; Arimura, H.; Frequent Pattern Mining and Knowledge Indexing Based on Zero-Suppressed BDDs; Proceedings of the 5th International Workshop on Knowledge Discovery in Inductive Databases (KDID 2006): ; ,152-169. |
| [5] | Knuth, D.E.; ; The Art of Computer Programming, Fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams: Boston, MA, USA 2009; Volume Volume 4 . · Zbl 1178.68372 |
| [6] | Minato, S.; ; SAPPORO BDD Package: Sapporo, Japan 2012; . |
| [7] | Denzumi, S.; Kawahara, J.; Tsuda, K.; Arimura, H.; Minato, S.; Sadakane, K.; DenseZDD: A Compact and Fast Index for Families of Sets; Proceedings of the International Symposium on Experimental Algorithms 2014: ; . · Zbl 1458.68045 |
| [8] | Raman, R.; Raman, V.; Satti, S.R.; Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets; ACM Trans. Algorithms: 2007; Volume 3 ,43. · Zbl 1446.68046 |
| [9] | Navarro, G.; Sadakane, K.; Fully-Functional Static and Dynamic Succinct Trees; ACM Trans. Algorithms: 2014; Volume 10 ,16. · Zbl 1333.68084 |
| [10] | Minato, S.; Ishiura, N.; Yajima, S.; Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean function Manipulation; Proceedings of the 27th ACM/IEEE Design Automation Conference: ; ,52-57. |
| [11] | Denzumi, S.; Yoshinaka, R.; Arimura, H.; Minato, S.; Sequence binary decision diagram: Minimization, relationship to acyclic automata, and complexities of Boolean set operations; Discret. Appl. Math.: 2016; Volume 212 ,61-80. · Zbl 1350.68066 |
| [12] | Minato, S.; Z-Skip-Links for Fast Traversal of ZDDs Representing Large-Scale Sparse Datasets; Proceedings of the European Symposium on Algorithms: ; ,731-742. · Zbl 1394.68100 |
| [13] | Maruyama, S.; Nakahara, M.; Kishiue, N.; Sakamoto, H.; ESP-index: A compressed index based on edit-sensitive parsing; J. Discret. Algorithms: 2013; Volume 18 ,100-112. · Zbl 1268.68080 |
| [14] | Navarro, G.; ; Compact Data Structures: Cambridge, UK 2016; . |
| [15] | Elias, P.; Universal codeword sets and representation of the integers; IEEE Trans. Inf. Theory: 1975; Volume 21 ,194-203. · Zbl 0298.94011 |
| [16] | Okanohara, D.; Sadakane, K.; Practical Entropy-Compressed Rank/Select Dictionary; Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX): ; . · Zbl 1428.68134 |
| [17] | Loekito, E.; Bailey, J.; Pei, J.; A binary decision diagram based approach for mining frequent subsequences; Knowl. Inf. Syst.: 2010; Volume 24 ,235-268. |
| [18] | Inoue, T.; Iwashita, H.; Kawahara, J.; Minato, S.; Graphillion: Software library for very large sets of labeled graphs; Int. J. Softw. Tools Technol. Transf.: 2016; Volume 18 ,57-66. |
| [19] | Bryant, R.E.; Chain Reduction for Binary and Zero-Suppressed Decision Diagrams; Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems: ; ,81-98. · Zbl 1423.68119 |
| [20] | Nishino, M.; Yasuda, N.; Minato, S.; Nagata, M.; Zero-suppressed Sentential Decision Diagrams; Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence: ; ,272-277. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
