LIPIcs.SEA.2020.6.pdf
- Filesize: 0.64 MB
- 13 pages
Document
Storing Set Families More Compactly with Top ZDDs
Authors
Shuhei Denzumi 
,
Kunihiko Sadakane
-
Part of:
Volume:
18th International Symposium on Experimental Algorithms (SEA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Experimental Algorithms (SEA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-12
File
Document Identifiers
Author Details
- Graduate School of Information Science and Technology, The University of Tokyo, Japan
Cite AsGet BibTex
Kotaro Matsuda, Shuhei Denzumi, and Kunihiko Sadakane. Storing Set Families More Compactly with Top ZDDs. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SEA.2020.6
https://doi.org/10.4230/LIPIcs.SEA.2020.6
Abstract
Zero-suppressed Binary Decision Diagrams (ZDDs) are data structures for representing set families in a compressed form. With ZDDs, many valuable operations on set families can be done in time polynomial in ZDD size. In some cases, however, the size of ZDDs for representing large set families becomes too huge to store them in the main memory.
This paper proposes top ZDD, a novel representation of ZDDs which uses less space than existing ones. The top ZDD is an extension of top tree, which compresses trees, to compress directed acyclic graphs by sharing identical subgraphs. We prove that navigational operations on ZDDs can be done in time poly-logarithmic in ZDD size, and show that there exist set families for which the size of the top ZDD is exponentially smaller than that of the ZDD. We also show experimentally that our top ZDDs have smaller size than ZDDs for real data.
Subject Classification
ACM Subject Classification
- Theory of computation → Data structures design and analysis
Keywords
- top tree
- Zero-suppressed Decision Diagram
- space-efficient data structure
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Stephen Alstrup, Jacom Holm, Kristian de Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Transactions on Algorithms, 1(2):243-264, 2005. URL: https://doi.org/10.1145/1103963.1103966.
- Philip Bille, Inge Li Gørtz, Gad M.Landau, and Oren Weimann. Tree compression with top trees. Information and Computation, 243:166-177, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.012.
- Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 35:677-691, 1986. URL: https://doi.org/10.1109/TC.1986.1676819.
- Peter Buneman, Martin Grohe, and Christoph Koch. Path queries on compressed XML. In Proceedings of the 29th International Conference on Very Large Data Bases, pages 141-152. Morgan Kaufmann, 2003. URL: https://doi.org/10.1016/B978-012722442-8/50021-5.
- Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin ichi Minato, and Kunihiko Sadakane. Densezdd: A compact and fast index for families of sets. In Proceedings of the 13th International Symposium on Experimental Algorithms, pages 187-–198. Springer Verlag, 2014. URL: https://doi.org/10.1007/978-3-319-07959-2_16.
- Peter J. Downey, Ravi Sethi, and Robert Endre Tarjan. Variations on the common subexpression problem. Journal of ACM, 27(4):758–771, 1980. URL: https://doi.org/10.1145/322217.322228.
- Markus Frick, Martin Grohe, and Christoph Koch. Query evaluation on compressed trees. In Proceedings of 18th Annual IEEE Symposium of Logic in Computer Science, LICS 2003, pages 188-197. IEEE Computer Society, 2003. URL: https://doi.org/10.1109/LICS.2003.1210058.
- Roberto Grossi and Jeffrey Scott Vitter. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM Journal on Computing, 35(2):378–407, 2005. URL: https://doi.org/10.1137/S0097539702402354.
- Kotaro Matsuda, Shuhei Denzumi, and Kunihiko Sadakane. Storing set families more compactly with top zdds, 2020. URL: http://arxiv.org/abs/2004.04586.
- Shin-ichi Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of the 30th International Design Automation Conference, pages 272-277. ACM, 1993. URL: https://doi.org/10.1145/157485.164890.
- Shin-ichi Minato, Nagisa Ishiura, and Shuzo Yajima. Shared binary decision diagram with attributed edges for efficient boolean function manipulation. In Proceedings of the 27th ACM/IEEE Design Automation Conference, pages 52-57, 1990. URL: https://doi.org/10.1145/123186.123225.
- Gonzalo Navarro and Kunihiko Sadakane. Fully functional static and dynamic succinct trees. ACM Transactions on Algorithms, 10(3), 2014. URL: https://doi.org/10.1145/2601073.
- Daisuke Okanohara and Kunihiko Sadakane. Practical entropy-compressed rank/select dictionary. In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments, 2007. URL: https://doi.org/10.1137/1.9781611972870.6.
- Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms, 3(4):43–es, 2007. URL: https://doi.org/10.1145/1290672.1290680.