Optimal and General Out-of-Order Sliding-Window Aggregation

Summary: FiBA enables out-of-order sliding-window agg with varying windows; uses finger search, lazy rebalancing, and pos-aware aggregates. Amortized O(log d) per insert/evict (d to boundary); O(1) in-order, near-O(1) for slight lateness; optimal; range queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11815
Venue: VLDB
Year: 2019
Pagerank: 5.2480159e-05
Overall Rank: 5,971 | 58.47%
DOI: 10.14778/3339490.3339499

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,822	Consistency and Completeness: Rethinking Distributed Stream Processing in Apache Kafka	2021	SIGMOD	5.8959131e-05
5,193	LightSaber: Efficient Window Aggregation on Multi-core Processors	2020	SIGMOD	5.6371049e-05
8,702	Efficient Evaluation of Arbitrarily-Framed Holistic SQL Aggregates and Window Functions	2022	SIGMOD	4.4650384e-05
9,792	Optimizing Time Series Queries with Versions	2024	SIGMOD	4.2818172e-05
11,261	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB	4.1945683e-05
11,421	SWS: A Complexity-Optimized Solution for Spatial-Temporal Kernel Density Visualization	2022	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
191	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00035738595
314	MillWheel: Fault-Tolerant Stream Processing at Internet Scale	2013	VLDB	0.00028084774
402	Mergeable Summaries	2012	PODS	0.00024196343
432	Flexible Time Management in Data Stream Systems	2004	PODS	0.00023368424
538	The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing	2015	VLDB	0.00020678804
1,141	Consistent Streaming Through Time: A Vision for Event Stream Processing	2007	CIDR	0.00013717279
1,551	Out-of-Order Processing: A New Architecture for High-Performance Stream Systems	2008	VLDB	0.00011416058
1,554	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB	0.00011400581
1,788	On-the-Fly Sharing for Streamed Aggregation	2006	SIGMOD	0.00010555742
1,794	Summingbird: A Framework for Integrating Batch and Online MapReduce Computations	2014	VLDB	0.00010532024
1,805	M4: A Visualization-Oriented Time Series Data Aggregation	2014	VLDB	0.00010493299
2,198	Continuous Analytics Over Discontinuous Streams	2010	SIGMOD	9.308495e-05
2,879	Microsoft CEP Server and Online Behavioral Targeting	2009	VLDB	7.9695819e-05
3,378	General Incremental Sliding-Window Aggregation	2015	VLDB	7.1622572e-05
3,815	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	6.7333316e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,784	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010567363
4,080	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.4652983e-05
2,789	Optimal Sampling from Sliding Windows	2009	PODS	8.1249652e-05
8,594	Stream Frequency over Interval Queries	2019	VLDB	4.4891331e-05
4,649	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB	6.0236001e-05
1,554	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB	0.00011400581
2,404	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.8837279e-05
5,594	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	5.4192122e-05
3,378	General Incremental Sliding-Window Aggregation	2015	VLDB	7.1622572e-05
11,261	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB	4.1945683e-05