Tries for spatial data range search
Loading...
Files
Date
2003
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Orthogonal range search finds and reports all objects falling in a specific query window. An algorithm to solve orthogonal range search problem on k dimensions using tries is developed and analyzed. Two hyper-rectangles intersect if and only if their sides on every dimension in the data space intersect. The algorithm reports the set HR (HR C input data set D, HR = A, D = n) or k-dimensional (k-d) hyper-rectangles intersecting a k-d axis-aligned query hyper-rectangle W, and supports dynamic operations. We assume that the input data set D and query hyper-rectangle W drawn from a uniform, random distribution. The storage S(n,k) = 0(kBn) and the expected preprocessing time P(n, k) = 0(kBn) for a trie containing n k-d hyper-rectangles where B is the number of bits for representing a coordinate value. The expected orthogonal range search time Q(n, k) = O(n[superscript a]) for 0.5 < & < 1 and & a complicated function of n and k. Experimental research with randomly generated data and query hyper-rectangles (and various values of k and n up to 10 and 100,000 respectively) is used to empirically validate the expected range search time. Our algorithm compares favorably to the existing dynamic orthogonal range search algorithm when k is large.