Together is Better: Heavy Hitters Quantile Estimation
Open Access
- 26 May 2023
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (1) , 1-25
Abstract
Stream monitoring is fundamental in many data stream applications, such as financial data trackers, security, anomaly detection, and load balancing. In that respect, quantiles are of particular interest, as they often capture the user's utility. For example, if a video connection has high tail (e.g., 99'th percentile) latency, the perceived quality will suffer, even if the average and median latencies are low. In this work, we consider the problem of approximating the per-item quantiles. Elements in our stream are (ID, value) tuples, and we wish to track the quantiles for each ID. Existing quantile sketches are designed for a plain number stream (i.e., containing just a value). While one could allocate a separate sketch instance for each ID, this may require an infeasible amount of memory. Instead, we consider tracking the quantiles for the heavy hitters (most frequent items), which are often considered particularly important, without knowing them beforehand. We first present a couple of simple and effective algorithms that serve as baselines, a sampling approach and a sketching approach. Then, we present SQUAD, an algorithm that combines sampling and sketching while improving the asymptotic space complexity. Intuitively, SQUAD uses a background sampling process to capture the behaviour of the quantiles of an item before it is allocated with a sketch, thereby allowing us to use fewer samples and sketches. The algorithms are rigorously analyzed, and we demonstrate SQUAD's superiority using extensive~simulations on real-world traces.Keywords
Funding Information
- ISF (3119/21)
- Technion HPI research school
This publication has 37 references indexed in Scilit:
- Volumetric Hierarchical Heavy Hitters2018
- Optimal elephant flow detection2017
- Quantiles over data streams: experimental comparisons, new analyses, and further improvementsThe VLDB Journal, 2016
- Weighted Random Sampling over Data Streams2015
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities2015
- Space-Efficient Estimation of Statistics Over Sub-Sampled StreamsAlgorithmica, 2015
- Optimal Tracking of Distributed Heavy Hitters and QuantilesAlgorithmica, 2011
- Methods for finding frequent items in data streamsThe VLDB Journal, 2009
- Space-efficient Relative Error Order Sketch over Data Streams2006
- Diamond in the rough2004