A Survey of Approximate Quantile Computation on Large-Scale Data

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

Full description

Saved in:
Bibliographic Details
Published in:IEEE access 2020, Vol.8, p.34585-34597
Main Authors: Chen, Zhiwei, Zhang, Aoqian
Format: Article
Language:English
Subjects:
Algorithms
approximate quantile
Approximation algorithms
Approximation error
Complexity theory
Computation
Computational modeling
Data profiling
Data transmission
Distributed databases
distributed model
Metadata
order statistics
Quantiles
streaming model
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2169-3536
2169-3536
DOI:10.1109/ACCESS.2020.2974919