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.
Mots-clés : average-case analysis of data-structures, information theory, trie, Mellin analysis
@article{ITA_2001__35_2_163_0,
author = {Bourdon, J\'er\'emie and Nebel, Markus and Vall\'ee, Brigitte},
title = {On the stack-size of general tries},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {163--185},
publisher = {EDP-Sciences},
volume = {35},
number = {2},
year = {2001},
mrnumber = {1862461},
zbl = {1016.68064},
language = {en},
url = {http://www.numdam.org/item/ITA_2001__35_2_163_0/}
}
TY - JOUR AU - Bourdon, Jérémie AU - Nebel, Markus AU - Vallée, Brigitte TI - On the stack-size of general tries JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2001 SP - 163 EP - 185 VL - 35 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_2001__35_2_163_0/ LA - en ID - ITA_2001__35_2_163_0 ER -
%0 Journal Article %A Bourdon, Jérémie %A Nebel, Markus %A Vallée, Brigitte %T On the stack-size of general tries %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2001 %P 163-185 %V 35 %N 2 %I EDP-Sciences %U http://www.numdam.org/item/ITA_2001__35_2_163_0/ %G en %F ITA_2001__35_2_163_0
Bourdon, Jérémie; Nebel, Markus; Vallée, Brigitte. On the stack-size of general tries. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 2, pp. 163-185. http://www.numdam.org/item/ITA_2001__35_2_163_0/
[1] , and, Dynamical Sources in Information Theory: A General Analysis of Trie Structures. Algorithmica 29 (2001) 307-369. | MR | Zbl
[2] , and, An average-case analysis of the Gaussian algorithm for lattice reduction. Combina. Probab. Comput. 6 (1997) 397-433. | MR | Zbl
[3] , and, The average height of planted plane trees, Graph Theory and Computing. Academic Press (1972) 15-22. | MR | Zbl
[4] and, On the Horton-Strahler number for Random Tries. RAIRO: Theoret. Informatics Appl. 30 (1996) 443-456. | Numdam | Zbl
[5] , On the performance of evaluation of extendible hashing and trie searching. Acta Informatica 20 (1983) 345-369. | MR | Zbl
[6] , and, Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci. 144 (1995) 3-58. | MR | Zbl
[7] and, Partial match retrieval of multidimensional data. J. ACM 33 (1986) 371-407. | MR
[8] , Trie Memory. Comm. ACM 3 (1990) 490-500.
[9] and, Handbook of Algorithms and Data Structures: in Pascal and C. Addison-Wesley (1991). | Zbl
[10] , Produit tensoriels topologiques et espaces nucléaires. Mem. Amer. Math. Soc. 16 (1955). | MR | Zbl
[11] , La Théorie de Fredholm. Bull. Soc. Math. France 84, 319-384. | Numdam | MR | Zbl
[12] and, Analytical Depoissonization and its Applications. Theoret. Comput. Sci. 201 in “Fundamental Study” (1998) 1-62. | Zbl
[13] and, On the Recursion Depth of Special Tree Traversal Algorithms. Inform. and Comput. 74 (1987) 15-32. | MR | Zbl
[14] , The average height of -tuply rooted planted plane trees. Computing 25 (1980) 209-232. | MR | Zbl
[15] , The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley (1973). | MR | Zbl
[16] M; Krasnoselskii, Positive solutions of operator equations. P. Noordhoff, Groningen (1964). | MR | Zbl
[17] , Evolution of Random Search Trees. Wiley-Interscience Series (1992). | MR | Zbl
[18] , The Stack-Size of Tries, a Combinatorial Study. Theoret. Comput. Sci. (to appear). | MR | Zbl
[19] , The Stack-Size of Uniform Random Tries Revisited (submitted).
[20] , On the Horton-Strahler Number for Combinatorial Tries. RAIRO: Theoret. Informatics Appl. 34 (2000) 279-296. | Numdam | MR | Zbl
[21] , Trie hashing analysis, in Proc. 4th Int.Conf. Data Eng.. Los Angeles, CA (1988) 377-387.
[22] , On the average height of trees in in digital search and dynamic hashing. Inform. Process. Lett. 13 (1982) 64-66. | MR | Zbl
[23] , Partial match retrieval algorithms. SIAM J. Comput. 5 (1976) 19-50. | MR | Zbl
[24] , Algorithms. Addison-Wesley (1988). | Zbl
[25] , On the height of digital trees and related problem. Algorithmica 6 (1991) 256-277. | MR | Zbl
[26] , Some results on -ary asymmetric tries. J. Algorithms 9 (1988) 224-244. | Zbl
[27] , Set representation and set intersection, Technical Report. Stanford University (1998).
[28] , Dynamical Sources in Information Theory: Fundamental Intervals and Word Prefixes. Algorithmica 29 (2001) 162-306. | MR | Zbl
[29] , Trees Everywhere, in Proc. CAAP'90. Springer, Lecture Notes in Comput. Sci. 431 (1990) 18-41. | Zbl
[30] , A note on the analysis of extendible hashing. Inform. Process. Lett. 11 (1980) 84-86. | MR | Zbl
