Multidimensional searching - alternative data structures

Abstract. 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 [1]. 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)