{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:49Z","timestamp":1725663289055},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540515425"},{"type":"electronic","value":"9783540482376"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51542-9_18","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:06:14Z","timestamp":1330203974000},"page":"206-217","source":"Crossref","is-referenced-by-count":5,"title":["Digital data structures and order statistics"],"prefix":"10.1007","author":[{"given":"Wojciech","family":"Szpankowski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"18_CR1","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley (1974)."},{"key":"18_CR2","unstructured":"D. Knuth, The Art of Computer Programming. Sorting and Searching, vol. III, Addison-Wesley (1973)."},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"A. Apostolico, \u201cThe Myriad Virtues of Suffix Trees\u201d, Combinatorial Algorithms on Words, 85\u201396, Springer-Verlag, ASI F12 (1985).","DOI":"10.1007\/978-3-642-82456-2_6"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1145\/320083.320092","volume":"4","author":"R. Fagin","year":"1979","unstructured":"R. Fagin, J. Nievergelt, N. Pippenger and H. Strong, \u201cExtendible Hashing: A Fast Access Method for Dynamic Files\u201d, ACM TODS, 4, 315\u2013344 (1979).","journal-title":"ACM TODS"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF00264279","volume":"20","author":"P. Flajolet","year":"1983","unstructured":"P. Flajolet, \u201cOn the Performance Evaluation of Extendible Hashing and Trie Searching\u201d, Acta Informatica, 20, 345\u2013369 (1983).","journal-title":"Acta Informatica"},{"key":"18_CR6","volume-title":"Information Theory and Reliable Communications","author":"R. Gallager","year":"1968","unstructured":"R. Gallager, Information Theory and Reliable Communications, John Wiley & Sons, New York (1968)."},{"key":"18_CR7","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1109\/TIT.1979.1056093","volume":"IT-25","author":"J. Capetanakis","year":"1979","unstructured":"J. Capetanakis, \u201cTree Algorithms for Packet Broadcast Channels\u201d, IEEE Trans. on Information Theory, IT-25, 505\u2013525 (1979).","journal-title":"IEEE Trans. on Information Theory"},{"key":"18_CR8","unstructured":"IEEE Transaction on Information Theory, IT-31, 2 (1985)."},{"key":"18_CR9","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/BFb0022669","volume":"214","author":"Ph. Jacquet","year":"1986","unstructured":"Ph. Jacquet and M. Regnier, \u201cTrie Partitioning Process: Limiting Distributions\u201d, in Lecture Notes in Computer Science, vol. 214, pp. 196\u2013210, Springer Verlag, New York 1986.","journal-title":"Lecture Notes in Computer Science"},{"key":"18_CR10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF00264248","volume":"21","author":"L. Devroye","year":"1984","unstructured":"L. Devroye, \u201cA Probabilistic Analysis of the Height of Tries and of the Complexity of Trie Sort\u201d, Acta Informatica, 21, 229\u2013232 (1984).","journal-title":"Acta Informatica"},{"key":"18_CR11","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1214\/aop\/1176993000","volume":"13","author":"B. Pittel","year":"1985","unstructured":"B. Pittel, \u201cAsymptotic Growth of a Class of Random Trees\u201d, The Annalus of Probability, 13, 414\u2013427 (1985).","journal-title":"The Annalus of Probability"},{"key":"18_CR12","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/1427240","volume":"18","author":"B. Pittel","year":"1986","unstructured":"B. Pittel, \u201cPath in a Random Digital Tree: Limiting Distributions\u201d, Adv. Appl. Probl., 18, 139\u2013155 (1986).","journal-title":"Adv. Appl. Probl."},{"key":"18_CR13","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/0020-0190(81)90033-8","volume":"13","author":"M. Regnier","year":"1981","unstructured":"M. Regnier, \u201cOn the Average Height of Trees in Digital Searching and Dynamic Hashing\u201d, Inform. Processing Letters, 13, 64\u201366 (1981).","journal-title":"Inform. Processing Letters"},{"key":"18_CR14","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/0020-0190(80)90008-3","volume":"11","author":"A. Yao","year":"1980","unstructured":"A. Yao, \u201cA Note on the Analysis of Extendible Hashing\u201d, Inform. Processing Letters, 11, 84\u201386 (1980).","journal-title":"Inform. Processing Letters"},{"key":"18_CR15","unstructured":"W. Szpankowski, \u201cOn the Analysis of the Average Height of a Digital Trie: Another Approach\u201d, Purdue University CSD TR-646 (1986); revision TR-816 (1988)."},{"key":"18_CR16","unstructured":"A. Apostolico and W. Szpankowski, \u201cSelf-Alignments in Words and Their Applications\u201d, Purdue University CSD TR-732 (1987), submitted to a journal."},{"key":"18_CR17","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/0196-6774(88)90039-9","volume":"9","author":"W. Szpankowski","year":"1988","unstructured":"W. Szpankowski, \u201cSome Results on V-ary Asymmetric Tries\u201d, Journal of Algorithms, 9, 224\u2013244 (1988).","journal-title":"Journal of Algorithms"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"P. Kirschenhofer, H. Prodinger and W. Szpankowski, \u201cOn the Variance of the External Path Length in a Symmetric Digital Trie\u201d, Discrete Applied Mathematics, to appear.","DOI":"10.1016\/0166-218X(89)90050-4"},{"key":"18_CR19","volume-title":"Order Statistics","author":"H. David","year":"1980","unstructured":"H. David, Order Statistics, John Wiley & Sons, New York (1980)."},{"key":"18_CR20","volume-title":"The Asymptotic Theory of Extreme Order Statistics","author":"J. Galambos","year":"1978","unstructured":"J. Galambos, The Asymptotic Theory of Extreme Order Statistics, John Wiley & Sons, New York (1978)."},{"key":"18_CR21","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/BF00536046","volume":"42","author":"T. Lai","year":"1978","unstructured":"T. Lai and H. Robbins, \u201cA Class of Dependent Random Variables and Their Maxima\u201d, Z. Wahrscheinlichkeitscheorie, 42, 89\u2013111 (1978).","journal-title":"Z. Wahrscheinlichkeitscheorie"},{"key":"18_CR22","volume-title":"Probability and Measures","author":"P. Billingsley","year":"1986","unstructured":"P. Billingsley, Probability and Measures, John Wiley & Sons, New York (1986)."},{"key":"18_CR23","unstructured":"W. Szpankowski, \u201c(Probably) Optimal Solutions to Some Problems NOT Only on Graphs\u201d, Purdue University CSD TR 780. 1988; revision 1989."},{"key":"18_CR24","doi-asserted-by":"crossref","first-page":"815","DOI":"10.2307\/3213436","volume":"15","author":"B. Silverman","year":"1978","unstructured":"B. Silverman and T.C. Brown, \u201cShort distances, flat triangles and Poisson limits\u201d, J. Appl. Probab., 15, 815\u2013825 (1978).","journal-title":"J. Appl. Probab."},{"key":"18_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-6283-9","volume-title":"Probability Approximations via the Poisson Clumping Heuristic","author":"D. Aldous","year":"1989","unstructured":"D. Aldous, Probability Approximations via the Poisson Clumping Heuristic, Springer Verlag, New York 1989."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:21:52Z","timestamp":1605648112000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}