{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:00:12Z","timestamp":1760148012541,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T00:00:00Z","timestamp":1679270400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Slovenian Research Agency","doi-asserted-by":"publisher","award":["P1-0383"],"award-info":[{"award-number":["P1-0383"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper proposes a new data structure, multiset-trie, that is designed for storing and efficiently processing a set of multisets. Moreover, multiset-trie can operate on a set of sets without efficiency loss. The multiset-trie structure is a search tree with properties similar to those of a trie. It implements all standard search tree operations together with the multiset containment operations for searching sub-multisets and super-multisets. Suppose that we have a set of multisets S and a multiset X. The multiset containment operations retrieve multisets from S that are either sub-multisets or super-multisets of X. We present the mathematical analysis of a multiset-trie that gives the time complexity of the algorithms and the space complexity of the data structure. Further, the empirical analysis of the data structure is implemented in a series of experiments. The experiments illuminate the time complexity space of the multiset containment operations.<\/jats:p>","DOI":"10.3390\/a16030170","type":"journal-article","created":{"date-parts":[[2023,3,21]],"date-time":"2023-03-21T02:36:22Z","timestamp":1679366182000},"page":"170","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Multiset-Trie Data Structure"],"prefix":"10.3390","volume":"16","author":[{"given":"Mikita","family":"Akulich","sequence":"first","affiliation":[{"name":"Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, 6000 Koper, Slovenia"}]},{"given":"Iztok","family":"Savnik","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, 6000 Koper, Slovenia"},{"name":"Faculty of Information Studies, 8000 Novo Mesto, Slovenia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4960-8901","authenticated-orcid":false,"given":"Matja\u017e","family":"Krnc","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, 6000 Koper, Slovenia"},{"name":"Faculty of Information Studies, 8000 Novo Mesto, Slovenia"},{"name":"Department of Mathematics, Faculty of Mathematics and Physics, University of Ljubljana, 1000 Ljubljana, Slovenia"}]},{"given":"Riste","family":"\u0160krekovski","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, 6000 Koper, Slovenia"},{"name":"Faculty of Information Studies, 8000 Novo Mesto, Slovenia"},{"name":"Department of Mathematics, Faculty of Mathematics and Physics, University of Ljubljana, 1000 Ljubljana, Slovenia"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,20]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Savnik, I., Akulich, M., Krnc, M., and \u0160krekovski, R. (2021). Data structure set-trie for storing and querying sets: Theoretical and empirical analysis. PLoS ONE, 2.","key":"ref_1","DOI":"10.1371\/journal.pone.0245122"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s10115-015-0895-7","article-title":"Set containment join revisited","volume":"49","author":"Bouros","year":"2016","journal-title":"Knowl. Inf. Syst."},{"doi-asserted-by":"crossref","unstructured":"Gripon, V., Rabbat, M., Skachek, V., and Gross, W.J. (2012, January 3\u20137). Compressing multisets using tries. Proceedings of the 2012 IEEE Information Theory Workshop, Lausanne, Switzerland.","key":"ref_3","DOI":"10.1109\/ITW.2012.6404756"},{"unstructured":"Ross, K.A., and Stoyanovich, J. (September, January 29). Symmetric relations and cardinality-bounded multisets in database systems. Proceedings of the Thirtieth International Conference on Very Large Data Bases, Volume 30, VLDB Endowment, Toronto, ON, Canada.","key":"ref_4"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1485","DOI":"10.1109\/TIT.2015.2392093","article-title":"Compressing sets and multisets of sequences","volume":"61","author":"Steinruecken","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"unstructured":"Zobel, J., Moffat, A., and Sacks-Davis, R. (1992, January 23\u201327). An efficient indexing technique for full-text database systems. Proceedings of the 18th Conference on Very Large Data Bases, Morgan Kaufmann, Vancouver, BC, Canada.","key":"ref_6"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/1132956.1132959","article-title":"Inverted files for text search engines","volume":"38","author":"Zobel","year":"2006","journal-title":"ACM Comput. Surv. (CSUR)"},{"doi-asserted-by":"crossref","unstructured":"Manning, C.D., Raghavan, P., and Sch\u00fctze, H. (2008). Introduction to Information Retrieval, Cambridge University Press.","key":"ref_8","DOI":"10.1017\/CBO9780511809071"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1023\/A:1009796218281","article-title":"Levelwise Search and Borders of Theories in Knowledge Discovery","volume":"1","author":"Mannila","year":"1997","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_10","first-page":"139","article-title":"Database Dependency Discovery: A Machine Learning Approach","volume":"12","author":"Flach","year":"1999","journal-title":"AI Commun."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0004-3702(82)90020-0","article-title":"Rete: A Fast Algorithm for the Many Pattern\/Many Object Pattern Match Problem","volume":"19","author":"Forgy","year":"1982","journal-title":"Artif. Intell."},{"doi-asserted-by":"crossref","unstructured":"Bayardo, R.J., Ma, Y., and Srikant, R. (2007, January 8\u201312). Scaling up All Pairs Similarity Search. Proceedings of the WWW\u201907: 16th International World Wide Web Conference, ACM, Banff, AB, Canada.","key":"ref_12","DOI":"10.1145\/1242572.1242591"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/2000824.2000825","article-title":"Efficient Similarity Joins for Near-Duplicate Detection","volume":"36","author":"Xiao","year":"2011","journal-title":"ACM Trans. Database Syst."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"925","DOI":"10.14778\/3099622.3099624","article-title":"Leveraging set relations in exact set similarity join","volume":"10","author":"Wang","year":"2017","journal-title":"Proc. VLDB Endow."},{"unstructured":"Cormen, T.H., Leiserson, C., Rivest, R.L., and Stein, C. (2001). Introduction to Algorithms, The MIT Press. [2nd ed.].","key":"ref_15"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1145\/296854.277632","article-title":"Inverted files versus signature files for text indexing","volume":"23","author":"Zobel","year":"1998","journal-title":"ACM Trans. Database Syst. (TODS)"},{"doi-asserted-by":"crossref","unstructured":"Broder, A.Z., Eiron, N., Fontoura, M., Herscovici, M., Lempel, R., McPherson, J., Qi, R., and Shekita, E. (2006, January 29). Indexing shared content in information retrieval systems. Proceedings of the International Conference on Extending Database Technology, Edinburgh, UK.","key":"ref_17","DOI":"10.1007\/11687238_21"},{"doi-asserted-by":"crossref","unstructured":"Terrovitis, M., Passas, S., Vassiliadis, P., and Sellis, T. (2006, January 6\u201311). A Combination of Trie-trees and Inverted Files for the Indexing of Set-valued Attributes. Proceedings of the 15th ACM International Conference on Information and Knowledge Management, Arlington, VA, USA.","key":"ref_18","DOI":"10.1145\/1183614.1183718"},{"doi-asserted-by":"crossref","unstructured":"Terrovitis, M., Bouros, P., Vassiliadis, P., Sellis, T., and Mamoulis, N. (2011, January 21). Efficient Answering of Set Containment Queries for Skewed Item Distributions. Proceedings of the 14th International Conference on Extending Database Technology, Uppsala, Sweden.","key":"ref_19","DOI":"10.1145\/1951365.1951394"},{"doi-asserted-by":"crossref","unstructured":"Deppisch, U. (1986, January 1). S-tree: A Dynamic Balanced Signature Index for Office Retrieval. Proceedings of the 9th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Pisa, Italy.","key":"ref_20","DOI":"10.1145\/253168.253189"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0306-4379(01)00047-3","article-title":"Signature-based Structures for Objects with Set-valued Attributes","volume":"27","author":"Tousidou","year":"2002","journal-title":"Inf. Syst."},{"unstructured":"Chen, Y., and Shi, Y. (2005). Encyclopedia of Database Technologies and Applications, IGI Global.","key":"ref_22"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1007\/s00778-003-0106-0","article-title":"A performance study of four index structures for set-valued attributes of low cardinality","volume":"12","author":"Helmer","year":"2003","journal-title":"VLDB J."},{"unstructured":"Savnik, I. (2022, January 23\u201326). Index data structure for fast subset and superset queries. Proceedings of the International Conference on Availability, Reliability, and Security, Vienna, Austria.","key":"ref_24"},{"unstructured":"Sedgewick, R., and Wayne, K. (2011). Algorithms, Addison-Wesley Professional. [4th ed.].","key":"ref_25"},{"unstructured":"Gardiner, C.W. (1985). Stochastic Methods, Springer.","key":"ref_26"},{"unstructured":"Akulich, M. (2023, March 10). Mstrie Repository. Available online: https:\/\/github.com\/nick-ak96\/mstrie.","key":"ref_27"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1145\/359007.359013","article-title":"Partial-match Retrieval Using Indexed Descriptor Files","volume":"23","author":"Pfaltz","year":"1980","journal-title":"Commun. ACM"},{"unstructured":"Zhang, C., Naughton, J., DeWitt, D., Luo, Q., Luo, Q., and Lohman, G. (2020, January 14\u201319). On Supporting Containment Queries in Relational Database Management Systems. Proceedings of the SIGMOD, Portland, OR, USA.","key":"ref_29"},{"unstructured":"Ramasamy, K., Patel, J.M., Naughton, J.F., and Kaushik, R. (2000, January 10\u201314). Set containment joins: The good, the bad and the ugly. Proceedings of the 26th VLDB Conference, Morgan Kaufmann, Cairo, Egypt.","key":"ref_30"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1145\/762471.762474","article-title":"Adaptive Algorithms for Set Containment Joins","volume":"28","author":"Melnik","year":"2003","journal-title":"ACM Trans. Database Syst."},{"doi-asserted-by":"crossref","unstructured":"Jampani, R., and Pudi, V. (2005, January 17\u201320). Using Prefix-Trees for Efficiently Computing Set Joins. Proceedings of the Database Systems for Advanced Applications, 10th International Conference, DASFAA 2005, Beijing, China.","key":"ref_32","DOI":"10.1007\/11408079_69"},{"doi-asserted-by":"crossref","unstructured":"Luo, Y., Fletcher, G.H.L., Hidders, J., and Bra, P.D. (2015, January 13\u201317). Efficient and scalable trie-based algorithms for computing set containment relations. Proceedings of the 31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, Republic of Korea.","key":"ref_33","DOI":"10.1109\/ICDE.2015.7113293"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/3\/170\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:59:44Z","timestamp":1760122784000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/3\/170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,20]]},"references-count":33,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["a16030170"],"URL":"https:\/\/doi.org\/10.3390\/a16030170","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2023,3,20]]}}}