Window-Aware Load Shedding for Aggregation Queries over Data Streams

Summary: Proposes Window Drop, a window-aware load-shedding operator for aggregate queries with sliding windows. It partitions input into windows, probabilistically drops selected windows and marks tuples to prevent new window starts, preserving window integrity and yielding bounded-quality results. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9684
Venue: VLDB
Year: 2006
Pagerank: 6.6481605e-05
Overall Rank: 4,517 | 69.02%
DOI: 10.1145/1164135.1164205

Incoming Non-self Citations Over Time

Authors

1. Nesime Tatbul (Brown University)
2. Stan Zdonik (Brown University)

BibTeX Citation

@article{tatbul_vldb06,
        title = {{Window-Aware Load Shedding for Aggregation Queries over Data Streams}},
        author = {Tatbul, Nesime and Zdonik, Stan},
        journal = {PVLDB},
        series = {{VLDB} '06},
        pages = {799--810},
        doi = {10.1145/1164135.1164205},
        url = {https://doi.org/10.1145/1164135.1164205},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,576	Optimal Sampling from Sliding Windows	2009	PODS	8.3964437e-05
3,123	Monarch: Google’s Planet-Scale In-Memory Time Series Database	2020	VLDB	7.7354933e-05
5,521	Staying FIT: Efficient Load Shedding Techniques for Distributed Stream Processing	2007	VLDB	6.1881166e-05
8,065	Changing Flights in Mid-air: A Model for Safely Modifying Continuous Queries	2011	SIGMOD	5.4942386e-05
8,324	THEMIS: Fairness in Federated Stream Processing under Overload	2016	SIGMOD	5.4539042e-05
8,980	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD	5.3398545e-05
12,267	SkySuite: A Framework of Skyline-Join Operators for Static and Stream Environments	2013	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00077458002
111	TelegraphCQ: Continuous Dataflow Processing for an Uncertain World	2003	CIDR	0.00032990214
127	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030738755
150	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.00029208207
167	Monitoring Streams – A New Class of Data Management Applications	2002	VLDB	0.0002757283
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
551	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016635191
587	Linear Road: A Stream Data Management Benchmark	2004	VLDB	0.00016106078
671	Load Shedding in a Data Stream Manager	2003	VLDB	0.00015154516
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010906135
1,656	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS	0.00010097487
1,703	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD	9.9673138e-05
3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	7.2217692e-05
4,596	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.6133976e-05
4,830	Distributed Operation in the Borealis Stream Processing Engine	2005	SIGMOD	6.4882268e-05
4,925	Query Languages and Data Models for Database Sequences and Data Streams	2004	VLDB	6.442888e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD
2	7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
3	6,033	Load Shedding in Stream Databases: A Control-Based Approach	2006	VLDB
4	3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
5	6,528	State-Slice: New Paradigm of Multi-query Optimization of Window-based Stream Queries	2006	VLDB
6	1,354	On-the-Fly Sharing for Streamed Aggregation	2006	SIGMOD
7	4,596	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD
8	1,703	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD
9	1,263	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB
10	671	Load Shedding in a Data Stream Manager	2003	VLDB