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: 11816
Venue: VLDB
Year: 2019
Pagerank: 5.1917864e-05
Overall Rank: 6,133 | 57.38%
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,824	Consistency and Completeness: Rethinking Distributed Stream Processing in Apache Kafka	2021	SIGMOD	5.8902451e-05
5,357	LightSaber: Efficient Window Aggregation on Multi-core Processors	2020	SIGMOD	5.5512343e-05
8,697	Efficient Evaluation of Arbitrarily-Framed Holistic SQL Aggregates and Window Functions	2022	SIGMOD	4.4607582e-05
9,795	Optimizing Time Series Queries with Versions	2024	SIGMOD	4.2777144e-05
11,263	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB	4.1905499e-05
11,424	SWS: A Complexity-Optimized Solution for Spatial-Temporal Kernel Density Visualization	2022	VLDB	4.1905499e-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.00035714897
314	MillWheel: Fault-Tolerant Stream Processing at Internet Scale	2013	VLDB	0.00028059664
398	Mergeable Summaries	2012	PODS	0.00024383201
433	Flexible Time Management in Data Stream Systems	2004	PODS	0.00023336894
536	The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing	2015	VLDB	0.00020651621
1,141	Consistent Streaming Through Time: A Vision for Event Stream Processing	2007	CIDR	0.00013703749
1,549	Out-of-Order Processing: A New Architecture for High-Performance Stream Systems	2008	VLDB	0.00011407374
1,557	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB	0.00011381807
1,791	On-the-Fly Sharing for Streamed Aggregation	2006	SIGMOD	0.0001052731
1,793	Summingbird: A Framework for Integrating Batch and Online MapReduce Computations	2014	VLDB	0.00010522029
1,804	M4: A Visualization-Oriented Time Series Data Aggregation	2014	VLDB	0.00010481427
2,204	Continuous Analytics Over Discontinuous Streams	2010	SIGMOD	9.2986554e-05
2,884	Microsoft CEP Server and Online Behavioral Targeting	2009	VLDB	7.9658952e-05
3,425	General Incremental Sliding-Window Aggregation	2015	VLDB	7.1042928e-05
3,818	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	6.7279318e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,773	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010600438
4,328	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.2765138e-05
2,807	Optimal Sampling from Sliding Windows	2009	PODS	8.096649e-05
8,592	Stream Frequency over Interval Queries	2019	VLDB	4.4848323e-05
4,647	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB	6.01732e-05
1,557	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB	0.00011381807
2,403	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.8738166e-05
5,602	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	5.4153555e-05
3,425	General Incremental Sliding-Window Aggregation	2015	VLDB	7.1042928e-05
11,263	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB	4.1905499e-05