TSYS School Computer Scientist Yi Zhou Develops Novel Algorithm to Improve Bulk Cache Evictions

Sliding window aggregation, which extracts summaries from data streams, is a core operation in streaming analysis. However, real-world data streams often involve out-of-order data and exhibit burst data characteristics, which pose performance challenges to these sliding window algorithms. To address this challenging issue, a new study by TSYS School computer scientist Yi Zhou and colleagues Jianjun Li, Yuhui Deng, Jiande Huang and Qifen Yang of Jinan University, along with Geyong Min of the University of Exeter, proposes Gecko - a novel sliding window aggregation algorithm that supports bulk cache eviction. According to the study, set to appear in a future issue of IEEE Transactions on Knowledge and Data Engineering, Gecko leverages a granular-based eviction strategy for various bulk sizes, enabling efficient bulk eviction while maintaining the performance close to that of in-order stream algorithms for single evictions. For large data bulks, Gecko performs coarse-grained eviction at the chunk level, followed by fine-grained eviction using leftward binary tree aggregation (LTA) as a complementary method. Moreover, Gecko partitions data based on chunks to prevent the impacts of out-of-order data on other chunks, thereby enabling efficient handling of out-of-order data streams. Extensive experiments conducted by Zhou et al. to evaluate the performance of Gecko demonstrate its superior performance over other solutions. In real-world data scenarios, Gecko performs 1.7 to 3.5 times better than the state-of-the-art algorithm while also demonstrating the best latency performance among all compared schemes.