k-dimensional orthogonal range search with tries
Loading...
Files
Date
2002
Authors
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.