Efficient external memory structures for range-aggregate queries

Published

Journal Article

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 O( logBN) 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( logBN) I/Os, and a linear-size structure for answering range-max queries in O(logB2N) I/Os. Our structures can be made dynamic and extended to higher dimensions. © 2012 Elsevier B.V.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Arge, L; Govindarajan, S; Yang, J; Yi, K

Published Date

  • April 1, 2013

Published In

Volume / Issue

  • 46 / 3

Start / End Page

  • 358 - 370

International Standard Serial Number (ISSN)

  • 0925-7721

Digital Object Identifier (DOI)

  • 10.1016/j.comgeo.2012.10.003

Citation Source

  • Scopus