一种新的数据结构,用于准确地在线累积基于排名的统计数据,如分位数和修剪均值
一种用于准确在线累积基于排名的统计数据(如分位数)的新数据结构 以及修剪平均值。 t-digest 算法对并行程序也非常友好,使其 在使用 Apache Spark 等技术实现的 MapReduce 和并行流式应用中非常有用。
t-digest 构建算法使用一种 1 维 k-均值聚类的变体，生成一个非常紧凑的数据结构，可用于精确估计量位。 该 t-digest 数据结构可用于估计量位、计算其他秩统计量，甚至估计相关度量，如修剪均值。 与用于此目的的以前的摘要算法相比，t-digest 的优点在于它能够处理具有完整浮点精度的数据。 仅做少量修改，t-digest 就可以处理任何有序集中的值，对于这些值，我们可以计算类似于均值的东西。 t-digest 生成的量位估计的精度比替代的摘要算法高出一个数量级，尽管 t-digest 更为紧凑，尤其是在序列化后。
总而言之，t-digest 的特别有趣的特点是： * 序列化时的摘要较小 * 可以处理双精度浮点数以及整数 * 为极端量化值提供每百万分之一的精度，而中等量化值通常精度为 <1000 ppm * 速度非常快（每次加法约 140 ns） * 非常简单（总共约 5000 行代码，仅最先进的实现就有 <1000 行） * 具有 90% 以上的测试覆盖率的参考实现 * 由于摘要可以合并，因此非常容易与 MapReduce 结合使用 * 在初始创建后不需要动态分配内存（仅支持“MergingDigest”） * 没有运行时依赖
最近的新闻 ---------- 《软件对 t-digest 的影响》一文（可免费阅读！）在《软件影响》上发表了，主要针对此次参考实现。 最近，在 t-digest 方面发生了很多事情。 最近，在许多人的帮助下，
暂无开放 Issues，或尚未同步最近议题。