FIFA: A Forest-Based Sliding Window Aggregation Scheme for Out-of-Order Data Streams

Sliding window aggregation is a core operation in data stream analysis that extracts summaries from the most recent data stream. An evict or insert of the window can be handled in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(1)$</tex-math></inline-formula> for in-order data streams. However, real-world data streams are typically disordered due to network delays. To process out-of-order data streams, existing methods primarily use a tree to maintain the sliding windows. Since the complexity of the tree is related to the window size, the performance of these methods will drop sharply or become unavailable when facing a big window. To overcome the limitation of existing methods, this paper presents Finger B-Trees Forest Aggregation (FIFA). This novel forest-based sliding window aggregation scheme optimally handles out-of-order data streams. At its heart, FIFA uses aggregation forest to extend Finger B-Trees. Specifically, FIFA evenly divides a window into several chunks and constructs a separate tree to maintain each chunk. When an out-of-order item arrives, FIFA first locates the corresponding chunk of the item and then uses Finger B-Trees to insert it into the window efficiently. Chunking reduces the complexity of the tree and the coupling of aggregation results by isolating items within windows. Thus, an insert or evict takes amortized <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(c)$</tex-math></inline-formula> in the worst case, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$c$</tex-math></inline-formula> is the size of each chunk. Finally, extensive experiments based on real-world data demonstrate that FIFA achieves an average 2-fold throughput improvement on out-of-order data streams compared with the state-of-the-art (SOTA) aggregation schemes.