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.

helmut@gauss.cam.wits.ac.za,

Peter.Kirschenhofer@tuwien.ac.at,

This paper is available in the Tex, Dvi, and PostScript format.
The drawings of the trees are not there (unfortunately).

Tex
Dvi
PostScript

(Back to List of Papers)