Lars Arge

Efficient external memory structures for range-aggregate queries

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • P.K. Agarwal, Duke University
  • ,
  • J. Yang, Denmark
  • L. Arge
  • S. Govindarajan, Indian Institute of Science
  • ,
  • K. Yi, HKUST
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 , 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( N) 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( N) 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.
Original languageEnglish
JournalComputational Geometry
Volume46
Issue3
Pages (from-to)358-370
Number of pages13
ISSN0925-7721
DOIs
Publication statusPublished - 1 Apr 2013

See relations at Aarhus University Citationformats

ID: 56165888