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: hf05eac32d95e06a4
Venue: VLDB
Year: 2006
Pagerank: 6.5139479e-05
Overall Rank: 4,590 | 69.15%
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,624	Optimal Sampling from Sliding Windows	2009	PODS	8.2095532e-05
2,919	Monarch: Google’s Planet-Scale In-Memory Time Series Database	2020	VLDB	7.8548399e-05
5,653	Staying FIT: Efficient Load Shedding Techniques for Distributed Stream Processing	2007	VLDB	6.0509231e-05
7,860	Changing Flights in Mid-air: A Model for Safely Modifying Continuous Queries	2011	SIGMOD	5.4391693e-05
8,490	THEMIS: Fairness in Federated Stream Processing under Overload	2016	SIGMOD	5.3315439e-05
9,123	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD	5.2254194e-05
12,558	SkySuite: A Framework of Skyline-Join Operators for Static and Stream Environments	2013	VLDB	4.9793485e-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.00076195956
112	TelegraphCQ: Continuous Dataflow Processing for an Uncertain World	2003	CIDR	0.00032459277
127	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030427614
152	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.0002867034
171	Monitoring Streams – A New Class of Data Management Applications	2002	VLDB	0.00027011593
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021384073
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021311793
566	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016295476
594	Linear Road: A Stream Data Management Benchmark	2004	VLDB	0.00015823573
676	Load Shedding in a Data Stream Manager	2003	VLDB	0.00014853749
842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013540697
1,431	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010681774
1,666	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS	9.9382031e-05
1,674	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD	9.922398e-05
3,727	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	7.0696489e-05
4,693	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4662079e-05
4,942	Distributed Operation in the Borealis Stream Processing Engine	2005	SIGMOD	6.34525e-05
5,038	Query Languages and Data Models for Database Sequences and Data Streams	2004	VLDB	6.3029403e-05

Semantically Similar Papers

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