A Lower Bound on the Complexity of Orthogonal Range Queries

Abstract

Let S be an arbitrary commutaUve semigroup (set of elements closed under a commutative and associative addmon operation, +). Given a set of records wtth d-dimensional key vectors over an ordered key space, such that each record has associated with it a value in S, an orthogonal range query is a request for the sum of the values associated with each record in some specified hypercube (cross product of mtervals). Data structures which accommodate inserUons and delettons of records and orthogonal range queries, such that an arbitrary sequence of n such operations takes time O(n(log n)a), have been presented by G. Lueker and D. Wdlard. It is shown here that fi(n(logn) ~) is a lower bound on the inherent worst case time reqmred to process a sequence of n intermixed insemons, deleuons, and range queries, which imphes that the Lueker and Wdlard data structures are in some sense optimal.