2020/01/01 by Zhiwei Chen, Aoqian Zhang · 1 citation
Computer Science · Mathematics · #Advanced Database Systems and Queries #Algorithm #Computation #Computer science #Data mining #Data stream #Data stream mining #Data structure #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Mathematics #Metadata #Order statistic #Profiling (computer programming) #Quantile #Scale (ratio) #Statistic #Statistics #cs.DB #cs.DS
paper · pdf · doi:10.1109/access.2020.2974919
published as IEEE Access 8 (2020): 34585-34597
openalex publication_date 2020/01/01 · openalex created_date 2020/03/06 · arxiv created 2020/04/17 · arxiv updated 2020/06/29 · openalex updated_date 2026/08/05
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.