  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 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.
