Lune

VLDB2021Top-tier venue

PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy

Siyuan Sheng, Qun Huang, Sa Wang, Yungang Bao

Abstract

Computing per-key aggregation is indispensable in streaming data analysis formulated as two phases, an update phase and a recovery phase. As the size and speed of data streams rise, accurate per-key information is useful in many applications like anomaly detection, attack prevention, and online diagnosis. Even though many algorithms have been proposed for per-key aggregation in stream processing, their accuracy guarantees only cover a small portion of keys. In this paper, we aim to achieve nearly full accuracy with limited resource usage. We follow the line of sketch-based techniques. We observe that existing methods suffer from high errors for most keys. The reason is that they track keys by complicated mechanism in the update phase and simply calculate per-key aggregation from some specific counter in the recovery phase. Therefore, we present PR-Sketch, a novel sketching design to address the two limitations. PR-Sketch builds linear equations between counter values and per-key aggregations to improve accuracy, and records keys in the recovery phase to reduce resource usage in the update phase. We also provide an extension called fast PR-Sketch to improve processing rate further. We derive space complexity, time complexity, and guaranteed error probability for both PR-Sketch and fast PR-Sketch. We conduct trace-driven experiments under 100K keys and 1M items to compare our algorithms with multiple state-of-the-art methods. Results demonstrate the resource efficiency and nearly full accuracy of our algorithms.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

4 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • BFES: Towards Optimal Bayesian Frequency Estimation Sketches in Data-Streams cites Bayesian Sketches for Volume Estimation in Data Streams
  • CounterSnake: A lossless and generalized compression framework for diverse sketches cites CodingSketch: A Hierarchical Sketch with Efficient Encoding and Recursive Decoding
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. CodingSketch: A Hierarchical Sketch with Efficient Encoding and Recursive DecodingQizhi Chen, Yisen Hong, Yuhan Wu, Tong Yang et al.ICDE 2024 · 5 citations
  2. Bayesian Sketches for Volume Estimation in Data StreamsFrancesco Da Dalt, Simon Scherrer, Adrian PerrigVLDB 2023 · 5 citations
  3. BFES: Towards Optimal Bayesian Frequency Estimation Sketches in Data-StreamsFrancesco Da Dalt, Adrian PerrigICDE 2025
  4. CounterSnake: A lossless and generalized compression framework for diverse sketchesXunpeng Liu, Qun Huang, Yaojing Wang, Lihua Miao et al.VLDB 2026

Builds on1

  1. OmniMon: Re-architecting Network Telemetry with Resource Efficiency and Full AccuracyQun Huang, Haifeng Sun, Patrick P. C. Lee, Wei Bai et al.SIGCOMM 2020 · 109 citations

Related papers

  1. HistSketch: A Compact Data Structure for Accurate Per-Key Distribution MonitoringJintao He, Jiaqi Zhu, Qun HuangICDE 2023 · 21 citations
  2. PBSketch: Finding Periodic Burst Items in Data StreamsZhuochen Fan, Zhongxian Liang, Zirui Liu, Dayu Wang et al.KDD 2026
  3. OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary PredicatesWieger R. Punter, Odysseas Papapetrou, Minos N. GarofalakisVLDB 2024 · 10 citations
  4. Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join QueriesMike Heddes, Igor Nunes, Tony Givargis, Alex NicolauSIGMOD 2024 · 5 citations
  5. XY-Sketch: on Sketching Data Streams at Web ScaleYongqiang Liu, Xike XieWWW 2021 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines