An investigation of multi-level k-ranges
| dc.contributor.author | Falconer, Sean, M. | |
| dc.contributor.author | Nickerson, Bradford, G. | |
| dc.date.accessioned | 2023-03-01T18:29:55Z | |
| dc.date.available | 2023-03-01T18:29:55Z | |
| dc.date.issued | 2004 | |
| dc.description.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[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). | |
| dc.description.copyright | Copyright @ Sean M. Falconer and Bradford G. Nickerson, 2004. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14959 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | An investigation of multi-level k-ranges | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1