Abstract | ||
---|---|---|
We propose a newindexing scheme, called the CRB-tree, 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 weights of points that lie inside a d-dimensional query rectangle. In this paper we focus on range-COUNT, SUM, AVG aggregates. First, we develop an indexing scheme for answering two-dimensional range-COUNT 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 range-COUNT problem. The index can be extended to obtain a near-linear-size structure for answering range-SUM queries using O(logB N) I/Os. We also obtain similar bounds for rectangle-intersection 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 temporal-aggregate 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 kdB-tree. For a dataset of around 100 million points, the CRB-tree query time is 8-10 times faster than the kdB-tree query time. Furthermore, unlike other indexing schemes, the query performance of CRB-tree is oblivious to the distribution of the input points and placement, shape and size of the query rectangle. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1007/3-540-36285-1_10 | ICDT |
Keywords | Field | DocType |
range-aggregate queries,range-aggregate query,d-dimensional query rectangle,efficient indexing scheme,query performance,rectangle-intersection aggregate query,kdb-tree query time,crb-tree query time,input point,logb n,query rectangle,indexing scheme,indexation | Block size,Query optimization,Indexation,Database query,Computer science,Rectangle,Sargable,Search engine indexing,Algorithm,Theoretical computer science,Spatial database | Conference |
Volume | ISSN | ISBN |
2572 | 0302-9743 | 3-540-00323-1 |
Citations | PageRank | References |
28 | 1.35 | 22 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sathish Govindarajan | 1 | 110 | 12.84 |
Pankaj K. Agarwal | 2 | 5257 | 593.81 |
Lars Arge | 3 | 2066 | 255.14 |