Patricia tries again revisited

ABSTRACT

The Patricia trie is a simple modification of a regular trie. By eliminating unary branching nodes, the Patricia achieves better performance than regular tries. However, the question is: how much on the average is the Patricia better? This paper offers a thorough answer to this question by considering some statistics of the number of nodes examined in a successful search and an unsuccessful search in the Patricia tries. It is shown that for the Patricia containing n records the average of the successful search length Sn asymptotically becomes 1/h1 · ln n + O(1), and the variance of Sn is either var Sn = c · ln n + 0(1) for an asymmetric Patricia or var Sn = 0(1) for a symmetric Patricia, where h1 is the entropy of the alphabet over which the Patricia is built and c is an explicit constant. Higher moments of Sn are also assessed. The number of nodes examined in an unsuccessful search Un is studied only for binary symmetric Patricia tries. We prove that the mth moment of the unsuccessful search length EUmn satisfies limn→∞ EUmn/logm2n = 1, and the variance of Un is var Un = 0.87907. These results suggest that Patricia tries are very well balanced trees in the sense that a random shape of Patriciatries resembles the shape of complete trees that are ultimately balanced trees.

REFERENCES

• 1: ABRAMOWITZ, M., AND STEGUN, I. Handbook of Mathematical Functions. Wiley, New York, 1972.
• 2: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 3: BERNDT, B. Ramanujan's Notebooks. Springer-Verlag, New York, 1985.
• 4: ERDELYI, A. Higher Transcendental Functions. McGraw-Hill, New York, 1953.
• 5: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 6: FLAJOLET, PH. On the performance evaluation of extendible hashing and trie searching. Acta Inf. 20 (1983), 345-369.
• 7: Philippe Flajolet , Nasser Saheb, The complexity of generating an exponentially distributed variate, Journal of Algorithms, v.7 n.4, p.463-488, Dec. 1986 [doi>10.1016/0196-6774(86)90014-3]
• 8: Philippe Flajolet , Robert Sedgewick, Digital search trees revisited, SIAM Journal on Computing, v.15 n.3, p.748-767, August 1986 [doi>10.1137/0215054]
• 9: GALLAGER, R. Conflict resolution in random access broadcast networks. In Proceedings of the AFOSR Workshop in Communication Theory and Applications. Provincetown, Mass., 1978, pp. 74-76.
• 10: Gaston H. Gonnet, Handbook of Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 11: Peter Henrici, Applied and computational complex analysis. Vol. 3: discrete Fourier analysis—Cauchy integrals—construction of conformal maps---univalent functions, John Wiley & Sons, Inc., New York, NY, 1986
• 12: JACQUET, PH., AND REGNIER, M. Limiting distributions for trie parameters. In Lecture Notes in Computer Science, vol. 214. Springer-Verlag, New York, 1986, pp. 196-210.
• 13: P Kirschenhofer , H Prodinger, Some further results on digital search trees, International Colloquium on Automata, Languages and Programming on Automata, languages and programming, p.177-185, September 1986, Rennes, France
• 14: 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
• 15: NORLUND, N.E. Memoire sur les polynomes de Bernoulli. Acta Math. 43 (1923), 124-196.
• 16: PAIGE, R., AND TARJAN, R. Three efficient algorithms based on partition refinements, preprint.
• 17: PITTEL, B. Asymptotical growth of a class of random trees. Ann. Prob. 13 (1985), 414-427.
• 18: RIORDAN, J. Combinatorial Identities. Wiley, New York, 1968.
• 19: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 20: SZPANKOWSHI, W. Patricia tries again revisited. Tech. Rep. CSD-TR 625. Dept. Comput. Sci., Purdue Univ., West Lafayette, Ind., 1986.
• 21: SZPANKOWSKI, W. On the recurrence equation arising in the analysis of conflict resolution algorithms. Stochastic Models 3 (1987), 89- l 14.
• 22: Wojciech Szpankowski, Solution of a linear recurrence equation arising in the analysis of some algorithms, SIAM Journal on Algebraic and Discrete Methods, v.8 n.2, p.233-250, April 1, 1987 [doi>10.1137/0608021]
• 23: Wojciech Szpankowski, The evaluation of an alternative sum with applications to the analysis of some data structures, Information Processing Letters, v.28 n.1, p.13-19, May 30, 1988 [doi>10.1016/0020-0190(88)90137-8]
• 24: Wojciech Szpankowski, Some results on V-ary asymmetric tries, Journal of Algorithms, v.9 n.2, p.224-244, June 1988 [doi>10.1016/0196-6774(88)90039-9]
• 25: WHITTAKER, E., AND WATSON, G. A Course of Modern Analysis. Cambridge Press, London, 1935.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Recurrences and difference equations; Generating functions
      G.2.2 Graph Theory
          Subjects: Trees

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Performance