Please use this identifier to cite or link to this item:

Aggregate processing of planar points

Authors Tao, YF
Papadias, D.
Zhang, J.
Issue Date 2002
Source Lecture Notes in Computer Science , v. 2287, 2002, p. 682-700
Summary Aggregate window queries return summarized information about objects that fall inside a query rectangle (e.g., the number of objects instead of their concrete ids). Traditional approaches for processing such queries usually retrieve considerable extra information, thus compromising the processing cost. The paper addresses this problem for planar points from both theoretical and practical points of view. We show that, an aggregate window query can be answered in logarithmic worst-case time by an indexing structure called the aP-tree. Next we study the practical behavior of the aP-tree and propose efficient cost models that predict the structure size and actual query cost. Extensive experiments show that the aP-tree, while involving more space consumption, accelerates query processing by up to an order of magnitude compared to a specialized method based on R-trees. Furthermore, our cost models are accurate and can be employed for the selection of the most appropriate method, balancing the space and query time tradeoff.
ISSN 0302-9743
ISBN 3-540-43324-4
Rights The original publication is available at Please use the appropriate URL and/or DOI for the article.
Language English
Format Article
Access View full-text via Web of Science
Files in this item:
File Description Size Format
aggr.pdf 296128 B Adobe PDF