{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:44Z","timestamp":1740109304787,"version":"3.37.3"},"reference-count":63,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T00:00:00Z","timestamp":1629417600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T00:00:00Z","timestamp":1629417600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100008393","name":"Teknologi og Produktion, Det Frie Forskningsr\u00e5d","doi-asserted-by":"crossref","award":["4005-00267","1323-00178"],"award-info":[{"award-number":["4005-00267","1323-00178"]}],"id":[{"id":"10.13039\/100008393","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1475\/18","592\/17"],"award-info":[{"award-number":["1475\/18","592\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2018141"],"award-info":[{"award-number":["2018141"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,12]]},"DOI":"10.1007\/s00453-021-00869-w","type":"journal-article","created":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T04:05:37Z","timestamp":1629432337000},"page":"3602-3628","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Top Tree Compression of Tries"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1120-5154","authenticated-orcid":false,"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gad M.","family":"Landau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,20]]},"reference":[{"key":"869_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Arge, L., Larsen, K.G.: Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model. In: Proceedings of the 28th SoCG, pp. 323\u2013332 (2012)","DOI":"10.1145\/2261250.2261299"},{"key":"869_CR2","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Proceedings of the 27th ICALP, pp. 73\u201384 (2000)","DOI":"10.1007\/3-540-45022-X_8"},{"issue":"2","key":"869_CR3","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/1103963.1103966","volume":"1","author":"S Alstrup","year":"2005","unstructured":"Alstrup, S., Holm, J., Lichtenberg, K.D., Thorup, M.: Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms 1(2), 243\u2013264 (2005)","journal-title":"ACM Trans. Algorithms"},{"issue":"9","key":"869_CR4","doi-asserted-by":"crossref","first-page":"1066","DOI":"10.1109\/32.31365","volume":"15","author":"JI Aoe","year":"1989","unstructured":"Aoe, J.I.: An efficient digital search algorithm by using a double-array structure. IEEE Trans. Softw. Eng. 15(9), 1066\u20131077 (1989)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"869_CR5","doi-asserted-by":"crossref","unstructured":"Arz, J., Fischer, J.: LZ-compressed string dictionaries. In: Proceedings of the 24th DCC, pp. 322\u2013331 (2014)","DOI":"10.1109\/DCC.2014.36"},{"key":"869_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-016-0226-8","volume":"80","author":"J Arz","year":"2018","unstructured":"Arz, J., Fischer, J.: Lempel\u2013Ziv-78 compressed string dictionaries. Algorithmica 80, 1\u201336 (2018)","journal-title":"Algorithmica"},{"issue":"5","key":"869_CR7","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1007\/s00778-010-0183-9","volume":"19","author":"N Askitis","year":"2010","unstructured":"Askitis, N., Sinha, R.: Engineering scalable, cache and space efficient tries for strings. VLDB J. 19(5), 633\u2013660 (2010)","journal-title":"VLDB J."},{"key":"869_CR8","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Vigna, S.: Dynamic Z-fast tries. In: Proceedings of the 17th SPIRE, pp. 159\u2013172 (2010)","DOI":"10.1007\/978-3-642-16321-0_15"},{"key":"869_CR9","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., Raffinot, M.: Composite repetition-aware data structures. In: Proceedings of the 26th CPM, pp. 26\u201339 (2015)","DOI":"10.1007\/978-3-319-19929-0_3"},{"key":"869_CR10","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Ord\u00f3nez, A., Puglisi, S.J., Tabei, Y.: Queries on LZ-bounded encodings. In: Proceedings of the 25th DCC, pp. 83\u201392 (2015)","DOI":"10.1109\/DCC.2015.69"},{"key":"869_CR11","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Gagie, T., Gog, S., Manzini, G., Sir\u00e9n, J.: Relative FM-indexes. In: Proceedings of the 21st SPIRE, pp. 52\u201364 (2014)","DOI":"10.1007\/978-3-319-11918-2_6"},{"issue":"1","key":"869_CR12","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"MA Bender","year":"2004","unstructured":"Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theoret. Comput. Sci. 321(1), 5\u201312 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"869_CR13","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43(4), 275\u2013292 (2005)","journal-title":"Algorithmica"},{"issue":"3","key":"869_CR14","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"SW Bent","year":"1985","unstructured":"Bent, S.W., Sleator, D.D., Tarjan, R.E.: Biased search trees. SIAM J. Comput. 14(3), 545\u2013568 (1985)","journal-title":"SIAM J. Comput."},{"key":"869_CR15","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.tcs.2017.12.021","volume":"713","author":"P Bille","year":"2018","unstructured":"Bille, P., Ettienne, M.B., G\u00f8rtz, I.L., Vildh\u00f8j, H.W.: Time-space trade-offs for Lempel\u2013Ziv compressed indexing. Theor. Comput. Sci. 713, 66\u201377 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"869_CR16","doi-asserted-by":"crossref","unstructured":"Bille, P., Fernstr\u00f8m, F., G\u00f8rtz, I.L.: Tight bounds for top tree compression. In: Proceedings of the 24th SPIRE, pp. 97\u2013102 (2017)","DOI":"10.1007\/978-3-319-67428-5_9"},{"key":"869_CR17","unstructured":"Bille, P., Gawrychowski, P., G\u00f8rtz, I.L., Landau, G.M., Weimann, O.: Top tree compression of tries. In: Proceedings of the 30th ISAAC (2019)"},{"key":"869_CR18","unstructured":"Bille, P., G\u00f8rtz, I.L., Skjoldjensen, F.R.: Deterministic indexing for packed strings. In: Proceedings of the 28th CPM (2017)"},{"key":"869_CR19","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.ic.2014.12.012","volume":"243","author":"P Bille","year":"2015","unstructured":"Bille, P., G\u00f8rtz, I.L., Weimann, O., Landau, G.M.: Tree compression with top trees. Inf. Comput. 243, 166\u2013177 (2015). (Announced at ICALP 2013)","journal-title":"Inf. Comput."},{"issue":"3","key":"869_CR20","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2015","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44(3), 513\u2013539 (2015). (Announced at SODA 2011)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"869_CR21","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1145\/77600.77614","volume":"37","author":"B Chazelle","year":"1990","unstructured":"Chazelle, B.: Lower bounds for orthogonal range searching: I. The reporting case. J. ACM 37(2), 200\u2013212 (1990)","journal-title":"J. ACM"},{"issue":"5","key":"869_CR22","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0925-7721(95)00002-X","volume":"5","author":"B Chazelle","year":"1996","unstructured":"Chazelle, B., Rosenberg, B.: Simplex range reporting on a pointer machine. Comput. Geom. 5(5), 237\u2013247 (1996)","journal-title":"Comput. Geom."},{"key":"869_CR23","doi-asserted-by":"crossref","unstructured":"Christiansen, A.R., Ettienne, M.B.: Compressed indexing with signature grammars. In: Proceedings of the 13th LATIN, pp. 331\u2013345 (2018)","DOI":"10.1007\/978-3-319-77404-6_25"},{"issue":"3","key":"869_CR24","first-page":"313","volume":"111","author":"F Claude","year":"2011","unstructured":"Claude, F., Navarro, G.: Self-indexed grammar-based compression. Fund. Inform. 111(3), 313\u2013337 (2011)","journal-title":"Fund. Inform."},{"key":"869_CR25","doi-asserted-by":"crossref","unstructured":"Claude, F., Navarro, G.: Improved grammar-based compressed indexes. In: Proceedings of the 19th SPIRE, pp. 180\u2013192 (2012)","DOI":"10.1007\/978-3-642-34109-0_19"},{"issue":"3","key":"869_CR26","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/spe.4380230305","volume":"23","author":"JJ 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."},{"key":"869_CR27","doi-asserted-by":"crossref","unstructured":"Dietz, P.F.: Finding level-ancestors in dynamic trees. In: Proceedings of the 2nd WADS, pp. 32\u201340 (1991)","DOI":"10.1007\/BFb0028247"},{"issue":"4","key":"869_CR28","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1145\/322217.322228","volume":"27","author":"PJ Downey","year":"1980","unstructured":"Downey, P.J., Sethi, R., Tarjan, R.E.: Variations on the common subexpression problem. J. ACM 27(4), 758\u2013771 (1980)","journal-title":"J. ACM"},{"key":"869_CR29","unstructured":"Dudek, B., Gawrychowski, P.: Slowing down top trees for better worst-case compression. In: Proceedings of the 29th CPM, pp. 16:1\u201316:8 (2018)"},{"issue":"5","key":"869_CR30","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1093\/comjnl\/bxx108","volume":"61","author":"A Farruggia","year":"2017","unstructured":"Farruggia, A., Gagie, T., Navarro, G., Puglisi, S.J., Sir\u00e9n, J.: Relative suffix trees. Comput. J. 61(5), 773\u2013788 (2017)","journal-title":"Comput. J."},{"issue":"9","key":"869_CR31","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"},{"key":"869_CR32","doi-asserted-by":"crossref","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: A faster grammar-based self-index. In: Proceedings of the 6th LATA, pp. 240\u2013251 (2012)","DOI":"10.1007\/978-3-642-28332-1_21"},{"key":"869_CR33","doi-asserted-by":"crossref","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: LZ77-based self-indexing with faster pattern matching. In: Proceedings of the 11th LATIN, pp. 731\u2013742 (2014)","DOI":"10.1007\/978-3-642-54423-1_63"},{"key":"869_CR34","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2656332","volume":"19","author":"R Grossi","year":"2015","unstructured":"Grossi, R., Ottaviano, G.: Fast compressed tries through path decompositions. ACM J. Exp. Algorithm. 19, 3\u20134 (2015)","journal-title":"ACM J. Exp. Algorithm."},{"issue":"2","key":"869_CR35","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"key":"869_CR36","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: Proceedings of the 15th STACS, pp. 366\u2013398 (1998)","DOI":"10.1007\/BFb0028575"},{"issue":"4","key":"869_CR37","first-page":"53:1\u201353:32","volume":"12","author":"M He","year":"2016","unstructured":"He, M., Munro, J.I., Zhou, G.: Data structures for path queries. ACM Trans. Algorithms 12(4), 53:1\u201353:32 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"869_CR38","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0020-0190(81)90030-2","volume":"13","author":"R Hood","year":"1981","unstructured":"Hood, R., Melville, R.: Real-time queue operation in pure LISP. Inf. Process. Lett. 13(2), 50\u201354 (1981)","journal-title":"Inf. Process. Lett."},{"key":"869_CR39","doi-asserted-by":"crossref","unstructured":"H\u00fcbschle-Schneider, L., Raman, R.: Tree compression with top trees revisited. In: Proceedings of the 14th SEA, pp. 15\u201327 (2015)","DOI":"10.1007\/978-3-319-20086-6_2"},{"issue":"3","key":"869_CR40","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1007\/s10115-016-0999-8","volume":"51","author":"S Kanda","year":"2017","unstructured":"Kanda, S., Morita, K., Fuketa, M.: Compressed double-array tries for string dictionaries supporting fast lookup. Knowl. Inf. Syst. 51(3), 1023\u20131042 (2017)","journal-title":"Knowl. Inf. Syst."},{"key":"869_CR41","doi-asserted-by":"crossref","unstructured":"Kanda, S., Morita, K., Fuketa, M.: Practical implementation of space-efficient dynamic keyword dictionaries. In: Proceedings of the 24th SPIRE, pp. 221\u2013233 (2017)","DOI":"10.1007\/978-3-319-67428-5_19"},{"key":"869_CR42","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Lempel\u2013Ziv parsing and sublinear-size index structures for string matching. In: Proceedings of the 3rd WSP, pp. 141\u2013155 (1996)"},{"issue":"2","key":"869_CR43","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"869_CR44","volume-title":"The Art of Computer Programming","author":"DE Knuth","year":"1969","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. 1. Addison Wesley, Boston (1969)"},{"issue":"2","key":"869_CR45","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr. J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"869_CR46","first-page":"191","volume":"56","author":"V M\u00e4kinen","year":"2003","unstructured":"M\u00e4kinen, V.: Compact suffix array\u2014a space-efficient full-text index. Fund. Inform. 56(1\u20132), 191\u2013210 (2003)","journal-title":"Fund. Inform."},{"issue":"1","key":"869_CR47","first-page":"40","volume":"12","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nordic J. Comput. 12(1), 40\u201366 (2005)","journal-title":"Nordic J. Comput."},{"key":"869_CR48","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Navarro, G., Sir\u00e9n, J., V\u00e4lim\u00e4ki, N.: Storage and retrieval of individual genomes. In: Proceedings of the 13th RECOMB, pp. 121\u2013137 (2009)","DOI":"10.1007\/978-3-642-02008-7_9"},{"issue":"3","key":"869_CR49","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1089\/cmb.2009.0169","volume":"17","author":"V M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., Navarro, G., Sir\u00e9n, J., V\u00e4lim\u00e4ki, N.: Storage and retrieval of highly repetitive sequence collections. J. Comput. Biol. 17(3), 281\u2013308 (2010)","journal-title":"J. Comput. Biol."},{"key":"869_CR50","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39, 1 (2007)","journal-title":"ACM Comput. Surv."},{"key":"869_CR51","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.tcs.2018.09.007","volume":"762","author":"G Navarro","year":"2019","unstructured":"Navarro, G., Prezza, N.: Universal compressed text indexing. Theor. Comput. Sci. 762, 41\u201350 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"869_CR52","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1016\/j.dam.2019.01.014","volume":"274","author":"T Nishimoto","year":"2019","unstructured":"Nishimoto, T., Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Dynamic index and LZ factorization in compressed space. Discrete Appl. Math. 274, 116\u2013129 (2019)","journal-title":"Discrete Appl. Math."},{"key":"869_CR53","doi-asserted-by":"crossref","unstructured":"Poyias, A., Raman, R.: Improved practical compact dynamic tries. In: Proceedings of the 22nd SPIRE, pp. 324\u2013336 (2015)","DOI":"10.1007\/978-3-319-23826-5_31"},{"issue":"2","key":"869_CR54","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"FP Preparata","year":"1977","unstructured":"Preparata, F.P., Hong, S.J.: Convex hulls of finite sets of points in two and three dimensions. Commun. ACM 20(2), 87\u201393 (1977)","journal-title":"Commun. ACM"},{"issue":"4","key":"869_CR55","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding K-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"869_CR56","doi-asserted-by":"crossref","unstructured":"Sadakane, K.: Compressed text databases with efficient query algorithms based on the compressed suffix array. In: Proceedings of the 11th ISAAC, pp. 410\u2013421 (2000)","DOI":"10.1007\/3-540-40996-3_35"},{"key":"869_CR57","doi-asserted-by":"crossref","unstructured":"Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V., Navarro, G.: Run-length compressed indexes are superior for highly repetitive sequence collections. In: Proceedings of the 15th SPIRE, pp. 164\u2013175 (2008)","DOI":"10.1007\/978-3-540-89097-3_17"},{"key":"869_CR58","doi-asserted-by":"crossref","unstructured":"Takagi, T., Goto, K., Fujishige, Y., Inenaga, S., Arimura, H.: Linear-size CDAWG: new repetition-aware indexing and grammar compression. In: Proceedings of the 24th SPIRE, pp. 304\u2013316 (2017)","DOI":"10.1007\/978-3-319-67428-5_26"},{"issue":"9","key":"869_CR59","doi-asserted-by":"crossref","first-page":"1785","DOI":"10.1587\/transfun.E100.A.1785","volume":"100","author":"T Takagi","year":"2017","unstructured":"Takagi, T., Inenaga, S., Sadakane, K., Arimura, H.: Packed compact tries: a fast and efficient data structure for online string processing. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 100(9), 1785\u20131793 (2017)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"issue":"2","key":"869_CR60","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"RE Tarjan","year":"1979","unstructured":"Tarjan, R.E.: A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. 18(2), 110\u2013127 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"869_CR61","unstructured":"Tsuruta, K., K\u00f6ppl, D., Kanda, S., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Dynamic packed compact tries revisited (2019). arXiv preprint arXiv:1904.07467"},{"key":"869_CR62","unstructured":"Yata, S.: Dictionary compression by nesting prefix\/patricia tries. In: Proceedings of the 17th Meeting of the Association for Natural Language (2011)"},{"key":"869_CR63","unstructured":"Yoshinaga, N., Kitsuregawa, M.: A self-adaptive classifier for efficient text-stream processing. In: Proceedings of the 25th COLING, pp. 1091\u20131102 (2014)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00869-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00869-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00869-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T11:39:04Z","timestamp":1637321944000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00869-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,20]]},"references-count":63,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["869"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00869-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,8,20]]},"assertion":[{"value":"20 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}