This paper provides an excellent overview of continuous query processing. It successfully shows why continuous queries are an important part of today’s applications.
Agarwal et al. make a novel attempt to extend the continuous query processing state of the art, by proposing a query-sensitive algorithm that exploits the potential overlap in predicates of a large set of queries. The algorithm discovers overlaps among the predicates of a group of continuous queries, and identifies hotspots that can be optimized when processing the queries in the group. The authors effectively explore the predicates of a large set of queries and identify all query intervals. This set of intervals is then partitioned into disjoint groups called stabbing partitions. Each partition has a stabbing point--a point that is common to all intervals within the same group. The set of all stabbing points forms a stabbing set of all intervals. Then, a stabbing set index (SSI) is created for a set of continuous queries: first, the set of intervals is identified; next, the stabbing partitions of the set of intervals are computed; finally, the stabbing points are stored for each partition in order (an index). At the heart of this algorithm is the effective identification of intervals for queries in the set.
The performance of the SSI is compared with that of other methods, such as equi-join, band-join, and window-join queries. According to this paper, the SSI outperforms other methods as the number of continuous queries in the set increases to approximately 104.
The paper has some weak points. The intervals on which the hotspots are defined and analyzed seem to be based on simple predicates that only cover range queries. The authors state that their work can be extended to cover more complicated queries, but from reading the paper, the degree to which complex conjunctive normal and disjunctive normal forms of predicates affect the result of the analysis is not clear.
Some parts of the paper are overly complicated; for example, the definition of &agr; hotspots and their properties, with respect to the size and number of interval groupings, is unclear. Also, when the authors use skylines to describe the SSI approach, it would be less confusing if there were some additional figures to demonstrate the basic purpose or concept being used.
With respect to the experiments, it is unclear what the sample sizes mean or whether these sizes are representative. For example, it is not clear if the number of queries is distinct or if it may include multiple instances of the same (duplicate) query. The fact that the number of queries is the same as the number of tuples seems unusual; furthermore, it is not clear how much or how fast these two quantities are likely to change in the real world. To a novice, there is a significant difference between the query processing performed when a new query is first added and the continuous update of its results, once it has processed all the existing data. In particular, the window-join method seems to be the most natural choice for the latter case; therefore, it would have been useful to include the window-join method in the experiments. Lastly, since Agarwal et al. needed to change the platform on which the experiments were run, in order to handle a larger dataset, it would have been nice to see the other experiments also run against this same platform. Lacking this, it is difficult to understand which components of the benchmarks are due to platform-specific issues, rather than query algorithm or dataset sizes.
