Scalable continuous query processing by tracking hotspots


Conference Paper

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.

Duke Authors

Cited Authors

  • Agarwal, PK; Xie, J; Yang, J; Yu, H

Published Date

  • December 1, 2006

Published In

  • Vldb 2006 Proceedings of the 32nd International Conference on Very Large Data Bases

Start / End Page

  • 31 - 42

International Standard Book Number 10 (ISBN-10)

  • 1595933859

International Standard Book Number 13 (ISBN-13)

  • 9781595933850

Citation Source

  • Scopus