| 基于多次过滤的TopN统计算法 |
| |
| 引用本文： | 张军,杨家海,王继龙.基于多次过滤的TopN统计算法[J].清华大学学报(自然科学版),2006,46(4):604-608. |
| |
| 作者姓名： | 张军 杨家海 王继龙 |
| |
| 作者单位： | 清华大学,信息网络工程研究中心,北京,100084 |
| |
| 基金项目： | 高比容电子铝箔的研究开发与应用项目 |
| |
| 摘 要： | 为了解决传统T opN统计算法性能远远落后于实际需求的矛盾,该文针对T opN统计特征进行研究,并提出一种基于多次过滤的T opN统计算法M F-T opN。该算法首先从原始数据集中随机采样,得到k×N个元素的采样集合,再从该采样集合中查找从大到小的第N个元素;利用此记录作为阈值,对原始数据集进行过滤,淘汰掉低于该阈值的元素;重复上述操作,直到剩余的数据元素个数小于k×N为止。最后对剩余的数据元素进行排序,输出前N个。理论分析和实验结果证明M F-T opN在时间性能上比传统的T opN算法(如基于堆的排序算法)提高了50%左右。
|
| 关 键 词： | TopN统计 网络测量 多次过滤 流量统计 |
| 文章编号： | 1000-0054(2006)04-0604-05 |
| 修稿时间： | 2005年3月24日 |
TopN sort algorithm based on multiple filtering |
| |
| ZHANG Jun,YANG Jiahai,WANG Jilong.TopN sort algorithm based on multiple filtering[J].Journal of Tsinghua University(Science and Technology),2006,46(4):604-608. |
| |
| Authors: | ZHANG Jun YANG Jiahai WANG Jilong |
| |
| Abstract: | |
| |
| Keywords: | TopN sort network measurement multiple filtering traffic statistics |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
