大规模实时分位数计算——Quantile Sketches 简史

摘要

这篇文章从 Sketch 结构的定义和特性出发，解释了 Sketch 结构如何解决大数据计算场景中海量数据计算痛点，明确了 Quantile 问题的定义。其次，结合大数据开发中常用组件，讨论了如何将 Quantile Sketch 算法带入工程实践中。本文着重介绍了 Quantile Sketches 算法原理，涵盖了算法发展的几个重要阶段和重要产物。笔者尝试用最简单的语言和逻辑讲解了每一个算法的核心思想、优点和缺陷，尝试将多种算法的发展串联起来，方便没有相关背景的人从零开始了解这个领域。