{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:43:15Z","timestamp":1725482595219},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540673064"},{"type":"electronic","value":"9783540464150"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/10719839_31","type":"book-chapter","created":{"date-parts":[[2007,4,11]],"date-time":"2007-04-11T12:13:55Z","timestamp":1176293635000},"page":"298-307","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Heights in Generalized Tries and PATRICIA Tries"],"prefix":"10.1007","author":[{"given":"Charles","family":"Knessl","sequence":"first","affiliation":[]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,4,12]]},"reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF00264248","volume":"21","author":"L. Devroye","year":"1984","unstructured":"Devroye, L.: A Probabilistic Analysis of the Height of Tries and the complexity of Trie Sort. Acta Informatica\u00a021, 229\u2013237 (1984)","journal-title":"Acta Informatica"},{"key":"31_CR2","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1002\/rsa.3240030209","volume":"3","author":"L. Devroye","year":"1992","unstructured":"Devroye, L.: A Note on the Probabilistic Analysis of Patricia Tries. Random Structures & Algorithms\u00a03, 203\u2013214 (1992)","journal-title":"Random Structures & Algorithms"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1214\/aoap\/1177005709","volume":"2","author":"L. Devroye","year":"1992","unstructured":"Devroye, L.: A Study of Trie-Like Structures Under the Density Model. Ann. Appl. Probability\u00a02, 402\u2013434 (1992)","journal-title":"Ann. Appl. Probability"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF00264279","volume":"20","author":"P. Flajolet","year":"1983","unstructured":"Flajolet, P.: On the Performance Evaluation of Extendible Hashing and Trie Searching. Acta Informatica\u00a020, 345\u2013369 (1983)","journal-title":"Acta Informatica"},{"key":"31_CR5","volume-title":"JWKB Approximation","author":"N. Froman","year":"1965","unstructured":"Froman, N., Froman, P.: JWKB Approximation. North-Holland, Amsterdam (1965)"},{"key":"31_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences. Cambridge University Press, Cambridge (1997)"},{"key":"31_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/BFb0022669","volume-title":"CAAP\u201986","author":"P. Jacquet","year":"1986","unstructured":"Jacquet, P., R\u00e9gnier, M.: Trie Partitioning Process: Limiting Distributions. In: Franchi-Zannettacci, P. (ed.) CAAP 1986. LNCS, vol.\u00a0214, pp. 196\u2013210. Springer, Heidelberg (1986)"},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0304-3975(94)00298-W","volume":"144","author":"P. Jacquet","year":"1995","unstructured":"Jacquet, P., Szpankowski, W.: Asymptotic Behavior of the Lempel-Ziv Parsing Scheme and Digital Search Trees. Theoretical Computer Science\u00a0144, 161\u2013197 (1995)","journal-title":"Theoretical Computer Science"},{"key":"31_CR9","volume-title":"The Art of Computer Programming. Sorting and Searching","author":"D. Knuth","year":"1998","unstructured":"Knuth, D.: The Art of Computer Programming. Sorting and Searching, 2nd edn. Addison-Wesley, Reading (1998)","edition":"2"},{"key":"31_CR10","first-page":"43","volume":"3","author":"C. Knessl","year":"1999","unstructured":"Knessl, C., Szpankowski, W.: Quicksort Algorithm Again Revisited. Discrete Mathematics and Theoretical Computer Science\u00a03, 43\u201364 (1999)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"31_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1990-1","volume-title":"Matched Asymptotic Expansions: Ideas and Techniques","author":"P. Lagerstrom","year":"1988","unstructured":"Lagerstrom, P.: Matched Asymptotic Expansions: Ideas and Techniques. Springer, New York (1988)"},{"key":"31_CR12","volume-title":"Evolution of Random Search Trees","author":"H. Mahmoud","year":"1992","unstructured":"Mahmoud, H.: Evolution of Random Search Trees. John Wiley & Sons, New York (1992)"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1214\/aop\/1176993000","volume":"13","author":"B. Pittel","year":"1985","unstructured":"Pittel, B.: Asymptotic Growth of a Class of Random Trees. Ann. of Probab.\u00a013, 414\u2013427 (1985)","journal-title":"Ann. of Probab."},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.2307\/1427240","volume":"18","author":"B. Pittel","year":"1986","unstructured":"Pittel, B.: Path in a Random Digital Tree: Limiting Distributions. Adv. Appl. Prob.\u00a018, 139\u2013155 (1986)","journal-title":"Adv. Appl. Prob."},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/0097-3165(90)90072-5","volume":"55","author":"B. Pittel","year":"1990","unstructured":"Pittel, B., Rubin, H.: How Many Random Questions Are Necessary to Identify n Distinct Objects? J. Combin. Theory, Ser. A.\u00a055, 292\u2013312 (1990)","journal-title":"J. Combin. Theory, Ser. A."},{"key":"31_CR16","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/96559.214080","volume":"37","author":"W. Szpankowski","year":"1990","unstructured":"Szpankowski, W.: Patricia Tries Again Revisited. Journal of the ACM\u00a037, 691\u2013711 (1990)","journal-title":"Journal of the ACM"},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/BF01759045","volume":"6","author":"W. Szpankowski","year":"1991","unstructured":"Szpankowski, W.: On the Height of Digital Trees and Related Problems. Algorithmica\u00a06, 256\u2013277 (1991)","journal-title":"Algorithmica"},{"key":"31_CR18","doi-asserted-by":"publisher","first-page":"1176","DOI":"10.1137\/0222070","volume":"22","author":"W. Szpankowski","year":"1993","unstructured":"Szpankowski, W.: A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors. SIAM J. Compt.\u00a022, 1176\u20131198 (1993)","journal-title":"SIAM J. Compt."},{"key":"31_CR19","doi-asserted-by":"publisher","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. Information Theory\u00a024, 530\u2013536 (1978)","journal-title":"IEEE Trans. Information Theory"}],"container-title":["Lecture Notes in Computer Science","LATIN 2000: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/10719839_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,31]],"date-time":"2019-08-31T11:41:05Z","timestamp":1567251665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10719839_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540673064","9783540464150"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/10719839_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"12 April 2007","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}