{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:56Z","timestamp":1760202656977},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,9,26]],"date-time":"2013-09-26T00:00:00Z","timestamp":1380153600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s00453-013-9836-6","type":"journal-article","created":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T22:02:58Z","timestamp":1380146578000},"page":"969-988","source":"Crossref","is-referenced-by-count":21,"title":["Linked Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space"],"prefix":"10.1007","volume":"71","author":[{"given":"Jesper","family":"Jansson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,9,26]]},"reference":[{"issue":"6","key":"9836_CR1","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0020-0190(93)90068-K","volume":"46","author":"A. Andersson","year":"1993","unstructured":"Andersson, A., Nilsson, S.: Improved behaviour of tries by adaptive branching. Inf. Process. Lett. 46(6), 295\u2013300 (1993)","journal-title":"Inf. Process. Lett."},{"key":"9836_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/978-3-540-69068-9_26","volume-title":"Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching (CPM 2008)","author":"D. Arroyuelo","year":"2008","unstructured":"Arroyuelo, D.: An improved succinct representation for dynamic k-ary trees. In: Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching (CPM 2008). Lecture Notes in Computer Science, vol.\u00a05029, pp.\u00a0277\u2013289. Springer, Berlin (2008)"},{"issue":"7","key":"9836_CR3","doi-asserted-by":"crossref","first-page":"1070","DOI":"10.1016\/j.ic.2011.03.001","volume":"209","author":"D. Arroyuelo","year":"2011","unstructured":"Arroyuelo, D., Navarro, G.: Space-efficient construction of Lempel-Ziv compressed text indexes. Inf. Comput. 209(7), 1070\u20131102 (2011)","journal-title":"Inf. Comput."},{"issue":"1","key":"9836_CR4","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P. Beame","year":"2002","unstructured":"Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J.\u00a0Comput. Syst. Sci. 65(1), 38\u201372 (2002)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9836_CR5","first-page":"1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)","author":"D.K. Blandford","year":"2005","unstructured":"Blandford, D.K., Blelloch, G.E.: Dictionaries using variable-length keys and data, with applications. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp.\u00a01\u201310 (2005)"},{"issue":"3","key":"9836_CR6","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/spe.4380230305","volume":"23","author":"J.J. Darragh","year":"1993","unstructured":"Darragh, J.J., Cleary, J.G., Witten, I.H.: Bonsai: a compact representation of trees. Softw. Pract. Exp. 23(3), 277\u2013291 (1993)","journal-title":"Softw. Pract. Exp."},{"issue":"2","key":"9836_CR7","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1002\/rsa.20067","volume":"27","author":"L. Devroye","year":"2005","unstructured":"Devroye, L., Szpankowski, W.: Probabilistic behavior of asymmetric level compressed tries. Random Struct. Algorithms 27(2), 185\u2013200 (2005)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"9836_CR8","first-page":"236","volume":"46","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string B-tree: a new data structure for string search in external memory and its applications. J.\u00a0ACM 46(2), 236\u2013280 (1999)","journal-title":"J.\u00a0ACM"},{"issue":"4","key":"9836_CR9","first-page":"552","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed texts. J.\u00a0ACM 52(4), 552\u2013581 (2005)","journal-title":"J.\u00a0ACM"},{"issue":"9","key":"9836_CR10","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E. Fredkin","year":"1960","unstructured":"Fredkin, E.: Trie memory. Commun. ACM 3(9), 490\u2013499 (1960)","journal-title":"Commun. ACM"},{"issue":"2","key":"9836_CR11","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H.N. Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J.\u00a0Comput. Syst. Sci. 30(2), 209\u2013221 (1985)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"3","key":"9836_CR12","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.tcs.2006.09.014","volume":"368","author":"R.F. Geary","year":"2006","unstructured":"Geary, R.F., Rahman, N., Raman, R., Raman, V.: A simple optimal representation for balanced parentheses. Theor. Comput. Sci. 368(3), 231\u2013246 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9836_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1007\/BFb0028575","volume-title":"Procedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998)","author":"T. Hagerup","year":"1998","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: Procedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998). Lecture Notes in Computer Science, vol.\u00a01373, pp.\u00a0366\u2013398. Springer, Berlin (1998)"},{"issue":"1","key":"9836_CR14","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s00453-006-1228-8","volume":"48","author":"W.-K. Hon","year":"2007","unstructured":"Hon, W.-K., Lam, T.-W., Sadakane, K., Sung, W.-K., Yiu, S.-M.: A space and time efficient algorithm for constructing compressed suffix arrays. Algorithmica 48(1), 23\u201336 (2007)","journal-title":"Algorithmica"},{"issue":"1","key":"9836_CR15","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/PL00009205","volume":"21","author":"J. K\u00e4rkk\u00e4inen","year":"1998","unstructured":"K\u00e4rkk\u00e4inen, J., Sutinen, E.: Lempel-Ziv index for q-grams. Algorithmica 21(1), 137\u2013154 (1998)","journal-title":"Algorithmica"},{"issue":"3","key":"9836_CR16","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1137\/S0097539797331105","volume":"29","author":"S.R. Kosaraju","year":"1999","unstructured":"Kosaraju, S.R., Manzini, G.: Compression of low entropy strings with Lempel-Ziv algorithms. SIAM J. Comput. 29(3), 893\u2013911 (1999)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"9836_CR17","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1089\/cmb.2005.12.943","volume":"12","author":"R.A. Lippert","year":"2005","unstructured":"Lippert, R.A., Mobarry, C.M., Walenz, B.P.: A space-efficient construction of the Burrows-Wheeler transform for genomic data. J.\u00a0Comput. Biol. 12(7), 943\u2013951 (2005)","journal-title":"J.\u00a0Comput. Biol."},{"issue":"4","key":"9836_CR18","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0020-0190(90)90022-P","volume":"35","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Bounded ordered dictionaries in O(loglogN) time and O(n) space. Inf. Process. Lett. 35(4), 183\u2013189 (1990)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9836_CR19","first-page":"514","volume":"15","author":"D.R. Morrison","year":"1968","unstructured":"Morrison, D.R.: PATRICIA\u2014Practical Algorithm To Retrieve Information Coded In Alphanumeric. J.\u00a0ACM 15(4), 514\u2013534 (1968)","journal-title":"J.\u00a0ACM"},{"issue":"3","key":"9836_CR20","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9836_CR21","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S1570-8667(03)00066-2","volume":"2","author":"G. Navarro","year":"2004","unstructured":"Navarro, G.: Indexing text using the Ziv-Lempel trie. J.\u00a0Discrete Algorithms 2(1), 87\u2013114 (2004)","journal-title":"J.\u00a0Discrete Algorithms"},{"issue":"6","key":"9836_CR22","doi-asserted-by":"crossref","first-page":"1083","DOI":"10.1109\/49.772439","volume":"17","author":"S. Nilsson","year":"1999","unstructured":"Nilsson, S., Karlsson, G.: IP-address lookup using LC-tries. IEEE J. Sel. Areas Commun. 17(6), 1083\u20131092 (1999)","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"9836_CR23","series-title":"Lecture Notes in Computer Science.","volume-title":"The Design of Dynamic Data Structures","author":"M.H. Overmars","year":"1983","unstructured":"Overmars, M.H.: The Design of Dynamic Data Structures. Lecture Notes in Computer Science., vol.\u00a0156. Springer, Berlin (1983)"},{"key":"9836_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/3-540-45061-0_30","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003)","author":"R. Raman","year":"2003","unstructured":"Raman, R., Rao, S.S.: Succinct dynamic dictionaries and trees. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003). Lecture Notes in Computer Science, vol.\u00a02719, pp.\u00a0357\u2013368. Springer, Berlin (2003)"},{"key":"9836_CR25","first-page":"1230","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006)","author":"K. Sadakane","year":"2006","unstructured":"Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy bounds. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp.\u00a01230\u20131239 (2006)"},{"issue":"6","key":"9836_CR26","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","volume":"17","author":"T.A. Welch","year":"1984","unstructured":"Welch, T.A.: A technique for high-performance data compression. IEEE Comput. 17(6), 8\u201319 (1984)","journal-title":"IEEE Comput."},{"issue":"2","key":"9836_CR27","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \u0398(N). Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9836_CR28","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/0022-0000(84)90020-5","volume":"28","author":"D.E. Willard","year":"1984","unstructured":"Willard, D.E.: New trie data structures which support very fast search operations. J.\u00a0Comput. Syst. Sci. 28(3), 379\u2013394 (1984)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"5","key":"9836_CR29","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory 24(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9836-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9836-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9836-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:13Z","timestamp":1559137513000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9836-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,26]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9836"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9836-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,26]]}}}