Stanford InfoLab Publication Server

Exploiting k-Constraints to Reduce Memory Overhead in Continuous Queries over Data Streams

Babu, Shivnath and Srivastava, Utkarsh and Widom, Jennifer (2002) Exploiting k-Constraints to Reduce Memory Overhead in Continuous Queries over Data Streams. Technical Report. Stanford.




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.

Item Type:Techreport (Technical Report)
Additional Information: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.
Uncontrolled Keywords:Data Streams, constraints, query processing
Subjects:Computer Science > Data Streams
Computer Science > Query Processing
Related URLs:Project Homepage
ID Code:560
Deposited By:Import Account
Deposited On:09 Nov 2002 16:00
Last Modified:25 Dec 2008 08:36

Download statistics

Repository Staff Only: item control page