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: hd20d3d4546e63252
Venue: PODS
Year: 2008
Pagerank: 5.9483023e-05
Overall Rank: 5,917 | 60.22%
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,446	Fast Manhattan Sketches in Data Streams	2010	PODS	6.5969248e-05
7,751	Quality-Driven Continuous Query Execution over Out-of-Order Data Streams	2015	SIGMOD	5.4595244e-05
10,338	Adaptive threshold sampling	2022	SIGMOD	5.0195045e-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.00052121228
710	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014608975
1,946	Aurora: A Data Stream Management System	2003	SIGMOD	9.3249193e-05
2,054	Space Efficient Mining of Multigraph Streams	2005	PODS	9.1135465e-05
2,260	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.7353589e-05
2,659	Maintaining Time-Decaying Stream Aggregates	2003	PODS	8.161764e-05
2,750	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.0573403e-05
2,875	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	7.9193665e-05
3,094	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6533343e-05
5,012	User-Defined Aggregate Functions: Bridging Theory and Practice	2006	SIGMOD	6.3145331e-05

Semantically Similar Papers

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