[ Pagewise preview ]
| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2005-36 | ||
| Submitted on | 30th of November 2005 | ||
| Author | Munagala, Kamesh; Srivastava, Utkarsh; Widom, Jennifer | ||
| Title | Optimization of Continuous Queries with Shared Expensive Filters | ||
| Date of publication | 2005 | ||
| Citation | Munagala, Kamesh; Srivastava, Utkarsh; Widom, Jennifer. Optimization of Continuous Queries with Shared Expensive Filters, | ||
| Number of pages | 13 | ||
| Language | English | ||
| Project | STREAM | ||
| Type | Technical Report | ||
| Subject group | Data Streams | ||
| Abstract | We consider the problem of optimizing and executing multiple continuous queries, where each query is a conjunction of filters and each filter may occur in multiple queries. When filters are expensive, significant performance gains are achieved by sharing filter evaluations across queries. A shared execution strategy in our scenario can either be fixed, in which filters are evaluated in the same predetermined order for all input, or {\em adaptive}, in which the next filter to be evaluated is chosen at runtime based on the results of the filters evaluated so far. We show that as filter costs increase, the best adaptive strategy is superior to any fixed strategy, despite the overhead of adaptivity. We show that it is NP-hard to find the optimal adaptive strategy, even if we are willing to approximate within any factor smaller than logarithmic in the number of queries. We present a greedy execution strategy and show that it approximates the best adaptive strategy to within a factor polylogarithmic in the number of queries and filters. We also show how the execution overhead of adaptive strategies can be reduced by appropriate precomputation. Finally, we present an experimental evaluation demonstrating the effectiveness of our techniques. | ||
| Keywords | continuous queries, streams, expensive filters, shared execution | ||
| Sponsored by | This work was supported by the National Science Foundation under grant IIS-0324431, by a Stanford Graduate Fellowship from Sequoia Capital, and by a fellowship from Microsoft Corporation. | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |
[ Pagewise preview ]