CBA Sketch: A Sketching Algorithm Mining Persistent Batches in Data Streams

Batch is a vital data pattern commonly observed in data streams, representing a group of identical items that occur closely together. However, existing works primarily focus on the periodicity mining of batches, neglecting other numerous essential patterns. In this paper, we introduce the concept of persistent batch, a particular pattern in data streams where multiple occurrences of the same batch happen in at least k out of t measurement periods. Mining persistent batches holds significance in applications such as APT detection, DDoS detection, and Click Fraud detection, etc. To fill up the gap of the prior art, we propose CBA Sketch, a memory-efficient sketching algorithm that effectively mines persistent batches from data streams. The CBA Sketch utilizes a Circular-Time Sketch (CT-Sketch) to accurately calculate item intervals and capture batches with limited memory resources. We incorporate the carefully designed Bloom Filter-based Existence Recorder (BE Recorder) and Approximate Size Recorder (AS Recorder) to preserve batch information. Additionally, we introduce a novel metric called dual-mean size to provide measurements for persistent batch sizes. Extensive experiments demonstrate that our CBA Sketch outperforms the strawman solution about $$62 \times $$ in terms of average relative error and $$2 \times $$ in terms of throughput.