An Efficient Adaptive Noise Correction Framework for Size Measurement over Data Streams

With the rapid development of the Internet of Things (IoT), massive high-speed data streams are produced every moment, making accurate size estimation a challenging task. Many sketches have been proposed to summarize real-time high-speed data streams and provide per-flow size estimations. However, sketches have to share the memory units to fit in limited on-chip space, inevitably introducing noises to all flows and resulting in over-estimation problems. Prior work adopts an average denoising strategy to remove the same noise from raw sketch estimations. However, they overlook that the noise distribution is highly skewed, leading to inaccurate results for most flows. This paper proposes an efficient Adaptive Noise Correction (ANC) framework, which analyzes the noise of each flow on a case-by-case basis and provides accurate size estimations. The key of our design is to build an ML model to predict a weight coefficient that indicates the noises in raw estimations, which is conducted for each flow by analyzing the neighbor flows whose memory units overlap with the given flow. Then we introduce a novel Probabilistic Cold Filter to block the tiny flows and assist in noise correction. Experimental results based on real Internet traces show that our framework can effectively remove the noises for different sketches, showing better estimation accuracy than the state-of-the-art.