×

On the stack-size of general tries. (English) Zbl 1016.68064

Summary: 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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68P05 Data structures
68P10 Searching and sorting
68W40 Analysis of algorithms
94A15 Information theory (general)
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML Link

References:

[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 · Zbl 1035.68039 · doi:10.1007/s004530010064
[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 · Zbl 0921.11072 · doi:10.1017/S0963548397003258
[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 · 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 · 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 · Zbl 0515.68048 · doi:10.1007/BF00264279
[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 · Zbl 0869.68057 · doi:10.1016/0304-3975(95)00002-E
[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 · Zbl 0719.68001
[10] A. Grothendieck , Produit tensoriels topologiques et espaces nucléaires . Mem. Amer. Math. Soc. 16 ( 1955 ). MR 75539 | Zbl 0064.35501 · Zbl 0064.35501
[11] A. Grothendieck , La Théorie de Fredholm . Bull. Soc. Math. France 84, 319 - 384 . Numdam | MR 88665 | Zbl 0073.10101 · 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 · Zbl 0902.68087 · doi:10.1016/S0304-3975(97)00167-9
[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 · Zbl 0625.68048 · doi:10.1016/0890-5401(87)90009-5
[14] R. Kemp , The average height of \(r\)-tuply rooted planted plane trees . Computing 25 ( 1980 ) 209 - 232 . MR 620394 | Zbl 0433.05024 · Zbl 0433.05024 · doi:10.1007/BF02242000
[15] D.E. Knuth , The Art of Computer Programming , Vol. 3: Sorting and Searching. Addison-Wesley ( 1973 ). MR 445948 | Zbl 0302.68010 · Zbl 0302.68010
[16] M; Krasnoselskii, Positive solutions of operator equations. P. Noordhoff, Groningen (1964). MR 181881 | Zbl 0121.10604 · Zbl 0121.10604
[17] H.M. Mahmoud , Evolution of Random Search Trees . Wiley-Interscience Series ( 1992 ). MR 1140708 | Zbl 0762.68033 · 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 · Zbl 0988.68137 · doi:10.1016/S0304-3975(00)00416-3
[19] M.E. Nebel , The Stack-Size of Uniform Random Tries Revisited (submitted). · Zbl 0995.68071
[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 · Zbl 0966.05019 · doi:10.1051/ita:2000117
[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 · Zbl 0472.68058 · doi:10.1016/0020-0190(81)90033-8
[23] R.L. Rivest , Partial match retrieval algorithms . SIAM J. Comput. 5 ( 1976 ) 19 - 50 . MR 395398 | Zbl 0331.68064 · Zbl 0331.68064 · doi:10.1137/0205003
[24] R. Sedgewick , Algorithms . Addison-Wesley ( 1988 ). Zbl 0717.68005 · 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 · Zbl 0711.68035 · doi:10.1007/BF01759045
[26] W. Szpankowski , Some results on \(V\)-ary asymmetric tries . J. Algorithms 9 ( 1988 ) 224 - 244 . Zbl 0637.68072 · Zbl 0637.68072 · doi:10.1016/0196-6774(88)90039-9
[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 · Zbl 1009.94003 · doi:10.1007/s004530010061
[29] X.G. Viennot , Trees Everywhere , in Proc. CAAP’90. Springer, Lecture Notes in Comput. Sci. 431 ( 1990 ) 18 - 41 . Zbl 0785.68092 · 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 · Zbl 0447.68077 · doi:10.1016/0020-0190(80)90008-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.