Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-30T23:16:29.105Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Stack-Size of General Tries

Published online by Cambridge University Press:  15 April 2002

Jérémie Bourdon ,
Markus Nebel  and
Brigitte Vallée
Jérémie Bourdon
Affiliation:
GREYC, Université de Caen, 14032 Caen, France; ([email protected])
Markus Nebel
Affiliation:
FB Informatik, Johann Wolfgang Goethe-Universität, 60054 Frankfurt a. M., Germany; ([email protected])
Brigitte Vallée
Affiliation:
GREYC, Université de Caen, 14032 C aen, France; ([email protected])
Get access

Abstract

Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural assumptions that encompass all commonly used data models (and more), we obtain a precise average-case and probabilistic analysis of stack-size. Furthermore, we study the dependency between the stack-size and the ordering on symbols in the alphabet: we establish that, when the source emits independent symbols, the optimal ordering arises when the most probable symbol is the last one in this order.

Keywords

Average-case analysis of data-structuresinformation theorytrieMellin analysis.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 35 , Issue 2 , March 2001 , pp. 163 - 185
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Clément, J., Flajolet, P. and Vallée, B., Dynamical Sources in Information Theory: A General Analysis of Trie Structures. Algorithmica 29 (2001) 307-369. CrossRef
Daudé, H., Flajolet, P. and Vallée, B., An average-case analysis of the Gaussian algorithm for lattice reduction. Combina. Probab. Comput. 6 (1997) 397-433. CrossRef
N.G. De Bruijn, D.E. Knuth and S.O. Rice, The average height of planted plane trees, Graph Theory and Computing. Academic Press (1972) 15-22.
Devroye, L. and Kruszewski, P., On the Horton-Strahler number for Random Tries. RAIRO: Theoret. Informatics Appl. 30 (1996) 443-456.
Flajolet, P., On the performance of evaluation of extendible hashing and trie searching. Acta Informatica 20 (1983) 345-369. CrossRef
Flajolet, P., Gourdon, X. and Dumas, P., Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci. 144 (1995) 3-58. CrossRef
Flajolet, P. and Puech, C., Partial match retrieval of multidimensional data. J. ACM 33 (1986) 371-407. CrossRef
Fredkin, E.H., Trie Memory. Comm. ACM 3 (1990) 490-500. CrossRef
G.H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data Structures: in Pascal and C. Addison-Wesley (1991).
A. Grothendieck, Produit tensoriels topologiques et espaces nucléaires. Mem. Amer. Math. Soc. 16 (1955).
A. Grothendieck, La Théorie de Fredholm. Bull. Soc. Math. France 84 , 319-384.
P. Jacquet and W. Szpankowski, Analytical Depoissonization and its Applications. Theoret. Comput. Sci. 201 in ``Fundamental Study'' (1998) 1-62.
Kirschenhofer, P. and Prodinger, H., On the Recursion Depth of Special Tree Traversal Algorithms. Inform. and Comput. 74 (1987) 15-32. CrossRef
R. Kemp, The average height of
D.E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley (1973).
M; Krasnoselskii, Positive solutions of operator equations. P. Noordhoff, Groningen (1964).
H.M. Mahmoud, Evolution of Random Search Trees. Wiley-Interscience Series (1992).
M.E. Nebel, The Stack-Size of Tries, a Combinatorial Study. Theoret. Comput. Sci. (to appear).
M.E. Nebel, The Stack-Size of Uniform Random Tries Revisited (submitted).
Nebel, M.E., On the Horton-Strahler Number for Combinatorial Tries. RAIRO: Theoret. Informatics Appl. 34 (2000) 279-296.
M. Régnier, Trie hashing analysis, in Proc. 4th Int.Conf. Data Eng.. Los Angeles, CA (1988) 377-387.
Régnier, M., On the average height of trees in in digital search and dynamic hashing. Inform. Process. Lett. 13 (1982) 64-66. CrossRef
Rivest, R.L., Partial match retrieval algorithms. SIAM J. Comput. 5 (1976) 19-50. CrossRef
R. Sedgewick, Algorithms. Addison-Wesley (1988).
Szpankowski, W., On the height of digital trees and related problem. Algorithmica 6 (1991) 256-277. CrossRef
W. Szpankowski, Some results on
L. Trabb Pardo, Set representation and set intersection, Technical Report. Stanford University (1998).
Vallée, B., Dynamical Sources in Information Theory: Fundamental Intervals and Word Prefixes. Algorithmica 29 (2001) 162-306. CrossRef
X.G. Viennot, Trees Everywhere, in Proc. CAAP'90. Springer, Lecture Notes in Comput. Sci. 431 (1990) 18-41.
Yao, A., A note on the analysis of extendible hashing. Inform. Process. Lett. 11 (1980) 84-86. CrossRef