| Orthogonal range search finds and reports all objects falling in a specified 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 ⊆ input data set D, |HR | = A, |D| = n) of 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) = theta(kBn) and the expected preprocessing time P(n, k) = theta(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(nalpha) for 0.5 ≤ alpha < 1 and alpha 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. |
