ON MULTI-LEVEL k-RANGES FOR RANGE SEARCH
Sean M. Falconer, Bradford G. Nickerson · International Journal of Computational Geometry & Applications · 2005
We investigate an implementation of the multi-level or ℓ-level k-range data structure. The ℓ-level k-range is compared to naive and R*tree search over N randomly generated k-dimensional points. Results indicate that multi-level k-ranges are not competitive due to their (previously unreported) complexity. We show that storage is S(N,k,ℓ) = O(N1+2(k-1)/ℓ) and S(N,k) = Θ(N1+2(k-1)/ log 2N). Our results also indicate that the ℓ-level k-range requires Q(N,k,ℓ) = O((2ℓ)k( log N + A)) time for range search, for A = number of points reported in range.