Time-Decaying Aggregates in Out-of-order Streams

Summary: First deterministic algorithms for time‑decayed aggregates on out‑of‑order streams (sliding window, polynomial/exponential), supporting range queries, quantiles, and heavy hitters where EH/Waves fail. Analytically and experimentally quantifies overhead/tradeoffs versus well‑ordered arrivals. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1448
Venue: PODS
Year: 2008
Pagerank: 6.0843083e-05
Overall Rank: 5,802 | 60.20%
DOI: 10.1145/1376916.1376930

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (AT&T)
2. Flip Korn (AT&T)
3. Srikanta Tirthapura (Iowa State University)

BibTeX Citation

@inproceedings{cormode_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Time-Decaying Aggregates in Out-of-order Streams}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376930},
        doi = {10.1145/1376916.1376930},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cormode, Graham and Korn, Flip and Tirthapura, Srikanta},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,370	Fast Manhattan Sketches in Data Streams	2010	PODS	6.7387541e-05
7,626	Quality-Driven Continuous Query Execution over Out-of-Order Data Streams	2015	SIGMOD	5.5800458e-05
10,110	Adaptive threshold sampling	2022	SIGMOD	5.1347137e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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.00052982574
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
1,888	Aurora: A Data Stream Management System	2003	SIGMOD	9.5338565e-05
2,013	Space Efficient Mining of Multigraph Streams	2005	PODS	9.3068345e-05
2,218	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.9331834e-05
2,610	Maintaining Time-Decaying Stream Aggregates	2003	PODS	8.347507e-05
2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.2108958e-05
2,808	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1006881e-05
3,044	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.820774e-05
4,896	User-Defined Aggregate Functions: Bridging Theory and Practice	2006	SIGMOD	6.4548696e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,934	Ranking Large Temporal Data	2012	VLDB
2	2,218	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS
3	3,599	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB
4	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
5	2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
6	7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
7	551	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD
8	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
9	11,460	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB
10	2,610	Maintaining Time-Decaying Stream Aggregates	2003	PODS