PBSketch: Finding Periodic Burst Items in Data Streams (ACM SIGKDD, 2026)

  • Authors: Zhuochen Fan, Zhongxian Liang, Zirui Liu, Dayu Wang, Dong Wen, Wenjun Li*, Tong Yang, Yuzhou Liu, and Weizhe Zhang
  • Zhuochen Fan, Zhongxian Liang, and Zirui Liu are co-first authors of this paper. Wenjun Li is the corresponding author of this paper (wenjunli@pku.org.cn).
  • This work was conducted under the supervision of Tong Yang (PhD advisor of Zhuochen Fan and Zirui Liu) and Wenjun Li (PhD advisor of Zhongxian Liang).

Abstract

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.

Downloads

News

2025.12.5: The source code of PBSketch has been uploaded.

2025.12.1: The website of PBSketch is under construction and will be finished soon.

Contact

E-mail: wenjunli@pku.org.cn.