实验室博士生黄建德，邓玉辉老师等人联合撰写的论文《FIFA: A Forest-based Sliding Window Aggregation Scheme for Out-of-Order Data Streams》被大数据领域的权威国际学术期刊《IEEE Transactions on Big Data》录用。论文将于2025年正式发表。
论文摘要如下：
Abstract—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 O(1) 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 O(c) in the worst case, where c 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.