On multi-level kappa-ranges for range search
We investigate an implementation of the multi-level or l-level k-range data structure. The l-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, l) = O(N(1+2(k-1)/l)) and S(N, k) = Theta(N(1+2(k-1)/log2 N)). Our results also indicate that the l-level k-range requires Q(N, k, l) = O((2l)(k)(log N + A)) time for range search, for A = number of points reported in range.
multidimensional orthogonal range search space and time complexity