{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:42Z","timestamp":1760202702612,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319238258"},{"type":"electronic","value":"9783319238265"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23826-5_31","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T08:20:20Z","timestamp":1441354820000},"page":"324-336","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Improved Practical Compact Dynamic Tries"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Poyias","sequence":"first","affiliation":[]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,9,5]]},"reference":[{"issue":"3","key":"31_CR1","doi-asserted-by":"publisher","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. Exper. 23(3), 277\u2013291 (1993)","journal-title":"Softw., Pract. Exper."},{"issue":"4","key":"31_CR2","doi-asserted-by":"publisher","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"},{"key":"31_CR3","unstructured":"Bentley, J., Sedgewick, B.: Ternary search trees (1998). http:\/\/www.drdobbs.com\/database\/ternary-search-trees\/184410528"},{"issue":"1","key":"31_CR4","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00453-001-0102-y","volume":"33","author":"S Nilsson","year":"2002","unstructured":"Nilsson, S., Tikkanen, M.: An experimental study of compression methods for dynamic tries. Algorithmica 33(1), 19\u201333 (2002)","journal-title":"Algorithmica"},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th Annual Symposium on Foundations of Computer Science, pp. 549\u2013554. IEEE Computer Society (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms 3(4) (2007)","DOI":"10.1145\/1290672.1290680"},{"issue":"1","key":"31_CR7","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/s00453-012-9664-0","volume":"68","author":"A Farzan","year":"2014","unstructured":"Farzan, A., Munro, J.I.: A uniform paradigm to succinctly encode various families of trees. Algorithmica 68(1), 16\u201340 (2014)","journal-title":"Algorithmica"},{"key":"31_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-642-02927-1_38","volume-title":"Automata, Languages and Programming","author":"A Farzan","year":"2009","unstructured":"Farzan, A., Raman, R., Rao, S.S.: Universal succinct representations of trees? In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 451\u2013462. Springer, Heidelberg (2009)"},{"key":"31_CR9","unstructured":"Munro, J.I., Raman, V., Storm, A.J.: Representing dynamic binary trees succinctly. In: Kosaraju, S.R. (ed.) Proc. 12th Annual Symposium on Discrete Algorithms, pp. 529\u2013536. ACM\/SIAM (2001)"},{"key":"31_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/3-540-45061-0_30","volume-title":"Automata, Languages and Programming","author":"R Raman","year":"2003","unstructured":"Raman, R., Rao, S.S.: Succinct dynamic dictionaries and trees. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 357\u2013368. Springer, Heidelberg (2003)"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Arroyuelo, D., Davoodi, P., Satti, S.: Succinct dynamic cardinal trees. Algorithmica, 1\u201336 (2015) (online first)","DOI":"10.1007\/s00453-015-9969-x"},{"issue":"4","key":"31_CR12","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1007\/s00453-013-9836-6","volume":"71","author":"J Jansson","year":"2015","unstructured":"Jansson, J., Sadakane, K., Sung, W.: Linked dynamic tries with applications to lz-compression in sublinear time and space. Algorithmica 71(4), 969\u2013988 (2015)","journal-title":"Algorithmica"},{"key":"31_CR13","unstructured":"Takagi, T., Uemura, T., Inenaga, S., Sadakane, K., Arimura, H.:Applications of succinct dynamic compact tries to some stringproblems (presented at WAAC 2013). http:\/\/www-ikn.ist.hokudai.ac.jp\/~arim\/papers\/waac13takagi.pdf"},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"Grossi, R., Ottaviano, G.: The wavelet trie: maintaining an indexed sequence of strings in compressed space. In: PODS, pp. 203\u2013214 (2012)","DOI":"10.1145\/2213556.2213586"},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"Patrascu, M.: Succincter. In: 49th Annual IEEE Symp. Foundations of Computer Science, pp. 305\u2013313. IEEE Computer Society (2008)","DOI":"10.1109\/FOCS.2008.83"},{"key":"31_CR16","unstructured":"Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol. 3, 2nd edn. Addison Wesley Longman (1998)"},{"issue":"2","key":"31_CR17","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L Carter","year":"1979","unstructured":"Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"31_CR18","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with 0(1) worst case access time. J. ACM 31(3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"issue":"2","key":"31_CR19","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/S0097539700369909","volume":"31","author":"R Pagh","year":"2001","unstructured":"Pagh, R.: Low redundancy in static dictionaries with constant query time. SIAM J. Comput. 31(2), 353\u2013363 (2001)","journal-title":"SIAM J. Comput."},{"key":"31_CR20","unstructured":"Yoshinaga, N., Kitsuregawa, M.: A self-adaptive classifier for efficient text-stream processing. In: COLING 2014, 25th International Conference on Computational Linguistics, Proceedings of the Conference: Technical Papers, August 23\u201329, 2014, Dublin, Ireland, pp. 1091\u20131102 (2014)"},{"key":"31_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/978-3-319-07959-2_28","volume-title":"Experimental Algorithms","author":"S Gog","year":"2014","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326\u2013337. Springer, Heidelberg (2014)"},{"key":"31_CR22","unstructured":"Goethals, B.: Frequent itemset mining implementations repository. http:\/\/fimi.ua.ac.be\/"},{"key":"31_CR23","doi-asserted-by":"crossref","unstructured":"Schlegel, B., Gemulla, R., Lehner, W.: Memory-efficient frequent-itemset mining. In: Proceedings of the 14th International Conference on Extending Database Technology, EDBT 2011, Uppsala, Sweden, March 21\u201324, 2011, pp. 461\u2013472 (2011)","DOI":"10.1145\/1951365.1951420"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23826-5_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T16:26:02Z","timestamp":1674836762000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23826-5_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319238258","9783319238265"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23826-5_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"5 September 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}