Math @ Duke

Publications [#235613] of Pankaj K. Agarwal
Papers Published
 Govindarajan, S; Agarwal, PK; Arge, L, CRBtree: An efficient indexing scheme for rangeaggregate queries,
Lecture notes in computer science, vol. 2572
(2003),
pp. 143157, ISSN 03029743
(last updated on 2018/07/22)
Abstract: We propose a new indexing scheme, called the CRBtree, for efficiently answering rangeaggregate queries. The rangeaggregate problem is defined as follows: Given a set of weighted points in ℝd, compute the aggregate of weights of points that lie inside a ddimensional query rectangle. In this paper we focus on rangeCOUNT, SUM, AVG aggregates. First, we develop an indexing scheme for answering twodimensional rangeCOUNT queries that uses O(N/B) disk blocks and answers a query in O(logB N) I/Os, where N is the number of input points and B is the disk block size. This is the first optimal index structure for the 2D rangeCOUNT problem. The index can be extended to obtain a nearlinearsize structure for answering rangeSUM queries using O(logB N) I/Os. We also obtain similar bounds for rectangleintersection aggregate queries, in which the input is a set of weighted rectangles and a query asks to compute the aggregate of the weights of those input rectangles that overlap with the query rectangle. This result immediately improves a recent result on temporalaggregate queries. Our indexing scheme can be dynamized and extended to higher dimensions. Finally, we demonstrate the practical efficiency of our index by comparing its performance against kdBtree. For a dataset of around 100 million points, the CRBtree query time is 810 times faster than the kdBtree query time. Furthermore, unlike other indexing schemes, the query performance of CRBtree is oblivious to the distribution of the input points and placement, shape and size of the query rectangle. © SpringerVerlag Berlin Heidelberg 2003.


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

