Abstract
We 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 Rd, compute the aggregate of the weights of the points that lie inside a d-dimensional orthogonal query rectangle. The aggregates we consider in this paper include count, sum, and max. First, we develop a structure for answering two-dimensional range-count queries that uses O(N/B) disk blocks and answers a query in View the MathML source I/Os, where N is the number of input points and B is the disk block size. The structure can be extended to obtain a near-linear-size structure for answering range-sum queries using View the MathML source I/Os, and a linear-size structure for answering range-max queries in View the MathML source I/Os. Our structures can be made dynamic and extended to higher dimensions.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Computational Geometry |
Vol/bind | 46 |
Sider (fra-til) | 358-370 |
Antal sider | 13 |
ISSN | 0925-7721 |
DOI | |
Status | Udgivet - 1 apr. 2013 |
Udgivet eksternt | Ja |
Emneord
- External memory algorithms
- Range-aggregation
- Data structures