CRB-Tree: An Efficient Indexing Scheme for Range-Aggregate Queries

摘要: We propose a newindexing scheme, called the CRB-tree, for efficiently answering range-aggregate queries. The problem is defined as follows: Given set of weighted points in Rd, compute aggregate weights that lie inside d-dimensional query rectangle. In this paper we focus on range-COUNT, SUM, AVG aggregates. First, develop an indexing scheme two-dimensional range-COUNT queries uses O(N/B) disk blocks and answers O(logB N) I/Os, where N number input B block size. This first optimal index structure 2D problem. can be extended to obtain near-linear-size range-SUM using I/Os. also similar bounds rectangle-intersection queries, which rectangles asks those overlap with result immediately improves recent temporal-aggregate Our dynamized higher dimensions. Finally, demonstrate practical efficiency our by comparing its performance against kdB-tree. For dataset around 100 million points, CRB-tree time 8-10 times faster than kdB-tree time. Furthermore, unlike other schemes, oblivious distribution placement, shape size