Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

A digital search tree (DST) -- one of the most fundamental data structures on words -- is a digital tree in which keys (strings, words) are stored directly in (internal) nodes. Such trees find myriad of applications from the popular Lempel-Ziv'78 data compression scheme to distributed hash tables. The profile of a DST measures the number of nodes at the same distance from the root; it is a function of the number of stored strings and the distance from the root. Most parameters of DST (e.g., height, fill-up) can be expressed in terms of the profile. However, from the inception of DST, the analysis of the profile has been elusive and it has become a prominent open problem in the area of analysis of algorithms. We make here the first, but decisive, step towards solving this problem. We present a precise analysis of the average profile when stored strings are generated by a biased memoryless source. The main technical difficulty of analyzing the profile lies in solving a sophisticated recurrence equation. We present such a solution for the Poissonized version of the problem (i.e., when the number of stored strings is generated by a Poisson distribution) in the Mellin transform domain. To accomplish it, we introduce a novel functional operator that allows us to express the solution in an explicit form, and then using analytic algorithmics tools to extract the asymptotic behavior of the profile. This analysis is surprisingly demanding but once it is carried out it reveals unusually intriguing and interesting behavior. The average profile undergoes several phase transitions when moving from the root to the longest path. At first, it resembles a full tree until it abruptly starts growing polynomially and it oscillates in this range. Our results are derived by methods of analytic algorithmics such as generating functions, Mellin transform, Poissonization and de-Poissonization, the saddle-point method, singularity analysis and uniform asymptotic analysis.

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 and H.-K. Hwang, Width and mode of the profile for some random trees of logarithmic height, Ann. Appl. Probab., 16, 886--918, 2006.
• 3: Philippe Flajolet , Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, New York, NY, 2009
• 4: Philippe Jacquet , Wojciech Szpankowski, Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees, Theoretical Computer Science, v.144 n.1-2, p.161-197, June 26, 1995 [doi>10.1016/0304-3975(94)00298-W]
• 5: C. Knessl, and W. Szpankowski, On the Average Profile of Symmetric Digital Search Trees, preprint, 2008.
• 6: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 7: G. Louchard, Exact and Asymptotic Distributions in Digital and Binary Search Trees, RAIRO Theoretical Inform. Applications, 21, 479--495, 1987.
• 8: G. Louchard and W. Szpankowski, Average Profile and Limiting Distribution for a Phrase Size in the Lempel-Ziv Parsing Algorithm, IEEE Trans. Information Theory, 41, 478--488, 1995.
• 9: Moni Naor , Udi Wieder, Novel architectures for P2P applications: the continuous-discrete approach, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777421]
• 10: Gahyun Park , Wojciech Szpankowski, Towards a complete characterization of tries, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 11: Gahyun Park , Wojciech Szpankowski, Profile of tries, Purdue University, West Lafayette, IN, 2006
• 12: G. Park, H. K. Hwang, P. Nicodeme, and W. Szpankowski, Profile of Tries, SIAM J. Computing, to appear; also Proc. LATIN'08, LNCS 4957, 1--11, 2008.
• 13: B. Pittel, Asymptotic Growth of a Class of Random Trees, Annals of Probability, 18, 414--427, 1985.
• 14: Helmut Prodinger, Digital Search Trees and Basic Hypergeometric Functions, Bulletin of the EATCS, 56, 1995.
• 15: Robert Sedgewick, Algorithms in C, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 16: Wojciech Szpankowski, A characterization of digital search trees from the successful search viewpoint, Theoretical Computer Science, v.85 n.1, p.117-134, Aug. 5, 1991 [doi>10.1016/0304-3975(91)90050-C]
• 17: Wojciech Szpankowski, Average Case Analysis of Algorithms on Sequences, John Wiley & Sons, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies