HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/2514
Title: Aggregate processing of planar points
Authors: Tao, Yufei
Papadias, Dimitris
Zhang, Jun
Keywords: Aggregate query processing
Planar points
Aggregate window queries
Summarized information
Query rectangle
Information retrieval
Issue Date: Mar-2002
Citation: 8th International conference on extended database technology, 2002. (LNCS 2287) p. 682-700
Abstract: 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.
Rights: The original publication is available at http://www.springerlink.com/. Please use the appropriate URL and/or DOI for the article.
URI: http://hdl.handle.net/1783.1/2514
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
aggr.pdfpre-published version289KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.