| Available via | http://dbpubs.stanford.edu/pub/2002-29 |
|
Submitted on |
11th of June 2002 |
|
Author |
Arasu, Arvind; Babcock, Brian; Babu, Shivnath; McAlister, Jon; Widom, Jennifer |
|
Title |
Characterizing Memory Requirements for Queries over Continuous Data Streams |
|
Date of publication |
May 2002 |
|
Published in |
extended version of publication 2001-49 |
|
Citation |
Arasu, Arvind; Babcock, Brian; Babu, Shivnath; McAlister, Jon; Widom, Jennifer. Characterizing Memory Requirements for Queries over Continuous Data Streams, extended version of publication 2001-49 |
|
Number of pages |
38 |
|
Language |
English |
|
Project |
STREAM |
|
Type |
Other |
|
Subject group |
Data Streams |
|
Abstract |
We consider conjunctive queries with arithmetic comparisons and optional
aggregation over multiple continuous data streams. We specify an
algorithm for determining whether or not any given query can be evaluated
using a bounded amount of memory for all possible instances of the data
streams. When a query can be evaluated using bounded memory, we produce
an execution strategy based on constant-sized synopses of the data
streams. When it cannot, we produce a data stream scenario in which
evaluating the query requires memory linear in the size of the streams. |
|
Keywords |
Continuous Data Streams, Query Optimization, Memory Requirements, Aggregation |
| Fulltext source |
Postscript (ps, ps.gz, ps.zip)
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | rwesley@stanford.edu
| |