Multidimensional searching - alternative data structures
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 behaviour of these
data structures with the $M$-dimensional Tries studied by
Flajolet and Puech . It turns out that Patricia is superior
to Digital Search Trees, the latter ones being superior to Tries.
This paper is available in the Tex, Dvi, and PostScript format.
The drawings of the trees are not there (unfortunately).
(Back to List of Papers)