{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:47Z","timestamp":1725663647848},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540194880"},{"type":"electronic","value":"9783540392910"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-19488-6_124","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:13:23Z","timestamp":1330200803000},"page":"302-316","source":"Crossref","is-referenced-by-count":1,"title":["Do we really need to balance patricia tries?"],"prefix":"10.1007","author":[{"given":"Peter","family":"Kirschenhofer","sequence":"first","affiliation":[]},{"given":"Helmut","family":"Prodinger","sequence":"additional","affiliation":[]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"22_CR1","unstructured":"Aho, A., Hopcroft, J. and Ullman, J., Data Structures and Algorithms, Addison-Wesley (1983)."},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/320083.320092","volume":"4","author":"R. Fagin","year":"1979","unstructured":"Fagin, R., Nievergelt, J., Pippenger, N. and Strong, H., Extendible hashing: A fast access method for dynamic files, ACM TODS, 4, pp. 315\u2013344 (1979)","journal-title":"ACM TODS"},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1137\/0215054","volume":"15","author":"P. Flajolet","year":"1986","unstructured":"Flajolet, Ph. and Sedgewick, R., Digital search trees revisited, SIAM J. Comput., 15, pp. 748\u2013767 (1986).","journal-title":"SIAM J. Comput."},{"key":"22_CR4","unstructured":"Gonnet, G., Handbook of algorithms and data structures, Addison-Wesley (1986)."},{"key":"22_CR5","volume-title":"Applied and computational complex analysis","author":"P. Henrici","year":"1977","unstructured":"Henrici, P., Applied and computational complex analysis, John Wiley & Sons, New York (1977)."},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Kirschenhofer, P. and Prodinger, H., Some further results on digital search trees in: Automata, Languages and Machines (ICALP'86) (L. Kott ed.), pp. 177\u2013185, Springer Lecture Notes in Computer Science 226 (1986).","DOI":"10.1007\/3-540-16761-7_67"},{"key":"22_CR7","unstructured":"Kirschenhofer, P. and Prodinger, H., On some applications of formulae of Ramanujan in the analysis of algorithms, preprint."},{"key":"22_CR8","unstructured":"Kirschenhofer, P., Prodinger, H. and Szpankowski, W., On the variance of the external path length in a symmetric digital trie, Combinatorics and Complexity Conference, Abstracts, pp. 53\u201354, Chicago (1987) (also submitted to a journal)."},{"key":"22_CR9","unstructured":"Knuth, D., The art of computer programming. Sorting and searching. Addison-Wesley (1973)."},{"issue":"2","key":"22_CR10","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1109\/TIT.1985.1057013","volume":"IT-31","author":"P. Mathys","year":"1985","unstructured":"Mathys, P. and Flajolet, P., Q-ary collision resolution algorithms in random-access system with free and blocked channel access, IEEE Trans. Information Theory, vol. IT-31, 2, pp. 217\u2013243 (1985).","journal-title":"IEEE Trans. Information Theory"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Szpankowski, W., Some results on V-ary asymmetric tries, Journal of Algorithms, 9 (1988).","DOI":"10.1016\/0196-6774(88)90039-9"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Szpankowski, W., The evaluation of an alternative sum with applications to the analysis of some data structures, Information Processing Letters, (1988).","DOI":"10.1016\/0020-0190(88)90137-8"},{"key":"22_CR13","unstructured":"Szpankowski, W., Patricia tries again revisited, Purdue University, CSD-TR 625 (1986) (also submitted to a journal)."},{"key":"22_CR14","unstructured":"Paige, R. and Tarjan, R., Three efficient algorithms based on partition refinement, (preprint) (1986)."},{"key":"22_CR15","unstructured":"Riordan, J., Combinatorial Identities, John Wiley & Sons (1968)."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-19488-6_124.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:56:00Z","timestamp":1619556960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19488-6_124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194880","9783540392910"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-19488-6_124","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}