PSC Sketch: Finding Periodic Spread Changers in High-Speed Data Streams

Periodicity and fluctuation are two crucial characteristics of data streams. This paper investigates a novel data stream pattern called periodic spread changer (PSC flow for short), which refers to the heavy change in the spread of a flow occurring with fixed time intervals. Effectively identifying such flows is essential for many real-world applications, such as anomaly detection and network monitoring. To achieve precise real-time detection of these flows under limited memory resources, we propose a novel structure named PSC Sketch. PSC Sketch firstly performs the spread estimation by removing duplicate data items and filters out those non-potential flows with small spreads. During the measurement period, PSC Sketch detects the spread changers, calculates the time intervals between adjacent heavy changes, and reports the top-k periodic spread changers. Extensive experiments based on four real-world datasets demonstrate that, compared to competing algorithms, PSC Sketch achieves an average of 16.80 times lower average absolute error, 44.93% higher accuracy, and 1.83 times higher throughput.