| Available via | http://dbpubs.stanford.edu/pub/2003-69 |
|
Submitted on |
5th of November 2003 |
|
Author |
Babu, Shivnath; Motwani, Rajeev; Munagala, Kamesh; Nishizawa, Itaru; Widom, Jennifer |
|
Title |
Adaptive Ordering of Pipelined Stream Filters |
|
Date of publication |
2003 |
|
Published in |
Proc. of ACM Intl. Conference on Management of Data (SIGMOD), 2004 |
|
Citation |
Babu, Shivnath; Motwani, Rajeev; Munagala, Kamesh; Nishizawa, Itaru; Widom, Jennifer. Adaptive Ordering of Pipelined Stream Filters, Proc. of ACM Intl. Conference on Management of Data (SIGMOD), 2004 |
|
Number of pages |
13 |
|
Language |
English |
|
Project |
STREAM |
|
Type |
Technical Report |
|
Subject group |
Data Streams; Query processing; Miscellaneous |
|
Abstract |
We consider the problem of pipelined filters, where a continuous
stream of elements is processed by a set of commutative filters.
Pipelined filters are common in stream applications and capture a
large class of multiway stream joins. We focus on the problem of
ordering the filters adaptively to minimize processing cost in an
environment where stream and filter characteristics vary unpredictably
over time. Our core algorithm, A-Greedy (for Adaptive
Greedy), has strong theoretical guarantees: If stream and filter
characteristics were to stabilize, A-Greedy would converge to an
ordering within a small constant factor of optimal. (In experiments
A-Greedy usually converges to the optimal ordering.) One very
important feature of A-Greedy is that it monitors and responds to
selectivities that are correlated across filters (i.e., that are
nonindependent), which provides the strong quality guarantee but
incurs run-time overhead. We identify and study a three-way tradeoff
among provable convergence to good orderings, run-time overhead, and
speed of adaptivity. We develop a suite of variants of A-Greedy that
lie at different points on this tradeoff spectrum. We have
implemented all our algorithms in a Data Stream Management System and
a thorough performance evaluation is presented. |
|
Contact address |
shivnath@stanford.edu |
|
Sponsored by |
NSF, NIH |
| Fulltext source |
Postscript (ps, ps.gz, ps.zip)
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | rwesley@stanford.edu
| |