PBSketch: Finding Periodic Burst Items in Data Streams

Detecting periodic burst (PB) items in data streams is crucial for applications like rate limiting but remains unexplored. % While combining existing sketch algorithms offers a baseline, it suffers from significant inaccuracy and inefficiency. In this paper, we propose PBSketch, the first dedicated sketch algorithm designed for detecting PB items in real time. Its key techniques mainly include: 1) a two-stage hierarchical structure that efficiently maintains potential burst items and discards those without potential; 2) a fine-grained PB selection mechanism during window processing, coupled with the Window Smoothing Processing optimization to amortize performance overhead and eliminate processing spikes. % We provide its error bounds through rigorous theoretical analysis. Our extensive experiments show that PBSketch outperforms the baseline solution in accuracy and speed. By deploying it on an FPGA platform, the throughput is further significantly improved. Moreover, it effectively optimizes a practical application of rate limiting, clearly improving performance with almost negligible overhead.