ALCOMFT-TR-01-185

Amalia Duch and Conrado Mart\'\inez
On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures
Barcelona. Work packages 1, 4 and 5. November 2001.

Abstract: In this work we present the average-case analysis of orthogonal range search for several multidimensional data structures. We first consider random relaxed K-d trees as a prototypical example and later extend our results to several different multidimensional data structures. We show that the performance of range searches is related to the performance of a variant of partial matches which simplifies the analysis and provides a tight asymptotic estimate for the expected cost of range searches.

Postscript file: ALCOMFT-TR-01-185.ps.gz (138 kb).