zbMATH — the first resource for mathematics

A characterization of digital search trees from the successful search viewpoint. (English) Zbl 0746.68027
The author is interested in studying the average complexity of the successful search in digital trees. He assumes that a sequence of elements is an independent sequence of Bernoulli trials and that the \(i\)- th digit in a key occurs independently of the other digits. In previous papers, the author has investigated radix search trees and Patricia tries from this point of view. He uses the method of generating functions and establishes a relationship between the derivatives of a generating function, defined by a rather sophisticated recurrence equation, and the moments of a successful search. It is well-known that the number of digits examined during a random successful search is \(c_ 1\log n+O(1)\). By solving the recurrence asymptotically, the author gets a more precise characterization of the form \(c_ 1\log n+c_ 2+O(\log n/n)\). Finally, he compares the three types of digital trees: The best constant in the mean value is achieved for the digital search tree, whereas the best variance is for Patricia tries. Unfortunately, the paper is not self- contained and, therefore, difficult to read.

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Abramowitz, M.; Stegun, I., Handbook of mathematical functions, (1964), Dover New York · Zbl 0171.38503
[2] Aho, A.; Hopcroft, J.; Ullman, J., Data structures and algorithms, (1983), Addison-Wesley Reading, MA
[3] Berger, T., Poisson multiple access for packet broadcast channels, IEEE trans. inform. theory, IT-30, 745-751, (1984) · Zbl 0553.94002
[4] Fagin, R.; Nievergelt, J.; Pippenger, N.; Strong, H., Extendible hashing: A fast access method for dynamic files, ACM trans. database systems, 4, 315-344, (1979)
[5] Flajolet, Ph., On the performance evaluation of extendible hashing and trie searching, Acta inform., 20, 345-369, (1983) · Zbl 0515.68048
[6] Flajolet, Ph.; Sedgewick, R., Digital search trees revisited, SIAM J. comput., 15, 748-767, (1986) · Zbl 0611.68041
[7] Flajolet, Ph.; Puech, C., Partial match retrieval of multidimensional data, J. assoc. comput. Mach., 33, 371-407, (1987)
[8] Frdelyi, A., Higher transcendental functions, (1953), McGraw-Hill New York
[9] Gallager, R., Conflict resolution in a random access broadcast networks, Proc. AFOSR workshop in communication theory and applications, 74-76, (1978)
[10] Gonnet, G., Handbook of algorithms and data structures, (1984), Addison-Wesley Reading, MA · Zbl 0665.68001
[11] Henrici, P., Applied and computational complex analysis, (1977), Wiley New York · Zbl 0377.30002
[12] Jacquet, Ph.; Regnier, M., (), 196-210
[13] Kirschenhofer, P.; Prodinger, H., Some further results on digital trees, (), 177-185
[14] Kirschenhofer, P.; Prodinger, H.; Szpankowski, W., On the variance of the external path length in a symmetric digital trie, Discrete appl. math., 25, 129-143, (1989) · Zbl 0685.68059
[15] Knuth, D., The art of computer programming. sorting and searching, (1973), Addison-Wesley Reading, MA · Zbl 0302.68010
[16] Pittel, B., Paths in a random digital tree: limiting distributions, Adv. in appl. probab., 18, 139-155, (1986) · Zbl 0588.60012
[17] Riordan, J., Combinatorial identities, (1968), Wiley New York · Zbl 0194.00502
[18] Szpankowski, W., How much on the average is the patricia trie better, Proc. 24th ann. allerton conf., 314-323, (1986)
[19] Szpankowski, W., Patricia tries again revisited, J. assoc. comput. Mach., 37, 691-711, (1990) · Zbl 0711.68065
[20] Szpankowski, W., The evaluation of an alternative sum with applications to the analysis of some data structures, Inform. process. lett., 28, 13-19, (1988) · Zbl 0657.68071
[21] Szpankowski, W., Some results on i-ary asymmetric tries, J. algorithms, 9, 224-244, (1988) · Zbl 0637.68072
[22] Whittaker, E.; Watson, G., A course of modern analysis, (1935), Cambridge Press · JFM 45.0433.02
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.