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.5109054e-05
Overall Rank: 4,592 | 69.14%
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,626	Optimal Sampling from Sliding Windows	2009	PODS	8.205667e-05
2,920	Monarch: Google’s Planet-Scale In-Memory Time Series Database	2020	VLDB	7.8519381e-05
5,654	Staying FIT: Efficient Load Shedding Techniques for Distributed Stream Processing	2007	VLDB	6.0480587e-05
7,864	Changing Flights in Mid-air: A Model for Safely Modifying Continuous Queries	2011	SIGMOD	5.4366003e-05
8,498	THEMIS: Fairness in Federated Stream Processing under Overload	2016	SIGMOD	5.32902e-05
9,132	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD	5.2229513e-05
12,564	SkySuite: A Framework of Skyline-Join Operators for Static and Stream Environments	2013	VLDB	4.9769913e-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.00076265429
112	TelegraphCQ: Continuous Dataflow Processing for an Uncertain World	2003	CIDR	0.00032445088
127	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030414379
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
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021376597
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.0002130211
566	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016288241
594	Linear Road: A Stream Data Management Benchmark	2004	VLDB	0.00015816384
677	Load Shedding in a Data Stream Manager	2003	VLDB	0.0001484703
843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013534623
1,431	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010676907
1,667	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS	9.9335373e-05
1,674	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD	9.9177225e-05
3,729	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	7.0664086e-05
4,695	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4632424e-05
4,944	Distributed Operation in the Borealis Stream Processing Engine	2005	SIGMOD	6.3422462e-05
5,040	Query Languages and Data Models for Database Sequences and Data Streams	2004	VLDB	6.2999611e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,431	Approximate Join Processing Over Data Streams	2003	SIGMOD
2	7,875	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
3	6,162	Load Shedding in Stream Databases: A Control-Based Approach	2006	VLDB
4	3,729	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
5	6,659	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,695	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	677	Load Shedding in a Data Stream Manager	2003	VLDB