{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:01Z","timestamp":1760202661765,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2015,1,7]],"date-time":"2015-01-07T00:00:00Z","timestamp":1420588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2015,2,3]]},"abstract":"<jats:p>Tries are popular data structures for storing a set of strings, where common prefixes are represented by common root-to-node paths. More than 50 years of usage have produced many variants and implementations to overcome some of their limitations. We explore new succinct representations of path-decomposed tries and experimentally evaluate the corresponding reduction in space usage and memory latency, comparing with the state of the art. We study the following applications: compressed string dictionary and monotone minimal perfect hash for strings.<\/jats:p>\n          <jats:p>In compressed string dictionary, we obtain data structures that outperform other state-of-the-art compressed dictionaries in space efficiency while obtaining predictable query times that are competitive with data structures preferred by the practitioners. On real-world datasets, our compressed tries obtain the smallest space (except for one case) and have the fastest lookup times, whereas access times are within 20% slower than the best-known solutions.<\/jats:p>\n          <jats:p>In monotone minimal perfect hash for strings, our compressed tries perform several times faster than other trie-based monotone perfect hash functions while occupying nearly the same space. On real-world datasets, our tries are approximately 2 to 5 times faster than previous solutions, with a space occupancy less than 10% larger.<\/jats:p>","DOI":"10.1145\/2656332","type":"journal-article","created":{"date-parts":[[2014,10,21]],"date-time":"2014-10-21T12:36:57Z","timestamp":1413895017000},"source":"Crossref","is-referenced-by-count":19,"title":["Fast Compressed Tries through Path Decompositions"],"prefix":"10.1145","volume":"19","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Ottaviano","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1,7]]},"reference":[{"volume-title":"Algorithm Engineering and Experimentation","series-title":"Lecture Notes in Computer Science","author":"Acharya Anurag","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","unstructured":"AOL. 2006. AOL Search Data. Retrieved September 9 2014 from http:\/\/www.gregsadetsky.com\/aol-data\/.  AOL. 2006. AOL Search Data. Retrieved September 9 2014 from http:\/\/www.gregsadetsky.com\/aol-data\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972900.9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496856"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963190.2025378"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142385"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118737.3118845"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361192.1361194"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008623.2008637"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109621"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2010.45"},{"key":"e_1_2_1_13_1","unstructured":"David Richard Clark. 1998. Compact Pat Trees. Ph.D. Dissertation. University of Waterloo Waterloo Ontario Canada.  David Richard Clark. 1998. Compact Pat Trees. Ph.D. Dissertation. University of Waterloo Waterloo Ontario Canada."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1841909.1841913"},{"volume-title":"Proceedings of the 18th Annual International Conference on Computing and Combinatories (COCOON). 396--407","author":"Davoodi Pooya","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_18_1","unstructured":"Robert M. Fano. 1971. On the number of bits required to implement an associative memory. Memorandum 61. Computer Structures Group Project MAC. MIT Cambridge MA.  Robert M. Fano. 1971. On the number of bits required to implement an associative memory. Memorandum 61. Computer Structures Group Project MAC. MIT Cambridge MA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301973"},{"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.1145\/1613676.1613680"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488440"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.09.002"},{"key":"e_1_2_1_26_1","unstructured":"Donald E. Knuth. 1998. The Art of Computer Programming Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley Reading MA.   Donald E. Knuth. 1998. The Art of Computer Programming Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley Reading MA."},{"key":"e_1_2_1_27_1","unstructured":"Donald E. Knuth. 2009. The Art of Computer Programming Volume 4 Fascicle 1: Bitwise Tricks and Techniques; Binary Decision Diagrams (12th ed.). Addison-Wesley Professional.   Donald E. Knuth. 2009. The Art of Computer Programming Volume 4 Fascicle 1: Bitwise Tricks and Techniques; Binary Decision Diagrams (12th ed.). Addison-Wesley Professional."},{"volume-title":"Proceedings of the Data Compression Conference. 296--305","year":"1999","author":"Jesper Larsson N.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","unstructured":"LAW. 2011. Laboratory for Web Algorithmics\u2014Datasets. Retrieved September 9 2014 from law.dsi.unimi.it\/datasets.php.  LAW. 2011. Laboratory for Web Algorithmics\u2014Datasets. Retrieved September 9 2014 from law.dsi.unimi.it\/datasets.php."},{"key":"e_1_2_1_30_1","unstructured":"LIBCDS. 2011. LIBCDS\u2014Compact Data Structures Library. Retrieved September 9 2014 from https:\/\/github.com\/fclaude\/libcds.  LIBCDS. 2011. LIBCDS\u2014Compact Data Structures Library. Retrieved September 9 2014 from https:\/\/github.com\/fclaude\/libcds."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.6"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873614"},{"key":"e_1_2_1_34_1","unstructured":"SDSL. 2010. SDSL 0.9\u2014Succinct Data Structure Library. Retrieved September 9 2014 from http:\/\/www.uni-ulm.de\/in\/theo\/research\/sdsl.html.  SDSL. 2010. SDSL 0.9\u2014Succinct Data Structure Library. Retrieved September 9 2014 from http:\/\/www.uni-ulm.de\/in\/theo\/research\/sdsl.html."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802464"},{"key":"e_1_2_1_36_1","unstructured":"SUCCINCT. 2012. Succinct Library. Retrieved September 9 2014 from http:\/\/github.com\/ot\/succinct.  SUCCINCT. 2012. Succinct Library. Retrieved September 9 2014 from http:\/\/github.com\/ot\/succinct."},{"key":"e_1_2_1_37_1","unstructured":"SUX4J. 2011. Sux 0.7 and Sux4J 2.0.1\u2014Implementing Succinct Data Structures. Retrieved September 9 2014 from http:\/\/sux.di.unimi.it\/.  SUX4J. 2011. Sux 0.7 and Sux4J 2.0.1\u2014Implementing Succinct Data Structures. Retrieved September 9 2014 from http:\/\/sux.di.unimi.it\/."},{"key":"e_1_2_1_38_1","unstructured":"TX. 2010. Tx 0.18\u2014Succinct Trie Data Structure. Retrieved September 9 2014 from http:\/\/code.google.com\/p\/tx-trie\/.  TX. 2010. Tx 0.18\u2014Succinct Trie Data Structure. Retrieved September 9 2014 from http:\/\/code.google.com\/p\/tx-trie\/."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788900"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.3.193"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2656332","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2656332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:37Z","timestamp":1750231177000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2656332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,7]]},"references-count":40,"alternative-id":["10.1145\/2656332"],"URL":"https:\/\/doi.org\/10.1145\/2656332","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2015,1,7]]}}}