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

TopN sort algorithm based on multiple filtering

作　　者：张军[1] 杨家海[1] 王继龙[1] 

机构地区：[1]清华大学信息网络工程研究中心,北京100084

出　　处：《清华大学学报（自然科学版）》2006年第4期604-608,共5页Journal of Tsinghua University(Science and Technology)

基　　金：国家"八六三"高技术项目(2003AA103110)

摘　　要：为了解决传统T opN统计算法性能远远落后于实际需求的矛盾,该文针对T opN统计特征进行研究,并提出一种基于多次过滤的T opN统计算法M F-T opN。该算法首先从原始数据集中随机采样,得到k×N个元素的采样集合,再从该采样集合中查找从大到小的第N个元素;利用此记录作为阈值,对原始数据集进行过滤,淘汰掉低于该阈值的元素;重复上述操作,直到剩余的数据元素个数小于k×N为止。最后对剩余的数据元素进行排序,输出前N个。理论分析和实验结果证明M F-T opN在时间性能上比传统的T opN算法(如基于堆的排序算法)提高了50%左右。Abst A TopN sort algorithm based on multiple filtering was developed to improve the performance of the conventional TopN sort algorithm. The algorithm first constructs a sampling set of k × N elements by randomly sampling the original dataset. The algorithm then finds the N^th element （in decreasing order） from the sampling set, which is used to filter out elements of the original dataset that are smaller than this element. This process is repeated till the number of elements in the original dataset is less than k × N. The algorithm then sorts the remaining elements in the original dataset using quieksort and outputs the first N elements. A theoretical analysis and sample comparisons show that the temporal performance of this TopN algorithm is about 50% better than conventional TopN algorithms, such as heapsort.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TP393[自动化与计算机技术—计算机科学与技术]