Identifying super spreaders is a core task in data stream processing. For this purpose, probabilistic data structures called sketches are widely used because they trade memory for estimation accuracy. Many existing sketch-based methods detect super spreaders inside fixed-length intervals known as epochs, clearing the sketch when each epoch ends. However, flushing the sketch in this manner can introduce a transient rebuilding phase during which the accumulated statistics have not yet stabilized. A super spreader that emerges within this interval may therefore be missed. On the other hand, if the stream is measured continuously without ever resetting the sketch, outdated entries build up over time and can reduce accuracy. To address this trade-off, we introduce CycleSketch, a sketch that performs continuous super spreader detection while purging stale data. Concretely, CycleSketch combines a sliding window with a circular queue to keep track of candidate super spreaders and cyclically overwrites aged entries by resetting the slot associated with each new epoch—without globally clearing the count part. To gauge its practical effectiveness, we build and benchmark CycleSketch on both conventional CPU hardware and the OVS virtual switch. On the evaluated traffic traces and under the tested settings, CycleSketch achieves higher measured precision and F1 score than the compared sketch-based detectors, with improvements of 50% and 125%, respectively.

A sketch is a probabilistic data structure that can accurately estimate massive network traffic with a small memory overhead. To improve the measurement accuracy, most sketch-based schemes separate elephant flows from mouse flows to accommodate the skewed network traffic. However, the increased algorithmic complexity often results in a sacrifice of measurement throughput. In addition, some improved sketches may be over-reliant on the skewed distribution of traffic, which results in unstable accuracy. To this end, a novel sketch, called Air Sketch, is proposed in this paper. It treats flows of different sizes as air with different temperatures. Meanwhile, a deterministic replacement strategy is applied to elephant flows. In order to improve throughput, an asymmetric insertion and query algorithm with a global hash is designed. The performance of Air Sketch is evaluated using real traffic transaction datasets, anonymized internet traces, and synthetic Zipf datasets. The experimental results demonstrate that Air Sketch can outperform the best typical measurement methods by up to 27 times in flow size measurement and up to 40 times in elephant flow detection. Additionally, Air Sketch achieves high accuracy and stability while achieving high insertion and query throughput.