Loading...
Loading...

Go to the content (press return)

On the average performance of orthogonal range search in multidimensional data structures

Author
Duch, A.; Martinez, C.
Type of activity
Report
Date
2001-11
Code
LSI-01-54-R
Repository
http://hdl.handle.net/2117/97828 Open in new window
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.
Citation
Duch, A., Martinez, C. "On the average performance of orthogonal range search in multidimensional data structures". 2001.
Keywords
Multidimensional data structures, Orthogonal range search, Random relaxed K-d trees
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments