2005 | OriginalPaper | Buchkapitel
Algorithms for Range-Aggregate Query Problems Involving Geometric Aggregation Operations
verfasst von : Prosenjit Gupta
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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. Efficient solutions are provided for point enclosure queries, 1-d interval intersection, 2-d orthogonal segment intersection and 1- and 2-d closest pair problems in this framework. Although range-aggregate queries have been widely investigated in the past for aggregation functions like average, count, min, max, sum etc. we consider geometric aggregation operations in this paper.