Chain: Operator Scheduling for Memory Minimization in Data Stream Systems

Summary: Introduces Chain, an adaptive, load-aware operator scheduler that minimizes memory under bursty streaming loads. Near-optimal for single-stream queries (selections, projections, joins) and effective for sliding-window workloads, with experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: ha3e17c1f5a3e0468
Venue: SIGMOD
Year: 2003
Pagerank: 0.00012303144
Overall Rank: 1,047 | 92.97%
DOI: 10.1145/872757.872789

Incoming Non-self Citations Over Time

Authors

1. Brian Babcock (Stanford University)
2. Shivnath Babu (Stanford University)
3. Mayur Datar (Stanford University)
4. Rajeev Motwani (Stanford University)

BibTeX Citation

@inproceedings{babcock_sigmod03,
        title = {{Chain: Operator Scheduling for Memory Minimization in Data Stream Systems}},
        author = {Babcock, Brian and Babu, Shivnath and Datar, Mayur and Motwani, Rajeev},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872789},
        url = {https://dl.acm.org/doi/10.1145/872757.872789},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
127	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030414379
430	Flexible Time Management in Data Stream Systems	2004	PODS	0.00018431194
1,279	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011226666
1,751	Towards a Streaming SQL Standard	2008	VLDB	9.7266159e-05
1,829	Fault-Tolerance in the Borealis Distributed Stream Processing System	2005	SIGMOD	9.5470848e-05
2,502	Operator Scheduling in a Data Stream Manager	2003	VLDB	8.3769557e-05
2,558	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.2968348e-05
3,371	Dynamic Plan Migration for Continuous Queries Over Data Streams	2004	SIGMOD	7.3659127e-05
3,576	STREAM: The Stanford Stream Data Manager (Demonstration Description)	2003	SIGMOD	7.1922202e-05
4,695	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4632424e-05
5,106	Run-Time Operator State Spilling for Memory Intensive Long-Running Queries	2006	SIGMOD	6.2694868e-05
6,162	Load Shedding in Stream Databases: A Control-Based Approach	2006	VLDB	5.8624264e-05
6,191	Finding Global Icebergs over Distributed Data Sets	2006	PODS	5.8543576e-05
8,137	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.391109e-05
8,274	CAPE: Continuous Query Engine with Heterogeneous-Grained Adaptivity	2004	VLDB	5.3623626e-05
8,853	Efficient Scheduling of Heterogeneous Continuous Queries	2006	VLDB	5.2629364e-05
9,178	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	5.2116787e-05
9,790	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR	5.1261639e-05
10,577	Enjima: A Resource-Adaptive Stream Processing System	2026	SIGMOD	4.9769913e-05
11,978	Klink: Progress-Aware Scheduling for Streaming Data Systems	2021	SIGMOD	4.9769913e-05
12,407	CE-Storm: Confidential Elastic Processing of Data Streams	2015	SIGMOD	4.9769913e-05
12,549	Utility-Maximizing Event Stream Suppression	2013	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052097907
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.000408505
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028977821
152	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.00028657752
171	Monitoring Streams – A New Class of Data Management Applications	2002	VLDB	0.00026999348
200	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00025444144
334	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00020682536
369	Continuous Queries over Append-Only Databases	1992	SIGMOD	0.0001984577
423	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.00018487497
852	Streaming Queries over Streaming Data	2002	VLDB	0.00013450014
1,030	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012402072
1,660	SQL Memory Management in Oracle9i	2002	VLDB	9.9581502e-05
1,796	Dynamic Pipeline Scheduling for Improving Interactive Query Performance	2001	VLDB	9.6147923e-05
3,365	SVP - a Model Capturing Sets, Streams, and Parallelism	1992	VLDB	7.3707699e-05
3,959	Tribeca: A Stream Database Manager For Network Traffic Analysis	1996	VLDB	6.8955123e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,466	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
2	2,754	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB
3	2,502	Operator Scheduling in a Data Stream Manager	2003	VLDB
4	2,782	Scheduling for shared window joins over data streams	2003	VLDB
5	14,094	Scheduling Continuous Queries in Data Stream Management Systems	2008	VLDB
6	8,853	Efficient Scheduling of Heterogeneous Continuous Queries	2006	VLDB
7	6,659	State-Slice: New Paradigm of Multi-query Optimization of Window-based Stream Queries	2006	VLDB
8	3,729	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
9	1,667	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS
10	9,790	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR