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.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
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
Cited by top-tier papers4
- CodingSketch: A Hierarchical Sketch with Efficient Encoding and Recursive DecodingQizhi Chen, Yisen Hong, Yuhan Wu, Tong Yang et al.ICDE 2024 · 5 citations
- Bayesian Sketches for Volume Estimation in Data StreamsFrancesco Da Dalt, Simon Scherrer, Adrian PerrigVLDB 2023 · 5 citations
- BFES: Towards Optimal Bayesian Frequency Estimation Sketches in Data-StreamsFrancesco Da Dalt, Adrian PerrigICDE 2025
- CounterSnake: A lossless and generalized compression framework for diverse sketchesXunpeng Liu, Qun Huang, Yaojing Wang, Lihua Miao et al.VLDB 2026
Builds on1
Related papers
- HistSketch: A Compact Data Structure for Accurate Per-Key Distribution MonitoringJintao He, Jiaqi Zhu, Qun HuangICDE 2023 · 21 citations
- PBSketch: Finding Periodic Burst Items in Data StreamsZhuochen Fan, Zhongxian Liang, Zirui Liu, Dayu Wang et al.KDD 2026
- OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary PredicatesWieger R. Punter, Odysseas Papapetrou, Minos N. GarofalakisVLDB 2024 · 10 citations
- 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
- XY-Sketch: on Sketching Data Streams at Web ScaleYongqiang Liu, Xike XieWWW 2021 · 12 citations
