k-dimensional orthogonal range search with tries

Loading...
Thumbnail Image
Date
2002
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We present an algorithm using tries to solve the orthogonal range search problem on k dimensions. The algorithm reports all k-d hyper-rectangles intersecting a k-d axis-aligned query hyper-rectangle W, and supports dynamic operations. For the input data set D and W drawn from a uniform, random distribution, we analyse the expected time for orthogonal range search. We show that the storage S(n, k) =O(nk), and the expected preprocessing time P(n, k) = O(nk) for a trie containing n k-d hyper-rectangles.
Description
Keywords
Citation
Collections