Scalable continuous query processing by tracking hotspots
This paper considers the problem of scalably processing a large number of continuous queries. We propose a flexible framework with novel data structures and algorithms for group-processing and indexing continuous queries by exploiting potential overlaps in query Predicates. Our approach partitions the collection of continuous queries into groups based on the clustering patterns of the query ranges, and then applies specialized processing strategies to those heavily-clustered groups (or hotspots). To maintain the partition dynamically, we present efficient algorithms that maintain a nearly optimal partition in nearly amortized logarithmic time. We show how to use the hotspots to scalably process large numbers of continuous select-join and band-join queries, which are much more chal-lenging than simple range selection queries. Experiments demonstrate that this approach can improve the processing throughput by orders of magnitude. As another application of hotspots, we show how to use them to build a high-quality histogram for intervals in linear time. Copyright 2006 VLDB Endowment, ACM.
Agarwal, PK; Xie, J; Yang, J; Yu, H
Vldb 2006 Proceedings of the 32nd International Conference on Very Large Data Bases
Start / End Page
International Standard Book Number 10 (ISBN-10)
International Standard Book Number 13 (ISBN-13)