Math @ Duke

Publications [#235557] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Arge, L; Govindarajan, S; Yang, J; Yi, K, Efficient external memory structures for rangeaggregate queries,
Computational Geometry, vol. 46 no. 3
(2013),
pp. 358370, ISSN 09257721 [doi]
(last updated on 2018/05/20)
Abstract: We present external memory data structures for efficiently answering rangeaggregate queries. The rangeaggregate 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 ddimensional orthogonal query rectangle. The aggregates we consider in this paper include count, sum, and max. First, we develop a structure for answering twodimensional rangecount 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 nearlinearsize structure for answering rangesum queries using O( logBN) I/Os, and a linearsize structure for answering rangemax queries in O(logB2N) I/Os. Our structures can be made dynamic and extended to higher dimensions. © 2012 Elsevier B.V.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

