{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:38Z","timestamp":1760202518304},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"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":[[1991,6]]},"DOI":"10.1007\/bf01759045","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:43:56Z","timestamp":1118918636000},"page":"256-277","source":"Crossref","is-referenced-by-count":37,"title":["On the height of digital trees and related problems"],"prefix":"10.1007","volume":"6","author":[{"given":"Wojciech","family":"Szpankowski","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01759045_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA (1974)."},{"key":"BF01759045_CR2","volume-title":"The Art of Computer Programming. Sorting and Searching, vol. III","author":"D. Knuth","year":"1973","unstructured":"D. Knuth,The Art of Computer Programming. Sorting and Searching, vol. III, Addison-Wesley, Reading, MA (1973)."},{"key":"BF01759045_CR3","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-642-82456-2_6","volume-title":"Combinatorial Algorithms on Words","author":"A. Apostolico","year":"1985","unstructured":"A. Apostolico, The Myriad Virtues of Suffix Trees,Combinatorial Algorithms on Words, pp. 85\u201396, Springer-Verlag, New York (1985)."},{"key":"BF01759045_CR4","doi-asserted-by":"crossref","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, Extendible Hashing: A Fast Access Method for Dynamic Files,ACM TODS,4, 315\u2013344 (1979).","journal-title":"ACM TODS"},{"key":"BF01759045_CR5","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF00264279","volume":"20","author":"P. Flajolet","year":"1983","unstructured":"P. Flajolet, On the Performance Evaluation of Extendible Hashing and Trie Searching,Acta Inform.,20, 345\u2013369 (1983).","journal-title":"Acta Inform."},{"key":"BF01759045_CR6","volume-title":"Information Theory and Reliable Communications","author":"R. Gallager","year":"1968","unstructured":"R. Gallager,Information Theory and Reliable Communications, Wiley, New York (1968)."},{"key":"BF01759045_CR7","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1109\/TIT.1979.1056093","volume":"25","author":"J. Capetanakis","year":"1979","unstructured":"J. Capetanakis, Tree Algorithms for Packet Broadcast Channels,IEEE Trans. Inform. Theory,25, 505\u2013525 (1979).","journal-title":"IEEE Trans. Inform. Theory"},{"key":"BF01759045_CR8","unstructured":"IEEE Transaction Inform. Theory,31, 2 (1985)."},{"key":"BF01759045_CR9","first-page":"196","volume-title":"Lecture Notes in Computer Science, vol. 214","author":"Ph. Jacquet","year":"1986","unstructured":"Ph. Jacquet and M. Regnier,Trie Partitioning Process: Limiting Distributions, Lecture Notes in Computer Science, vol. 214, pp. 196\u2013210, Springer-Verlag, Berlin, 1986."},{"key":"BF01759045_CR10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF00264248","volume":"21","author":"L. Devroye","year":"1984","unstructured":"L. Devroye, A Probabilistic Analysis of the Height of Tries and of the Complexity of Trie Sort,Acta Inform.,21, 229\u2013232 (1984).","journal-title":"Acta Inform."},{"key":"BF01759045_CR11","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1214\/aop\/1176993000","volume":"13","author":"B. Pittel","year":"1985","unstructured":"B. Pittel, Asymptotic Growth of a Class of Random Trees,Ann. Probab.,13, 414\u2013427 (1985).","journal-title":"Ann. Probab."},{"key":"BF01759045_CR12","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/1427240","volume":"18","author":"B. Pittel","year":"1986","unstructured":"B. Pittel, Path in a Random Digital Tree: Limiting Distributions,Adv. in Appl. Probab.,18, 139\u2013155 (1986).","journal-title":"Adv. in Appl. Probab."},{"key":"BF01759045_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, On the Average Height of Trees in Digital Searching and Dynamic Hashing,Inform. Process. Lett.,13, 64\u201366 (1981).","journal-title":"Inform. Process. Lett."},{"key":"BF01759045_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, A Note on the Analysis of Extendible Hashing,Inform. Process. Lett.,11, 84\u201386 (1980).","journal-title":"Inform. Process. Lett."},{"key":"BF01759045_CR15","unstructured":"W. Szpankowski, On the Analysis of the Average Height of a Digital Trie: Another Approach, CSD TR-646, Purdue University (1986)."},{"key":"BF01759045_CR16","unstructured":"A. Apostolico and W. Szpankowski, Self-Alignments in Words and Their Applications, CSD TR-732, Purdue University (1987), submitted to a journal."},{"key":"BF01759045_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, Some Results onV-ary Asymmetric Tries,J. Algorithms,9, 224\u2013244 (1988).","journal-title":"J. Algorithms"},{"key":"BF01759045_CR18","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0166-218X(89)90050-4","volume":"25","author":"P. Kirschenhofer","year":"1989","unstructured":"P. Kirschenhofer, H. Prodinger, and W. Szpankowski, On the Variance of the External Path Length in a Symmetric Digital Trie,Discrete Appl. Math.,25, 129\u2013143 (1989).","journal-title":"Discrete Appl. Math."},{"key":"BF01759045_CR19","volume-title":"Order Statistics","author":"H. David","year":"1980","unstructured":"H. David,Order Statistics, Wiley, New York (1980)."},{"key":"BF01759045_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, Wiley, New York (1978)."},{"key":"BF01759045_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, A Class of Dependent Random Variables and Their Maxima,Z. Wahrsch. Vern. Gebiete,42, 89\u2013111 (1978).","journal-title":"Z. Wahrsch. Vern. Gebiete"},{"key":"BF01759045_CR22","volume-title":"Probability and Measures","author":"P. Billingsley","year":"1986","unstructured":"P. Billingsley,Probability and Measures, Wiley, New York (1986)."},{"key":"BF01759045_CR23","unstructured":"W. Szpankowski, (Probably) Optimal Solutions to Some Problems NOT Only on Graphs, CSD TR-780, Purdue University (1988); revision TR-872 (1989)."},{"key":"BF01759045_CR24","volume-title":"Art of Computer Programming. Fundamental Algorithms, vol. I","author":"D. Knuth","year":"1973","unstructured":"D. Knuth,Art of Computer Programming. Fundamental Algorithms, vol. I, Addison-Wesley, Reading, MA (1973)."},{"key":"BF01759045_CR25","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparisons","year":"1983","unstructured":"D. Sankoff and J. Kruskal (eds.),Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparisons, Addison-Wesley, Reading, MA (1983)."},{"key":"BF01759045_CR26","unstructured":"Bull. Math. Biol,46, No. 4 (1984) (a special commemorative issue honoring Margonet O. Dayhoff)."},{"key":"BF01759045_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-6283-9","volume-title":"Probability Approximations via the Poisson Clumping Heristic","author":"D. Aldous","year":"1989","unstructured":"D. Aldous,Probability Approximations via the Poisson Clumping Heristic, Springer-Verlag, New York (1989)."},{"key":"BF01759045_CR28","doi-asserted-by":"crossref","first-page":"626","DOI":"10.2307\/3214002","volume":"23","author":"N. Kamarkar","year":"1986","unstructured":"N. Kamarkar, R. M. Karp, G. S. Lueker, and A. D. Odlyzko, Probabilistic Analysis of Optimum Partitioning,J. Appl. Probab.,23, 626\u2013645 (1986).","journal-title":"J. Appl. Probab."},{"key":"BF01759045_CR29","doi-asserted-by":"crossref","first-page":"293","DOI":"10.2307\/1427422","volume":"19","author":"S. Karlin","year":"1987","unstructured":"S. Karlin and F. Ost, Counts of Long Aligned Word Matches Among Random Letter Sequences,Adv. Appl. Probab.,19, 293\u2013351 (1987).","journal-title":"Adv. Appl. Probab."},{"key":"BF01759045_CR30","series-title":"Lecture Notes in Mathematics","volume-title":"Ecole d'Et\u00e9 de Probabilit\u00e9s de Saint-Flour V\u20141975","author":"J. F. C. Kingman","year":"1976","unstructured":"J. F. C. Kingman, Subadditive Processes, inEcole d'Et\u00e9 de Probabilit\u00e9s de Saint-Flour V\u20141975, Lecture Notes in Mathematics, vol. 539, Springer-Verlag, Berlin, 1976."},{"key":"BF01759045_CR31","unstructured":"L. Devroye, W. Szpankowski, and B. Rais, A Note on the Height of Suffix Trees, CSD TR-905, Purdue University (1989)."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759045.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01759045\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T16:25:43Z","timestamp":1557332743000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01759045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":31,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01759045"],"URL":"https:\/\/doi.org\/10.1007\/bf01759045","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}