{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:16:44Z","timestamp":1760203004658,"version":"3.41.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JSPS KAKENHI","award":["17J07555, JP18F18120"],"award-info":[{"award-number":["17J07555, JP18F18120"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2020,12,6]]},"abstract":"<jats:p>\n            A keyword dictionary is an associative array whose keys are strings. Recent applications handling massive keyword dictionaries in main memory have a need for a space-efficient implementation. When limited to static applications, there are a number of highly compressed keyword dictionaries based on the advancements of practical succinct data structures. However, as most succinct data structures are only efficient in the static case, it is still difficult to implement a keyword dictionary that is\n            <jats:italic>space efficient<\/jats:italic>\n            and\n            <jats:italic>dynamic<\/jats:italic>\n            . In this article, we propose such a keyword dictionary. Our main idea is to embrace the path decomposition technique, which was proposed for constructing cache-friendly tries. To store the path-decomposed trie in small memory, we design data structures based on recent compact hash trie representations. Experiments on real-world datasets reveal that our dynamic keyword dictionary needs up to 68% less space than the existing smallest ones, while achieving a relevant space-time tradeoff.\n          <\/jats:p>","DOI":"10.1145\/3418033","type":"journal-article","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T11:13:41Z","timestamp":1601464421000},"page":"1-28","source":"Crossref","is-referenced-by-count":5,"title":["Dynamic Path-decomposed Tries"],"prefix":"10.1145","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5462-122X","authenticated-orcid":false,"given":"Shunsuke","family":"Kanda","sequence":"first","affiliation":[{"name":"RIKEN Center for Advanced Intelligence Project, Chuo-ku, Tokyo, Japan"}]},{"given":"Dominik","family":"K\u00f6ppl","sequence":"additional","affiliation":[{"name":"Kyushu University and Japan Society for Promotion of Science"}]},{"given":"Yasuo","family":"Tabei","sequence":"additional","affiliation":[{"name":"RIKEN Center for Advanced Intelligence Project, Chuo-ku, Tokyo, Japan"}]},{"given":"Kazuhiro","family":"Morita","sequence":"additional","affiliation":[{"name":"Tokushima University, Minamijyousanjima-cho, Tokushima, Japan"}]},{"given":"Masao","family":"Fuketa","sequence":"additional","affiliation":[{"name":"Tokushima University, Minamijyousanjima-cho, Tokushima, Japan"}]}],"member":"320","published-online":{"date-parts":[[2020,9,30]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.31365"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67428-5_4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9969-x"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0348-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0183-9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_11"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67428-5_5"},{"edition":"2","volume-title":"Modern Information Retrieval","author":"Baeza-Yates Ricardo","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","unstructured":"Doug Baskins. 2002. A 10-minute Description of How Judy Arrays Work and Why They Are So Fast. Retrieved from http:\/\/judy.sourceforge.net\/doc\/10minutes.htm.  Doug Baskins. 2002. A 10-minute Description of How Judy Arrays Work and Why They Are So Fast. Retrieved from http:\/\/judy.sourceforge.net\/doc\/10minutes.htm."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16321-0_15"},{"volume-title":"Bentley and Robert Sedgewick","year":"1997","author":"Jon","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_2_1_15_1","unstructured":"Brazil Inc.2019. Groonga: An Open-Source Fulltext Search Engine and Column Store. Retrieved from http:\/\/groonga.org\/.  Brazil Inc.2019. Groonga: An Open-Source Fulltext Search Engine and Column Store. Retrieved from http:\/\/groonga.org\/."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.149"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676499"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380230305"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/364520.364540"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376943"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67428-5_16"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/367390.367400"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_28"},{"volume-title":"Poster Proceedings of the 4th Workshop on Experimental and Efficient Algorithms (WEA\u201905)","year":"2005","author":"Gonz\u00e1lez Rodrigo","key":"e_1_2_1_24_1"},{"volume-title":"Sparsehash: C++ Associative Containers.","year":"2005","author":"Google Inc.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19929-0_19"},{"volume-title":"Sparsepp: A Fast, Memory Efficient Hash Map for C++.","year":"2016","author":"Gregory Popovitch","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_3"},{"key":"e_1_2_1_29_1","article-title":"Fast compressed tries through path decompositions","volume":"19","author":"Grossi Roberto","year":"2014","journal-title":"ACM J. Exp. Algor."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.06.005"},{"volume-title":"Information Retrieval: Computational and Theoretical Aspects","year":"1978","author":"Heaps Harold Stanley","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/506309.506312"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00063-3"},{"volume-title":"Proceedings of the 22nd International Conference on World Wide Web (WWW\u201913)","year":"2013","author":"Paul Hsu Bo-June","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9836-6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2516"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0999-8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67428-5_19"},{"edition":"2","volume-title":"The Art of Computer Programming, 3: Sorting and Searching","author":"Knuth Donald E.","key":"e_1_2_1_40_1"},{"volume-title":"Proceedings of the 18th International Symposium on Experimental Algorithms (SEA\u201920)","year":"2020","author":"K\u00f6ppl Dominik","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v008.i14"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.08.008"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18818-8_9"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-21568-2_17"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974768.9"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054118430025"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 16th International Symposium on Experimental Algorithms (SEA\u201917)","volume":"75","author":"Prezza Nicola","year":"2017"},{"volume-title":"Proceedings of the 14th ACM International Conference on Object Oriented Programming Systems Languages 8 Applications (OOPSLA\u201914)","author":"Steele Guy L.","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44543-4_17"},{"volume-title":"Hopscotch-map: C++ Implementation of a Fast Hash Map and Hash Set Using Hopscotch Hashing.","year":"2016","key":"e_1_2_1_52_1"},{"volume-title":"Array-hash: C++ Implementation of a Fast and Memory Efficient Hash Map and Hash Set Specialized for Strings.","year":"2017","key":"e_1_2_1_53_1"},{"volume-title":"Hat-trie: C++ Implementation of a Fast and Memory Efficient HAT-trie.","year":"2017","key":"e_1_2_1_54_1"},{"volume-title":"Robin-map: C++ Implementation of a Fast Hash Map and Hash Set Using Robin Hood Hashing.","year":"2017","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC47342.2020.00032"},{"key":"e_1_2_1_57_1","first-page":"85","article-title":"A parallel distributed Web crawler consisting of producer-consumer modules","volume":"6","author":"Ueda Takanori","year":"2013","journal-title":"IPSJ Trans. Datab."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1984.1659158"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.3.193"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568014"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25073-6_49"},{"volume-title":"Proceedings of the 24th International Conference on Computational Linguistics (COLING\u201914)","year":"2014","author":"Yoshinaga Naoki","key":"e_1_2_1_62_1"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418033","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3418033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:35Z","timestamp":1750195895000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,30]]},"references-count":60,"alternative-id":["10.1145\/3418033"],"URL":"https:\/\/doi.org\/10.1145\/3418033","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2020,9,30]]}}}