基于多次过滤的TopN统计算法

为了解决传统T opN统计算法性能远远落后于实际需求的矛盾,该文针对T opN统计特征进行研究,并提出一种基于多次过滤的T opN统计算法M F-T opN。该算法首先从原始数据集中随机采样,得到k×N个元素的采样集合,再从该采样集合中查找从大到小的第N个元素;利用此记录作为阈值,对原始数据集进行过滤,淘汰掉低于该阈值的元素;重复上述操作,直到剩余的数据元素个数小于k×N为止。最后对剩余的数据元素进行排序,输出前N个。理论分析和实验结果证明M F-T opN在时间性能上比传统的T opN算法(如基于堆的排序算法)提高了50%左右。