Nickerson, Bradford, G.Bu, Lingke2023-03-012023-03-012002https://unbscholar.lib.unb.ca/handle/1882/14804We 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.http://purl.org/coar/access_right/c_abf2technical reportComputer Science