Towards a complete characterization of tries

ABSTRACT

Tries and suffix trees are the most popular data structures on words. Tries were introduced in 1960 by Fredkin as an efficient method for searching and sorting digital data. Since then myriad of novel trie applications were found such as dynamic hashing, conflict resolution algorithms, leader election algorithms, IP addresses lookup, coding, polynomial factorization, Lempel-Ziv compression schemes, and so on. Furthermore, various analyses of tries reveal new fundamental properties of strings appearing in those applications. Parameters of interest are the (partial) fillup level (the largest full level of the trie), shortest path, height (longest path), typical depth, and path length (sum of depths). All of these parameters are analyzed here in a unifying manner by studying the external and internal profiles. A profile of a tree at level k is the number of nodes (internal or external) at level k. We derive recurrences for both profiles and solve them asymptotically for various ranges of k when the strings stored in the trie are generated by a memoryless source (extension to a Markov source is possible). In particular, we present asymptotic results for the average profile, the variance and the limiting distribution. As consequences we find the height, shortest path, fillup level, and the depth. These results are derived here by methods of analytic algorithmics such as generating functions, Mellin transform, poissonization and depoissonization, and the saddle point method.

REFERENCES

• 1: L. Devroye, A Study of Trie-Like Structures Under the Density Model, Annals of Applied Probability, 2, 402--434, 1992.
• 2: L. Devroye, A Note on the Probabilistic Analysis of Patricia Tries, Random Structures & Algorithms, 3, 203--214, 1992.
• 3: Luc Devroye, Analysis of random LC tries, Random Structures & Algorithms, v.19 n.3-4, p.359-375, October-December 2001 [doi>10.1002/rsa.10006]
• 4: Philippe Flajolet , Xavier Gourdon , Philippe Dumas, Mellin transforms and asymptotics: harmonic sums, Theoretical Computer Science, v.144 n.1-2, p.3-58, June 26, 1995 [doi>10.1016/0304-3975(95)00002-E]
• 5: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 6: P. Jacquet, and W. Szpankowski, Analysis of Digital Tries with Markovian Dependency, IEEE Trans. Information Theory, 37, 1470--1475, 1991.
• 7: Philippe Jacquet , Wojciech Szpankowski, Autocorrelation on words and its applications: analysis of suffix trees by string-ruler approach, Journal of Combinatorial Theory Series A, v.66 n.2, p.237-269, May 1994 [doi>10.1016/0097-3165(94)90065-5]
• 8: Philippe Jacquet , Wojciech Szpankowski, Analytical depoissonization and its applications, Theoretical Computer Science, v.201 n.1-2, p.1-62, July 6, 1998 [doi>10.1016/S0304-3975(97)00167-9]
• 9: S. Janson and W. Szpankowski, Analysis of an Asymmetric Leader Election Algorithm, The Electronic Journal of Combinatorics64(1), R17, 1--16, 1997.
• 10: P. Kirschenhofer , H. Prodinger , W. Szpankowski, On the variance of the external path length in a symmetric digital trie, Discrete Applied Mathematics, v.25 n.1-2, p.129-143, 1989 [doi>10.1016/0166-218X(89)90050-4]
• 11: Charles Knessl , Wojciech Szpankowski, On the number of full levels in tries, Random Structures & Algorithms, v.25 n.3, p.247-276, October 2004 [doi>10.1002/rsa.20023]
• 12: D. E. Knuth, Fundamental Algorithms, 3rd ed. (Reading, Massachusetts: Addison Wesley, 1997).
• 13: Donald E. Knuth, Selected papers on analysis of algorithms, CSLI Publications, Stanford, CA, 2000
• 14: H. Mahmoud, Evolution of Random Search Trees, John Wiley & Sons, New York, 1992.
• 15: S. Nilsson, Radix Sorting & Searching, PhD Thesis, Lund University, 1996.
• 16: B. Pittel, Asymptotic Growth of a Class of Random Trees, Annals of Probability, 18, 414--427, 1985.
• 17: B. Pittel, Paths in a Random Digital Tree: Limiting Distributions, Adv. in Applied Probability, 18, 139--155, 1986.
• 18: Yuriy A. Reznik, Some results on tries with adaptive branching, Theoretical Computer Science, v.289 n.2, p.1009-1026, 30 October 2002 [doi>10.1016/S0304-3975(01)00415-7]
• 19: Robert Sedgewick , Philippe Flajolet, An introduction to the analysis of algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 20: V. Srinivasan , George Varghese, Faster IP lookups using controlled prefix expansion, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.1-10, June 22-26, 1998, Madison, Wisconsin, United States
• 21: W. Szpankowski, On the Height of Digital Trees and Related Problems, Algorithmica, 6, 256--277, 1991.
• 22: Wojciech Szpankowski, Average Case Analysis of Algorithms on Sequences, John Wiley & Sons, Inc., New York, NY, 2001