Loading...
Please wait, while we are loading the content...
Similar Documents
An investigation of multi-level k-ranges.
| Content Provider | CiteSeerX |
|---|---|
| Author | Falconer, Sean M. Nickerson, Bradford G. |
| Abstract | 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 ) storage. They also introduced the multi-level k-range, which o#ers slightly slower query time but with O(N ) storage for any fixed values of k and # > 0. In this paper, we investigate an implementation of the multi-level k-range data structure. The #-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 #-level k-ranges require Q(N, k, #) = O(# (log N A)) time for range search. We show that the minimal storage for N , where a and # are positive integers, is S(N, k) = O(N ). |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Query Time Efficient Theoretical Data Structure Fixed Value Positive Integer Level K-ranges Range Search Level K-range Multi-level K-ranges Multi-level K-range Data Point 1-level K-range Offer Multi-level K-range Data Structure Test Case Naive Search K-d Point Tree Search Range Searching Minimal Storage |
| Content Type | Text |
