{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T06:18:59Z","timestamp":1648534739160},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2006,9,22]],"date-time":"2006-09-22T00:00:00Z","timestamp":1158883200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2006,10,17]]},"DOI":"10.1007\/s00236-006-0019-7","type":"journal-article","created":{"date-parts":[[2006,10,3]],"date-time":"2006-10-03T20:10:03Z","timestamp":1159906203000},"page":"243-264","source":"Crossref","is-referenced-by-count":4,"title":["Distances in random digital search trees"],"prefix":"10.1007","volume":"43","author":[{"given":"Rafik","family":"Aguech","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nabil","family":"Lasmar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hosam","family":"Mahmoud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,9,22]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1239\/jap\/1152413729","volume":"43","author":"R. Aguech","year":"2006","unstructured":"Aguech R., Lasmar N., Mahmoud H. (2006) Limit distribution of distances in biased random tries. J. Appl. Probab. 43, 1\u201314","journal-title":"J. Appl. Probab."},{"key":"19_CR2","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0196-6774(02)00208-0","volume":"44","author":"H. Chern","year":"2002","unstructured":"Chern H., Hwang H., Tsai T. (2002) An asymptotic theory for Cauchy-Euler differential equations with applications to the analysis of algorithms. J. Algorithms 44, 177\u2013225","journal-title":"J. Algorithms"},{"key":"19_CR3","doi-asserted-by":"crossref","first-page":"1536","DOI":"10.1214\/105051605000000106","volume":"15","author":"C. Christophi","year":"2005","unstructured":"Christophi C., Mahmoud H. (2005) The oscillatory distribution of distances in random tries. Ann. Appl. Probab. 15, 1536\u20131564","journal-title":"Ann. Appl. Probab."},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Coffman E., Eve J.: File structures using hashing functions. Commun. ACM 13, 427\u2013432, and 436 (1970)","DOI":"10.1145\/362686.362693"},{"key":"19_CR5","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/S0097539703424521","volume":"33","author":"L. Devroye","year":"2004","unstructured":"Devroye L., Neininger R. (2004) Distances and finger search in random binary search trees. SIAM J. Comput. 33, 647\u2013658","journal-title":"SIAM J. Comput."},{"key":"19_CR6","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1137\/0215054","volume":"15","author":"P. Flajolet","year":"1986","unstructured":"Flajolet P., Sedgewick R. (1986) Digital search trees revisited. SIAM J. Comput. 15, 748\u2013767","journal-title":"SIAM J. Comput."},{"key":"19_CR7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(95)00002-E","volume":"144","author":"P. Flajolet","year":"1995","unstructured":"Flajolet P., Gourdon X., Dumas P. (1995) Mellin transform and asymptotic harmonic sums. Theor. Comput. Sci. 144, 3\u201358","journal-title":"Theor. Comput. Sci."},{"key":"19_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-70982-1","volume-title":"Mathematical Concepts in Organic Chemistry","author":"I. Gutman","year":"1986","unstructured":"Gutman I., Polansky O. (1986) Mathematical Concepts in Organic Chemistry. Springer, Berlin Heidelberg New York"},{"key":"19_CR9","unstructured":"Jacquet P.: Contribution de l\u2019Analyse d\u2019Algorithmes a l\u2019Evaluation de Protocoles de Communication. Th\u00e8se Universit\u00e9 de Paris Sud-Orsay, Paris (1989)"},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00167-9","volume":"201","author":"P. Jacquet","year":"1998","unstructured":"Jacquet P., Szpankowski W. (1998) Analytical depoissonization and its applications. Theor. Comput. Sci. 201, 1\u201362","journal-title":"Theor. Comput. Sci."},{"key":"19_CR11","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0304-3975(88)90023-0","volume":"58","author":"P. Kirschenhofer","year":"1988","unstructured":"Kirschenhofer P., Prodinger H. (1988) Further results on digital search trees. Theor. Comput. Sci. 58, 143\u2013154","journal-title":"Theor. Comput. Sci."},{"key":"19_CR12","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1137\/S0097539790189368","volume":"23","author":"P. Kirschenhofer","year":"1994","unstructured":"Kirschenhofer P., Prodinger H., Szpankowski W. (1994) Digital search trees again revisited: the internal path length perspective. SIAM J. Comput. 23, 598\u2013616","journal-title":"SIAM J. Comput."},{"key":"19_CR13","unstructured":"Knuth D. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Addison-Wesley, Reading, MA (1998)"},{"key":"19_CR14","first-page":"479","volume":"21","author":"G. Louchard","year":"1987","unstructured":"Louchard G. (1987) Exact and asymptotic distributions in digital and binary search trees. RAIRO: Theor. Informat. Appl. 21, 479\u2013495","journal-title":"RAIRO: Theor. Informat. Appl."},{"key":"19_CR15","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1109\/18.370149","volume":"41","author":"G. Louchard","year":"1995","unstructured":"Louchard G., Szpankowski W. (1995) Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm. IEEE Trans. Informat. Theory 41, 478\u2013488","journal-title":"IEEE Trans. Informat. Theory"},{"key":"19_CR16","first-page":"935","volume":"28","author":"G. Louchard","year":"1999","unstructured":"Louchard G., Szpankowski W., Tang J. (1999) Average profile of the generalized digital-search tree and the generalized Lempel-Ziv algorithms. SIAM J. Comput. 28, 935\u2013954","journal-title":"SIAM J. Comput."},{"key":"19_CR17","volume-title":"Evolution of Random Search Trees","author":"H. Mahmoud","year":"1992","unstructured":"Mahmoud H. (1992) Evolution of Random Search Trees. Wiley, New York"},{"key":"19_CR18","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1214\/aoap\/1042765668","volume":"13","author":"M. Mahmoud","year":"2003","unstructured":"Mahmoud M., Neininger R. (2003) Distribution of distances in random binary search trees. Ann. Appl. Probab. 13, 253\u2013276","journal-title":"Ann. Appl. Probab."},{"key":"19_CR19","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1109\/TIT.1985.1057013","volume":"31","author":"P. Mathys","year":"1985","unstructured":"Mathys P., Flajolet P. (1985) Q-ary collision resolution algorithms in random-access systems with free and blocked channel access. IEEE Trans. Informat. Theory 31, 217\u2013243","journal-title":"IEEE Trans. Informat. Theory"},{"key":"19_CR20","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1002\/rsa.10010","volume":"19","author":"R. Neininger","year":"2001","unstructured":"Neininger R. (2001) On a multivariate contraction method for random recursive structures with applications to Quicksort. Random Struct. Algorithms 19, 498\u2013524","journal-title":"Random Struct. Algorithms"},{"key":"19_CR21","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1017\/S0963548302005321","volume":"11","author":"R. Neininger","year":"2002","unstructured":"Neininger R. (2002) The Wiener index of random trees. Combinat. Probab. Comput. 11, 587\u2013597","journal-title":"Combinat. Probab. Comput."},{"key":"19_CR22","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1214\/aoap\/1075828056","volume":"14","author":"R. Neininger","year":"2004","unstructured":"Neininger R., R\u00fcschendorf L. (2004) A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab. 14, 378\u2013418","journal-title":"Ann. Appl. Probab."},{"key":"19_CR23","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1214\/105051604000000071","volume":"14","author":"A. Panholzer","year":"2004","unstructured":"Panholzer A., Prodinger H. (2004) Spanning tree size in random binary search trees. Ann. Appl. Probab. 14, 718\u2013733","journal-title":"Ann. Appl. Probab."},{"key":"19_CR24","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1214\/aop\/1176993000","volume":"13","author":"B. Pittel","year":"1985","unstructured":"Pittel B. (1985) Asymptotical growth of a class of random trees. Ann. Probab. 13, 414\u2013427","journal-title":"Ann. Probab."},{"key":"19_CR25","doi-asserted-by":"crossref","first-page":"770","DOI":"10.2307\/1428133","volume":"27","author":"S. Rachev","year":"1995","unstructured":"Rachev S., R\u00fcschendorf L. (1995) Probability metrics and recursive algorithms. Adv. Appl. Probab. 27, 770\u2013799","journal-title":"Adv. Appl. Probab."},{"key":"19_CR26","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1051\/ita\/1991250100851","volume":"25","author":"U. R\u00f6sler","year":"1991","unstructured":"R\u00f6sler U. (1991) A limit theorem for \u201cQuicksort\u201d. RAIRO Inform. Th\u00e9or. Appl. 25, 85\u2013100","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"19_CR27","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/BF02679621","volume":"29","author":"U. R\u00f6sler","year":"2001","unstructured":"R\u00f6sler U. (2001) On the analysis of stochastic divide and conquer algorithms. Algorithmica, 29, 238\u2013261","journal-title":"Algorithmica,"},{"key":"19_CR28","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02679611","volume":"29","author":"U. R\u00f6sler","year":"2001","unstructured":"R\u00f6sler U., R\u00fcschendorf L. (2001) The contraction method for recursive algorithms. Algorithmica 29, 3\u201333","journal-title":"Algorithmica"},{"key":"19_CR29","unstructured":"Schachinger W.: Beitr\u00e4ge zur Analyse von Datenstrukturen zur Digitalen Suche. Dissertation Technische Universit\u00e4t Wien, Vienna (1993)"},{"key":"19_CR30","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0304-3975(91)90050-C","volume":"85","author":"W. Szpankowski","year":"1991","unstructured":"Szpankowski W. (1991) A characterization of digital search trees from the successful search viewpoint. Theor. Comput. Sci. 85, 117\u2013134","journal-title":"Theor. Comput. Sci."},{"key":"19_CR31","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032770","volume-title":"Average Case Analysis of Algorithms on Sequences","author":"W. Szpankowski","year":"2001","unstructured":"Szpankowski W. (2001) Average Case Analysis of Algorithms on Sequences. Wiley, New York"},{"key":"19_CR32","volume-title":"Chemical Graph Theory","author":"N. Trinajsti\u0107","year":"1992","unstructured":"Trinajsti\u0107 N. (1992) Chemical Graph Theory. CRC Press, Boca Raton FL"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-006-0019-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-006-0019-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-006-0019-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T09:41:53Z","timestamp":1558690913000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-006-0019-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9,22]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,10,17]]}},"alternative-id":["19"],"URL":"https:\/\/doi.org\/10.1007\/s00236-006-0019-7","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9,22]]}}}