On the stack-size of general tries
Bourdon, Jérémie ; Nebel, Markus ; Vallée, Brigitte
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 163-185 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2001-01-01
Classification:  68P05,  68W40,  94A15 
@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},
     volume = {35},
     year = {2001},
     pages = {163-185},
     mrnumber = {1862461},
     zbl = {1016.68064},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 163-185. http://gdmltest.u-ga.fr/item/ITA_2001__35_2_163_0/

[1] J. Clément, P. Flajolet and B. Vallée, Dynamical Sources in Information Theory: A General Analysis of Trie Structures. Algorithmica 29 (2001) 307-369. | MR 1887308 | Zbl 1035.68039

[2] H. Daudé, P. Flajolet and B. Vallée, An average-case analysis of the Gaussian algorithm for lattice reduction. Combina. Probab. Comput. 6 (1997) 397-433. | MR 1483426 | Zbl 0921.11072

[3] 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. | MR 505710 | Zbl 0247.05106

[4] L. Devroye and P. Kruszewski, On the Horton-Strahler number for Random Tries. RAIRO: Theoret. Informatics Appl. 30 (1996) 443-456. | Numdam | Zbl 0867.68087

[5] P. Flajolet, On the performance of evaluation of extendible hashing and trie searching. Acta Informatica 20 (1983) 345-369. | MR 732311 | Zbl 0515.68048

[6] P. Flajolet, X. Gourdon and P. Dumas, Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci. 144 (1995) 3-58. | MR 1337752 | Zbl 0869.68057

[7] P. Flajolet and C. Puech, Partial match retrieval of multidimensional data. J. ACM 33 (1986) 371-407. | MR 835110

[8] E.H. Fredkin, Trie Memory. Comm. ACM 3 (1990) 490-500.

[9] G.H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data Structures: in Pascal and C. Addison-Wesley (1991). | Zbl 0719.68001

[10] A. Grothendieck, Produit tensoriels topologiques et espaces nucléaires. Mem. Amer. Math. Soc. 16 (1955). | MR 75539 | Zbl 0064.35501

[11] A. Grothendieck, La Théorie de Fredholm. Bull. Soc. Math. France 84, 319-384. | Numdam | MR 88665 | Zbl 0073.10101

[12] P. Jacquet and W. Szpankowski, Analytical Depoissonization and its Applications. Theoret. Comput. Sci. 201 in “Fundamental Study” (1998) 1-62. | Zbl 0902.68087

[13] P. Kirschenhofer and H. Prodinger, On the Recursion Depth of Special Tree Traversal Algorithms. Inform. and Comput. 74 (1987) 15-32. | MR 895267 | Zbl 0625.68048

[14] R. Kemp, The average height of r-tuply rooted planted plane trees. Computing 25 (1980) 209-232. | MR 620394 | Zbl 0433.05024

[15] D.E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley (1973). | MR 445948 | Zbl 0302.68010

[16] M; Krasnoselskii, Positive solutions of operator equations. P. Noordhoff, Groningen (1964). | MR 181881 | Zbl 0121.10604

[17] H.M. Mahmoud, Evolution of Random Search Trees. Wiley-Interscience Series (1992). | MR 1140708 | Zbl 0762.68033

[18] M.E. Nebel, The Stack-Size of Tries, a Combinatorial Study. Theoret. Comput. Sci. (to appear). | MR 1871080 | Zbl 0988.68137

[19] M.E. Nebel, The Stack-Size of Uniform Random Tries Revisited (submitted).

[20] M.E. Nebel, On the Horton-Strahler Number for Combinatorial Tries. RAIRO: Theoret. Informatics Appl. 34 (2000) 279-296. | Numdam | MR 1809861 | Zbl 0966.05019

[21] M. Régnier, Trie hashing analysis, in Proc. 4th Int.Conf. Data Eng.. Los Angeles, CA (1988) 377-387.

[22] M. Régnier, On the average height of trees in in digital search and dynamic hashing. Inform. Process. Lett. 13 (1982) 64-66. | MR 645811 | Zbl 0472.68058

[23] R.L. Rivest, Partial match retrieval algorithms. SIAM J. Comput. 5 (1976) 19-50. | MR 395398 | Zbl 0331.68064

[24] R. Sedgewick, Algorithms. Addison-Wesley (1988). | Zbl 0717.68005

[25] W. Szpankowski, On the height of digital trees and related problem. Algorithmica 6 (1991) 256-277. | MR 1093014 | Zbl 0711.68035

[26] W. Szpankowski, Some results on V-ary asymmetric tries. J. Algorithms 9 (1988) 224-244. | Zbl 0637.68072

[27] L. Trabb Pardo, Set representation and set intersection, Technical Report. Stanford University (1998).

[28] B. Vallée, Dynamical Sources in Information Theory: Fundamental Intervals and Word Prefixes. Algorithmica 29 (2001) 162-306. | MR 1887307 | Zbl 1009.94003

[29] X.G. Viennot, Trees Everywhere, in Proc. CAAP'90. Springer, Lecture Notes in Comput. Sci. 431 (1990) 18-41. | Zbl 0785.68092

[30] A. Yao, A note on the analysis of extendible hashing. Inform. Process. Lett. 11 (1980) 84-86. | MR 589964 | Zbl 0447.68077