Shahout, Rana;
Friedman, Roy;
Basat, Ran Ben;
(2022)
SQUAD: Combining Sketching and Sampling Is Better than Either for Per-item Quantile Estimation.
In:
SYSTOR '22: Proceedings of the 15th ACM International Conference on Systems and Storage.
ACM
Preview |
Text
2201.01958.pdf - Other Download (1MB) | Preview |
Abstract
Latency quantiles measurements are essential as they often capture the user's utility. For example, if a video connection has high tail 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, latency) tuples, and we wish to track the latency quantiles for each ID. Existing quantile sketches are designed for a single number stream (e.g., containing just the latency). 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 simple sampling algorithm that serves as a benchmark. Then, we design an algorithm that augments a quantile sketch within each entry of a heavy hitter algorithm, resulting in similar space complexity but with a deterministic error guarantee. Finally, we present SQUAD, a method that combines sampling and sketching while improving the asymptotic space complexity. Intuitively, SQUAD uses a background sampling process to capture the behaviour of the latencies of an item before it is allocated with a sketch, thereby allowing us to use fewer samples and sketches. Our solutions are rigorously analyzed, and we demonstrate the superiority of our approach using extensive simulations.
| Type: | Proceedings paper |
|---|---|
| Title: | SQUAD: Combining Sketching and Sampling Is Better than Either for Per-item Quantile Estimation |
| Event: | SYSTOR '22: 15th ACM International Conference on Systems and Storage |
| ISBN-13: | 978-1-4503-9380-5 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1145/3534056.3535009 |
| Publisher version: | https://doi.org/10.1145/3534056.3535009 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10152893 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
