Vaidya’s work provides an insight into such issues as the minimum amount of storage needed to ensure a certain query time. The tradeoff between space and time depends on the model of the data structure and the set of records in the database. Worst-case bounds or the lower bound of the space-time product can be obtained by fixing a data structure and showing the existence of a set of records whose space-time product has the given bound.

This paper presents the space-time tradeoffs for orthogonal range queries on a static database. The database contains a collection of records, each of which has a key and a number of data fields. A database system returns either the set of records or a function of the set of records whose keys satisfy all the constraints of a given query. A record ( k , f ( k ) ) is a pair, where k is the key and f ( k ) is the datum from a commutative semigroup G. If k is a d -tuple, an orthogonal range query is specified by a 2 d -tuple ( x ₁₁ , x ₁₂ , x ₂₁ , x ₂₂ ,..., x _d1 , x _d2 ) of positive integers satisfying x _i1 < x _i2 where 1 ≤ i ≤ d. The query region for an orthogonal range query is a parallelepiped defined by the product of d -semiclosed intervals [ x ₁₁ , x ₁₂ ) × [x ₂₁ , x ₂₂ ) × ... × [ x _d1 , x _d2 ). A key is said to be located in the parallelepiped if and only if x _i1 ≤ k _i ≤ x _i2 for 1 ≤ i ≤ d.

The author considers two types of responses to an orthogonal range query. In one case, the output is the semigroup sum of the data values whose keys are located in the query parallelepiped, while in the other the output is a list of all the records whose keys lie in the query parallelepiped. The paper studies two models, the arithmetic model and the tree model. The arithmetic model attributes unit cost to each arithmetic operation but no cost to measuring retrieval. Given a query box b, the query answering algorithm is expected to return the semigroup sum of the data values whose keys are located in b. The tree model considers a scaled query time in order to take the overhead involved in producing the response to a query into account. The data structure for this model is a rooted tree with each edge in the tree associated with a condition. The output to a query is a function of the data associated with the vertices visited, starting from the root.

The paper is clear and concise. Since most data structures in practical use are rooted trees (fitting the tree model), the results are significant.