Name
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 R^d, 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 O(log"BN) 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 O(log"BN) I/Os, and a linear-size structure for answering range-max queries in O(log"B^2N) I/Os. Our structures can be made dynamic and extended to higher dimensions. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.comgeo.2012.10.003 | Comput. Geom. |
Keywords | Field | DocType |
disk block,range-aggregate query,efficient external memory structure,range-aggregate problem,two-dimensional range-count query,disk block size,d-dimensional orthogonal query rectangle,range-max query,near-linear-size structure,external memory data structure,linear-size structure,external memory algorithms,data structures | Block size,Discrete mathematics,Data structure,Combinatorics,Computer science,Rectangle,Out-of-core algorithm,Auxiliary memory | Journal |
Volume | Issue | ISSN |
46 | 3 | 0925-7721 |
Citations | PageRank | References |
6 | 0.46 | 19 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Lars Arge | 2 | 2066 | 255.14 |
| Sathish Govindarajan | 3 | 110 | 12.84 |
| Jun Yang | 4 | 2762 | 241.66 |
| Ke Yi | 5 | 1659 | 77.79 |