RANGE-AGGREGATE QUERY PROBLEMS INVOLVING GEOMETRIC AGGREGATION OPERATIONS

摘要

We consider variations of the standard orthogonal range searching motivated by applications in database querying and VLSI layout processing. In a generic instance of such a problem, called a range-aggregate query problem we wish to preprocess a set S of geometric objects such that given a query orthogonal range q, a certain intersection or proximity query on the objects of S intersected by q can be answered efficiently. Although range-aggregate queries have been widely investigated in the past for aggregation functions like average, count, min, max, sum etc. we consider aggregation operations involving geometric intersection searching problems in this paper. Efficient solutions are provided for point enclosure queries for d > 1, 1-d interval intersection, 2-d orthogonal segment intersection and interval/rectangle/hyper-rectangle enclosure queries in this framework.