| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2002-52 | ||
| Submitted on | 10th of November 2002 | ||
| Author | Babu, Shivnath; Srivastava, Utkarsh; Widom, Jennifer | ||
| Title | Exploiting k-Constraints to Reduce Memory Overhead in Continuous Queries over Data Streams | ||
| Date of publication | November 2002 | ||
| Citation | Babu, Shivnath; Srivastava, Utkarsh; Widom, Jennifer. Exploiting k-Constraints to Reduce Memory Overhead in Continuous Queries over Data Streams | ||
| Number of pages | 28 | ||
| Language | English | ||
| Project | STREAM | ||
| Type | Technical Report | ||
| Subject group | Data Streams; Query processing | ||
| Abstract | Continuous queries often require significant run-time state over arbitrary data streams. However, streams may exhibit certain data or arrival patterns, or constraints, that can be detected and exploited to reduce state considerably without compromising correctness. Rather than requiring constraints to be satisfied precisely, which can be unrealistic in a data streams environment, we introduce k-constraints, where k is an adherence parameter specifying how closely a stream adheres to the constraint. (Smaller k's are closer to strict adherence and offer better memory reduction.) We present a query processing architecture, called k-Mon, that detects useful k-constraints automatically and exploits the constraints to reduce run-time state for a wide range of continuous queries. Experimental results show dramatic state reduction, while only modest computational overhead is incurred for our constraint monitoring and query execution algorithms. | ||
| Keywords | Data Streams, constraints, query processing | ||
| Contact address | shivnath@stanford.edu | ||
| Sponsored by |
This work was supported by the National Science Foundation under grants IIS-0118173 and IIS-9817799, and by a Stanford Graduate Fellowship from Sequoia Capital. | ||
| Notes | This technical report is an updated version of an earlier technical report of the same name, which appeared originally in November 2002. This version contains new material on constraint monitoring (Sections 1.4, 4.2, 5.2, and 6.2) and adds author Srivastava. | ||
| Fulltext source |
| Management of the document by | rwesley@stanford.edu
| |