Stanford InfoLab Publication Server

Adaptive Ordering of Pipelined Stream Filters

Babu, Shivnath and Motwani, Rajeev and Munagala, Kamesh and Nishizawa, Itaru and Widom, Jennifer (2003) Adaptive Ordering of Pipelined Stream Filters. Technical Report. Stanford. (Publication Note: Proc. of ACM Intl. Conference on Management of Data (SIGMOD), 2004)




We consider the problem of <i>pipelined filters</i>, 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, <i>A-Greedy</i> (for <i> Adaptive Greedy</i>), 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.

Item Type:Techreport (Technical Report)
Subjects:Computer Science > Data Streams
Computer Science > Query Processing
Related URLs:Project Homepage
ID Code:621
Deposited By:Import Account
Deposited On:04 Nov 2003 16:00
Last Modified:24 Dec 2008 08:40

Download statistics

Repository Staff Only: item control page