{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:02:59Z","timestamp":1760241779045,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2018,8,17]],"date-time":"2018-08-17T00:00:00Z","timestamp":1534464000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["25-193700"],"award-info":[{"award-number":["25-193700"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a11080128","type":"journal-article","created":{"date-parts":[[2018,8,17]],"date-time":"2018-08-17T10:54:25Z","timestamp":1534503265000},"page":"128","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["DenseZDD: A Compact and Fast Index for Families of Sets \u2020"],"prefix":"10.3390","volume":"11","author":[{"given":"Shuhei","family":"Denzumi","sequence":"first","affiliation":[{"name":"Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8654, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Kawahara","sequence":"additional","affiliation":[{"name":"Graduate School of Science and Technology, Nara Institute of Science and Technology, Ikoma 630-0192, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Koji","family":"Tsuda","sequence":"additional","affiliation":[{"name":"Department of Computational Biology and Medical Sciences, Graduate School of Frontier Sciences, The University of Tokyo, Tokyo 113-8654, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroki","family":"Arimura","sequence":"additional","affiliation":[{"name":"Graduate School of IST, Hokkaido University, Sapporo 060-0808, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shin-ichi","family":"Minato","sequence":"additional","affiliation":[{"name":"Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[{"name":"Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8654, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,8,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","article-title":"Graph-Based Algorithms for Boolean Function Manipulation","volume":"100","author":"Bryant","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"ref_2","unstructured":"Minato, S. (2016, January 12\u201317). Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA."},{"key":"ref_3","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 Advances in Knowledge Discovery and Data Mining (PAKDD), Osaka, Japan."},{"key":"ref_4","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 (KDID 2006), Berlin, Germany."},{"key":"ref_5","unstructured":"Knuth, D.E. (2009). The Art of Computer Programming, Fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams, Addison-Wesley."},{"key":"ref_6","unstructured":"Minato, S. (2012). SAPPORO BDD Package, Division of Computer Science, Hokkaido University. unreleased."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Denzumi, S., Kawahara, J., Tsuda, K., Arimura, H., Minato, S., and Sadakane, K. (July, January 29). DenseZDD: A Compact and Fast Index for Families of Sets. Proceedings of the International Symposium on Experimental Algorithms 2014, Copenhagen, Denmark.","DOI":"10.1007\/978-3-319-07959-2_16"},{"key":"ref_8","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_9","doi-asserted-by":"crossref","first-page":"16","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_10","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_11","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.dam.2014.11.022","article-title":"Sequence binary decision diagram: Minimization, relationship to acyclic automata, and complexities of Boolean set operations","volume":"212","author":"Denzumi","year":"2016","journal-title":"Discret. Appl. Math."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Minato, S. (2013, January 2\u20134). Z-Skip-Links for Fast Traversal of ZDDs Representing Large-Scale Sparse Datasets. Proceedings of the European Symposium on Algorithms, Sophia Antipolis, France.","DOI":"10.1007\/978-3-642-40450-4_62"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.jda.2012.07.009","article-title":"ESP-index: A compressed index based on edit-sensitive parsing","volume":"18","author":"Maruyama","year":"2013","journal-title":"J. Discret. Algorithms"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Navarro, G. (2016). Compact Data Structures, Cambridge University Press.","DOI":"10.1017\/CBO9781316588284"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","article-title":"Universal codeword sets and representation of the integers","volume":"21","author":"Elias","year":"1975","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Okanohara, D., and Sadakane, K. (2007, January 6). Practical Entropy-Compressed Rank\/Select Dictionary. Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, LA, USA.","DOI":"10.1137\/1.9781611972870.6"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s10115-009-0252-9","article-title":"A binary decision diagram based approach for mining frequent subsequences","volume":"24","author":"Loekito","year":"2010","journal-title":"Knowl. Inf. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10009-014-0352-z","article-title":"Graphillion: Software library for very large sets of labeled graphs","volume":"18","author":"Inoue","year":"2016","journal-title":"Int. J. Softw. Tools Technol. Transf."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Bryant, R.E. (2018, January 14\u201321). Chain Reduction for Binary and Zero-Suppressed Decision Diagrams. Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, Thessaloniki, Greece.","DOI":"10.1007\/978-3-319-89960-2_5"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Nishino, M., Yasuda, N., Minato, S., and Nagata, M. (2016, January 12\u201317). Zero-suppressed Sentential Decision Diagrams. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA.","DOI":"10.1609\/aaai.v30i1.10114"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/8\/128\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:19:25Z","timestamp":1760195965000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/8\/128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,17]]},"references-count":20,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2018,8]]}},"alternative-id":["a11080128"],"URL":"https:\/\/doi.org\/10.3390\/a11080128","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,8,17]]}}}