# A Survey of Approximate Quantile Computation on Large-scale Data (Technical Report)

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2020.

## Built on by (most cited first, 3 of 3)

- [AcME -- Accelerated Model-agnostic Explanations: Fast Whitening of the Machine-Learning Black Box](https://mlsanity.com/paper/2112.12635/) (2021)
- [Fast Online Value-Maximizing Prediction Sets with Conformal Cost Control](https://mlsanity.com/paper/2302.00839/) (2023)
- [A Novel Approach in Solving Stochastic Generalized Linear Regression via Nonconvex Programming](https://mlsanity.com/paper/2401.08488/) (2024)

## Abstract (arXiv)

As data volume grows extensively, data profiling helps to extract metadata of large-scale data. However, one kind of metadata, order statistics, is difficult to be computed because they are not mergeable or incremental. Thus, the limitation of time and memory space does not support their computation on large-scale data. In this paper, we focus on an order statistic, quantiles, and present a comprehensive analysis of studies on approximate quantile computation. Both deterministic algorithms and randomized algorithms that compute approximate quantiles over streaming models or distributed models are covered. Then, multiple techniques for improving the efficiency and performance of approximate quantile algorithms in various scenarios, such as skewed data and high-speed data streams, are presented. Finally, we conclude with coverage of existing packages in different languages and with a brief discussion of the future direction in this area.