我正在研究数值的时间序列，例如温度传感器产生的数值。我想过滤这些值，粗略地选择那些形成例如收到值的前 10%。
记录所有样本并使用任何众所周知的算法提取 k 最大值的明显解决方案在我的情况下是不可能的，原因有两个:
系列可能是无限的，内存绝对不是。
我希望该算法可以实时使用，或者至少可以在具有预定延迟的流模式下使用。
值的分布不正态，也不符合我所知道的任何众所周知的分布。我随时可用的指标包括已收到的值的均值、方差和偏度。
不同于this question ，我不需要完美的准确性，尽管我希望能够调整选择算法的参数。
我相信在单 channel 可变比特率 (VBR) 媒体编解码器中使用了类似的东西，通过确定可用位数来为每个帧分配可用带宽。不幸的是，我研究的所有 VBR 算法都过于关注 DSP 和媒体流，以至于我无法理解和/或实现。
是否有任何已知的算法可以帮助我处理这个问题？任何能让我朝着正确方向前进的提示都将不胜感激。
最佳答案
如果您决定只对最后 10N 项感兴趣，您可以使用两个堆，一个大小为 N，另一个堆大小为 9N，以跟踪最后 10N 中的 N 个最高项。当您看到新项目时，首先删除最旧的项目。如果它来自小堆，则从大堆中取出最大的元素并将其放入小堆中。现在查看新项目，要么将其直接放入大堆中，要么从小堆中取出最小的项目并将其转移到大项目中，然后再将新项目放入小堆中。
任何时候你都有一小堆高项目和一大堆低项目，你知道最新的项目是否在这 10N 个中的前 10%。
但这真的是你想要的吗？请注意，如果您的样本在比 10N 样本大得多的一段时间内稳定上升然后稳定下降，那么将近一半的时间最新项目将位于前 10% - 事实上它将是内存中看到的最大项目10N 项。
已经有关于寻找流数据的近似分位数的学术论文。其中之一是 "Effective Computation of Biased Quantiles over Data Streams" , Cormode、Korn、Muthukrishnan 和 Srivastava 着
关于algorithm - 用于选择时间序列前 X% 的在线/流式算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7402672/