zbMATH — the first resource for mathematics

Multidimensional digital searching – alternative data structures. (English) Zbl 0803.68024
Summary: We analyze the average cost of partial match queries in \(M\)-dimensional Digital Search Trees and Patricia Tries. Our results allow a precise comparison of the average behavior of these data structures with the \(M\)- dimensional Tries studied by P. Flajolet and C. Puech [J. Assoc. Comput. Math. 33, 371-407 (1986)]. It turns out that Patricia is superior to Digital Search Trees, the latter ones being superior to Tries.
Reviewer: Reviewer (Berlin)

68P10 Searching and sorting
68P05 Data structures
Full Text: DOI
[1] Flajolet, J. Assoc. Comput. Mach. 33 pp 371– (1986) · doi:10.1145/5383.5453
[2] Plajolet, SIAM J. Comput. 15 pp 748– (1986)
[3] The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.
[4] Vorlesungen über Differenzenrechnung, Chelsea, New York, 1954.
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.