An efficient framework for parallel and continuous frequent item monitoring

作者：Zhang, Yu^*; Sun, Yue; Zhang, Jianzhong; Xu, Jingdong; Wu, Ying

来源：Concurrency and Computation: Practice and Experience (CCPE) , 2014, 26(18): 2856-2879.

DOI：10.1002/cpe.3182

• frequent items
• parallel algorithms
• weighted data streams
• multi-core processors

In high-speed network monitoring, the ever-growing traffic calls for a high-performance solution for the computation of frequent items. The increasing number of cores in the current commodity multi-core processors opens up new opportunities in parallelization. In this paper, we present a novel precision integrated framework (PRIF) that exploits the great parallel capability of multi-cores to speed up the famous frequent algorithm. PRIF equally distributes the input data stream into sub-threads that use the optimized weighted frequent algorithm to track local frequent items. The items with frequency increments exceeding a pre-defined threshold are sent to a merging thread which is able to return the global continuous epsilon-deficient frequent items. The theoretical correctness and complexity analyses are presented. Experiments with real and synthetic traces confirm the theoretical analyses and demonstrate the excellent performance as well as the effects of parameters and data skewness. The results show that PRIF is able to provide continuous frequent items and near-linear speedup at the cost of greater memory use.

• 出版日期2014-12-25
• 单位天津市农业科学院; 南开大学