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.
References:
| [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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
