University of 7th November at Carthage
Range searching and its variants have been studied extensively in the computational geometry and database communities because of their many important applications. Range-aggregate queries, such as range-COUNT, SUM and MAX, are some of the most commonly used versions of range searching in database applications. The authors present external memory data structures for efficiently answering range-aggregate queries. The range-aggregate problem is defined as follows: Given a set of weighted points in R (d), compute the aggregate of the weights of the points that lie inside a d-dimensional orthogonal query rectangle. The aggregates they consider in this paper include COUNT, wSUM, and MAX.