Browsing by Author "Bu, Lingke"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    k-dimensional orthogonal range search with tries
    (2002) Nickerson, Bradford, G.; Bu, Lingke
    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.