Donald Bren School of Information and Computer Sciences

A data base is said to allow range restrictions if we may request that only records with some specified field in a specified range be considered when answering a given query. We present a transformation which enables range restrictions to be added to an arbitrary dynamic data structure on n elements, provided that the problem satisfies a certain decomposability condition, and that we are willing to allow increases of a factor of log n in the worst-case time for an operation and in the space used. This is a generalization of a known transformation which works for static structures. We then use this transformation to produce a data structure for range queries in k dimensions with worst-case times of O(log^kn) for each insertion, deletion, or query operation.

(Similar results were achieved independently by Dan Willard. See the remarks at the end of section 1.)