Browsing by Author "Falconer, Sean, M."

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    An investigation of multi-level k-ranges
    (2004) Falconer, Sean, M.; Nickerson, Bradford, G.
    Multi-level k-ranges are an efficient theoretical data structure for range searching introduced by J. L. Bentley and H. A. Maurer. Bentley and Maurer showed that a 1-level k-range offers O(k log N + A) query time, where k is the number of dimensions, N is the number of data points and A is the number of points matching the query at the expense of O(N[superscript 2k−1]) storage. They also introduced the multi-level k-range, which offers slightly slower query time but with O(N[superscript 1+e]) storage for any fixed values of k and e > 0. In this paper, we investigate an implementation of the multi-level k-range data structure. The l-level k-range is compared to naive and R*tree search over N randomly generated k-d points. We show that the R*tree search is significantly faster and that even naive search is faster for most test cases. Results indicate that multi-level k-ranges are not competitive due to their (previously unreported) complexity. Our results indicate that l-level k-ranges require Q(N, k, l) = O((2l)[superscript (k−1)](log N + A)) time for range search. We show that S(N, k, l) = O(N[superscript 1+2(k−1)/l]) and when N does not equal a[superscript l] where a and l are positive integers, S(N, k) = O(N[superscript 1+2(k−1)]/ log[subscript 2] N).