论文部分内容阅读
频繁项挖掘算法在网络监控领域具有广泛的应用。利用频繁项挖掘算法识别网络中的大流量,可以实时检测网络中的异常及拥塞情况、辅助服务商流量计费等。但是,随着骨干网络链路带宽和流量的增长,网络流监控系统对性能要求越来越高。虽然目前已有单数据项处理时间O(1)的频繁项挖掘算法,但是单核CPU主频已经接近极限,无法满足骨干网中网络监控的需求。近年来,多核处理器发展迅速,即使是标准的工作站也有4-8核,具有很强的并行计算能力。本文试图设计并行的频繁项挖掘算法,充分利用多核处理器的并行计算能力,从而提高频繁项挖掘算法的吞吐量。
论文首先介绍了常见的频繁项挖掘算法,对现存的并行频繁项挖掘算法进行了分析,并总结了它们的优点和缺点。在这个基础上,本文提出了自己的并行频繁项挖掘算法,该算法基于无共享设计,即本地线程不共享数据,也不需要像精度合成法那样需要向汇聚线程发送数据项。接着论文对算法的正确性进行了证明,并详细介绍了本算法的各个模块的实现过程和技术细节。最后论文验证了本算法在不同的数据分发策略下的性能,结果表明,本算法在使用hash法和轮转法进行数据分发时,算法的吞吐量超过其它的并行设计,最大加速比达到了物理CPU核数。