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

摘要：

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

关键词：TopN统计、网络测量、多次过滤、流量统计

所属期刊栏目：46

分类号：TP301;TP393(计算技术、计算机技术)

资助基金：高比容电子铝箔的研究开发与应用项目2003AA103110

在线出版日期：2006-06-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：604-608