# Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees

arXiv: https://arxiv.org/abs/2304.07652 · HTML: https://mlsanity.com/paper/2304.07652/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 14 references that are in the map.
- First posted on arXiv 15 Apr 2023.

## Builds on (most cited first, 7 of 7)

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [SOSD: A Benchmark for Learned Indexes](https://mlsanity.com/paper/1911.13014/) (2019)
- [Optimal Quantile Approximation in Streams](https://mlsanity.com/paper/1603.05346/) (2016)
- [Streaming Quantiles Algorithms with Small Space and Update Time](https://mlsanity.com/paper/1907.00236/) (2019)
- [Theory meets Practice at the Median: a worst case comparison of relative error quantile algorithms](https://mlsanity.com/paper/2102.09299/) (2021)

## Abstract (arXiv)

An varepsilon-approximate quantile sketch over a stream of n inputs approximates the rank of any query point q - that is, the number of input points less than q - up to an additive error of varepsilon n, generally with some probability of at least 1 - 1/poly(n), while consuming o(n) space. While the celebrated KLL sketch of Karnin, Lang, and Liberty achieves a provably optimal quantile approximation algorithm over worst-case streams, the approximations it achieves in practice are often far from optimal. Indeed, the most commonly used technique in practice is Dunning's t-digest, which often achieves much better approximations than KLL on real-world data but is known to have arbitrarily large errors in the worst case. We apply interpolation techniques to the streaming quantiles problem to attempt to achieve better approximations on real-world data sets than KLL while maintaining similar guarantees in the worst case.