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: 12003
Venue: VLDB
Year: 2019
Pagerank: 6.1094861e-05
Overall Rank: 5,719 | 60.77%
DOI: 10.14778/3339490.3339499

Incoming Non-self Citations Over Time

Authors

1. Kanat Tangwongsan (Mahidol University International College)
2. Martin Hirzel (IBM)
3. Scott Schneider (IBM)

BibTeX Citation

@article{tangwongsan_vldb19,
        title = {{Optimal and General Out-of-Order Sliding-Window Aggregation}},
        author = {Tangwongsan, Kanat and Hirzel, Martin and Schneider, Scott},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {10},
        pages = {1167--1180},
        doi = {10.14778/3339490.3339499},
        url = {https://doi.org/10.14778/3339490.3339499},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,389	Consistency and Completeness: Rethinking Distributed Stream Processing in Apache Kafka	2021	SIGMOD	6.7304854e-05
4,820	LightSaber: Efficient Window Aggregation on Multi-core Processors	2020	SIGMOD	6.493623e-05
8,685	Efficient Evaluation of Arbitrarily-Framed Holistic SQL Aggregates and Window Functions	2022	SIGMOD	5.3849617e-05
9,947	Optimizing Time Series Queries with Versions	2024	SIGMOD	5.1915905e-05
11,460	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB	5.093636e-05
11,619	SWS: A Complexity-Optimized Solution for Spatial-Temporal Kernel Density Visualization	2022	VLDB	5.093636e-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
127	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030738755
224	MillWheel: Fault-Tolerant Stream Processing at Internet Scale	2013	VLDB	0.00024130894
361	The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing	2015	VLDB	0.00020138717
424	Flexible Time Management in Data Stream Systems	2004	PODS	0.0001870735
451	Mergeable Summaries	2012	PODS	0.00018151445
899	Consistent Streaming Through Time: A Vision for Event Stream Processing	2007	CIDR	0.00013337792
1,223	Out-of-Order Processing: A New Architecture for High-Performance Stream Systems	2008	VLDB	0.00011602265
1,263	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB	0.00011425419
1,354	On-the-Fly Sharing for Streamed Aggregation	2006	SIGMOD	0.00011057534
1,472	M4: A Visualization-Oriented Time Series Data Aggregation	2014	VLDB	0.00010668946
1,639	Summingbird: A Framework for Integrating Batch and Online MapReduce Computations	2014	VLDB	0.00010155021
1,945	Continuous Analytics Over Discontinuous Streams	2010	SIGMOD	9.4348569e-05
2,479	Microsoft CEP Server and Online Behavioral Targeting	2009	VLDB	8.521563e-05
2,802	General Incremental Sliding-Window Aggregation	2015	VLDB	8.1093063e-05
3,342	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	7.4999147e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,513	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD
2	3,599	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB
3	2,576	Optimal Sampling from Sliding Windows	2009	PODS
4	8,603	Stream Frequency over Interval Queries	2019	VLDB
5	4,517	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB
6	1,263	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB
7	2,218	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS
8	5,802	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS
9	2,802	General Incremental Sliding-Window Aggregation	2015	VLDB
10	11,460	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB