Multidimensional search trees that provide new types of memory reductions
Dan E. Willard · Journal of the ACM · 1987
An orthogonal query that asks to aggregate the set of records in k -dimensional box regions is studied, and it is shown that space O ( N ((log N )/(log log N )) k -1 ) makes possible a combined time complexity O (log k N ) for retrievals, insertions, and deletions.