algorithm - 动态监控分位数的算法

Question

我想估计一些数据的分位数。数据太大了，内存放不下。新数据不断涌入。有没有人知道一种算法，可以在内存和计算非常有限的情况下监控迄今为止观察到的数据的分位数？我发现P2 算法很有用。但它不适用于我的数据，这是非常重尾分布的。

Answer 1

考虑将值空间划分为多个 bin，每个 bin 包含一个范围内的值的计数。

您可以尝试在您期望查找分位数的点周围使箱变小。

如果您使垃圾箱的数量足够大，这应该可以很好地工作。