{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:03:45Z","timestamp":1760234625295,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T00:00:00Z","timestamp":1622419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 the 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 sizes than ZDDs for real data.<\/jats:p>","DOI":"10.3390\/a14060172","type":"journal-article","created":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T21:42:06Z","timestamp":1622497326000},"page":"172","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Storing Set Families More Compactly with Top ZDDs"],"prefix":"10.3390","volume":"14","author":[{"given":"Kotaro","family":"Matsuda","sequence":"first","affiliation":[{"name":"Graduate School of Information Technology and Science, The University of Tokyo, Tokyo 158-8557, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0794-4157","authenticated-orcid":false,"given":"Shuhei","family":"Denzumi","sequence":"additional","affiliation":[{"name":"Graduate School of Information Technology and Science, The University of Tokyo, Tokyo 158-8557, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8212-3682","authenticated-orcid":false,"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[{"name":"Graduate School of Information Technology and Science, The University of Tokyo, Tokyo 158-8557, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Minato, S. (1993, January 14\u201318). Zero-suppressed BDDs for Set Manipulation in Combinatorial Problems. Proceedings of the 30th International Design Automation Conference, Dallas, TX, USA.","DOI":"10.1145\/157485.164890"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","article-title":"Graph-Based Algorithms for Boolean Function Manipulation","volume":"35","author":"Bryant","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"ref_3","unstructured":"Coudert, O. (1997, January 17\u201320). Solving Graph Optimization Problems with ZBDDs. Proceedings of the European Design and Test Conference, Paris, France."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0020-0190(98)00067-2","article-title":"On the properties of combination set operations","volume":"66","author":"Okuno","year":"1998","journal-title":"Inf. Process. Lett."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Loekito, E., and Bailey, J. (2006, January 20\u201323). Fast Mining of High Dimensional Expressive Contrast Patterns Using Zero-Suppressed Binary Decision Diagrams. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA.","DOI":"10.1145\/1150402.1150438"},{"key":"ref_6","unstructured":"Minato, S., and Arimura, H. (2006, January 18). Frequent Pattern Mining and Knowledge Indexing Based on Zero-Suppressed BDDs. Proceedings of the 5th International Workshop on Knowledge Discovery in Inductive Databases, Berlin, Germany."},{"key":"ref_7","unstructured":"Minato, S., Uno, T., and Arimura, H. (2008, January 20\u201323). LCM over ZBDDs: Fast Generation of Very Large-Scale Frequent Itemsets Using a Compact Graph-Based Representation. Proceedings of the 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Osaka, Japan."},{"key":"ref_8","unstructured":"Ishihata, M., Kameya, Y., Sato, T., and Minato, S. (2008, January 10\u201312). Propositionalizing the EM algorithm by BDDs. Proceedings of the 18th International Conference on Inductive Logic Programming, Prague, Czech Republic."},{"key":"ref_9","unstructured":"Minato, S., Satoh, K., and Sato, T. (2007, January 6\u201312). Compiling Bayesian Networks by Symbolic Probability Calculation Based on Zero-suppressed BDDs. Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Sakurai, Y., Ueda, S., Iwasaki, A., Minato, S., and Yokoo, M. (2011, January 16\u201318). A Compact Representation Scheme of Coalitional Games Based on Multi-Terminal Zero-Suppressed Binary Decision Diagrams. Proceedings of the 14th International Conference on Principles and Practice of Multi-Agent Systems, Wollongong, Australia.","DOI":"10.1007\/978-3-642-25044-6_4"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Denzumi, S., Kawahara, J., Tsuda, K., Arimura, H., Minato, S., and Sadakane, K. (2018). DenseZDD: A Compact and Fast Index for Families of Sets. Algorithms, 11.","DOI":"10.3390\/a11080128"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bille, P., G\u00f8rtz, I.L., M.Landau, G., and Weimann, O. (2013, January 8\u201312). Tree Compression with Top Trees. Proceedings of the Automata, Languages, and Programming&x2014;40th International Colloquium Part I, Riga, Latvia.","DOI":"10.1007\/978-3-642-39206-1_14"},{"key":"ref_13","unstructured":"Matsuda, K., Denzumi, S., and Sadakane, K. (2020, January 16\u201318). Storing Set Families More Compactly with Top ZDDs. Proceedings of the 18th International Symposium on Experimental Algorithms, Catania, Italy."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2601073","article-title":"Fully Functional Static and Dynamic Succinct Trees","volume":"10","author":"Navarro","year":"2014","journal-title":"ACM Trans. Algorithms"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1290672.1290680","article-title":"Succinct Indexable Dictionaries with Applications to Encoding K-Ary Trees, Prefix Sums and Multisets","volume":"3","author":"Raman","year":"2007","journal-title":"ACM Trans. Algorithms"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1137\/S0097539702402354","article-title":"Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching","volume":"35","author":"Grossi","year":"2005","journal-title":"SIAM J. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Minato, S., Ishiura, N., and Yajima, S. (1990, January 24\u201328). Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean function Manipulation. Proceedings of the 27th ACM\/IEEE Design Automation Conference, Orlando, FL, USA.","DOI":"10.1145\/123186.123225"},{"key":"ref_18","unstructured":"Buneman, P., Grohe, M., and Koch, C. (2003, January 9\u201312). Path Queries on Compressed XML. Proceedings of the 29th International Conference on Very Large Data Bases, Berlin, Germany."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1145\/322217.322228","article-title":"Variations on the Common Subexpression Problem","volume":"27","author":"Downey","year":"1980","journal-title":"J. ACM"},{"key":"ref_20","unstructured":"Frick, M., Grohe, M., and Koch, C. (2003, January 14\u201318). Query evaluation on compressed trees. Proceedings of the 18th Annual IEEE Symposium of Logic in Computer Science, Vienna, Austria."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/1103963.1103966","article-title":"Maintaining Information in Fully Dynamic Trees with Top Trees","volume":"1","author":"Alstrup","year":"2005","journal-title":"ACM Trans. Algorithms"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Okanohara, D., and Sadakane, K. (2007, January 6). Practical Entropy-Compressed Rank\/Select Dictionary. Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611972870.6"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1376","DOI":"10.1016\/j.egypro.2012.02.255","article-title":"A New Fault Diagnosis Method Based on Fault Tree and Bayesian Networks","volume":"17","year":"2012","journal-title":"Energy Procedia"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/172\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:09:29Z","timestamp":1760162969000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,31]]},"references-count":23,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["a14060172"],"URL":"https:\/\/doi.org\/10.3390\/a14060172","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,5,31]]}}}