  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.
