{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:41:22Z","timestamp":1777596082996,"version":"3.51.4"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,8,3]],"date-time":"2016-08-03T00:00:00Z","timestamp":1470182400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"SoBigData EU Project"},{"name":"MIUR of Italy under project PRIN ARS Technomedia 2012"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,9,2]]},"abstract":"<jats:p>\n            In this article, we study three variants of the well-known prefix-search problem for strings, and we design solutions for the cache-oblivious model which improve the best known results. Among these contributions, we close (asymptotically) the classic problem, which asks for the detection of the set of strings that share the longest common prefix with a queried pattern by providing an I\/O-optimal solution that matches the space lower bound for tries up to a constant multiplicative factor of the form (1 + \u03f5), for \u03f5 &gt; 0. Our solutions hinge upon a novel compressed storage scheme that adds the ability to decompress\n            <jats:italic>prefixes<\/jats:italic>\n            of the stored strings I\/O-optimally to the elegant locality-preserving front coding (Bender et al. 2006) still preserving its space bounds.\n          <\/jats:p>","DOI":"10.1145\/2903141","type":"journal-article","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T13:26:34Z","timestamp":1470317194000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Compressed Cache-Oblivious String B-Tree"],"prefix":"10.1145","volume":"12","author":[{"given":"Paolo","family":"Ferragina","sequence":"first","affiliation":[{"name":"Department of Computer Science University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rossano","family":"Venturini","sequence":"additional","affiliation":[{"name":"Department of Computer Science University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,8,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Alberto Apostolico. 1985. The myriad virtues of subword trees. Combinatorial Algorithms on Words (1985) 85--96.  Alberto Apostolico. 1985. The myriad virtues of subword trees. Combinatorial Algorithms on Words (1985) 85--96.","DOI":"10.1007\/978-3-642-82456-2_6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888935.1888985"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142385"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109621"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294165"},{"key":"e_1_2_1_6_1","unstructured":"Erik D. Demaine John Iacono and Stefan Langerman. 2004. Worst-case optimal tree layout in a memory hierarchy. CoRR cs.DS\/0410048 (2004).  Erik D. Demaine John Iacono and Stefan Langerman. 2004. Worst-case optimal tree layout in a memory hierarchy. CoRR cs.DS\/0410048 (2004)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_1_8_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_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.011"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301973"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376943"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868248"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_40"},{"key":"e_1_2_1_14_1","volume-title":"Information Retrieval: Data Structures and Algorithms","author":"Frakes William","year":"1992"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/367390.367400"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071383"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Dan Gusfield. 1997. Algorithms on Strings Trees and Sequences - Computer Science and Computational Biology. Cambridge University Press.   Dan Gusfield. 1997. Algorithms on Strings Trees and Sequences - Computer Science and Computational Biology. Cambridge University Press.","DOI":"10.1017\/CBO9780511574931"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344432"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1875737.1875761"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321481"},{"key":"e_1_2_1_22_1","volume-title":"Tables. In Proceedings of the 16th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 37--42","author":"Munro J. Ian","year":"1996"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"key":"e_1_2_1_24_1","unstructured":"Ian H. Witten Alistair Moffat and Timothy C. Bell. 1999. Managing Gigabytes: Compressing and Indexing Documents and Images (2nd ed.). Morgan Kaufmann.   Ian H. Witten Alistair Moffat and Timothy C. Bell. 1999. Managing Gigabytes: Compressing and Indexing Documents and Images (2nd ed.). Morgan Kaufmann."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903141","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2903141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:15Z","timestamp":1750222575000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,3]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,9,2]]}},"alternative-id":["10.1145\/2903141"],"URL":"https:\/\/doi.org\/10.1145\/2903141","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,3]]},"assertion":[{"value":"2015-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}