在分布式数据流中查找近期频繁项方法的研究  

Finding Recently Frequent Item in Distributed Data Stream

作　　者：任家东[1] 李可[1] 冯佳音[1] 杨楠[2] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]燕山大学电气工程学院,河北秦皇岛066004

出　　处：《计算机科学》2008年第3期206-208,共3页Computer Science

摘　　要：传统的分布式数据流挖掘模型是一种挖掘结果中逐层进行的层次模型,通信带宽是一个瓶颈。为了减少分布式数据流结点的通信,本文采用一种基于数据密度的偏倚抽样方法对分布式数据流组中的每个流进行抽样,只维护抽样数据中最近期的元素。在频繁项挖掘过程中,设计了一种哈希计数方法(不同于传统哈希计数算法),可以同时对数据的计数进行增加和删减,计数的值是有一定误差保证的近似值,算法称为FFIDDS算法。实验结果证明,通信负担和处理时间均明显比传统HCS模型的算法优秀。Traditional method of mining frequent elements in distributed data stream tends to result in excessively communication within layers , and bandwidth is bottleneck. To minimize communication requirements, we propose a method of sampling from distributed data stream basing on data density. We mine, frequent items in thisdata stream that are composed of sampled data. In the aggregated data stream, we only deal with the recent data. The proposed method counts the elements with hash-based approach and can handle both insertion and deletion of item counts. it is named FFIDDS algorithm. Through experiment the FFIDDS model is shown outperformed the HCS model in communicational load and processing time.

关 键 词：分布式数据流 频繁项 算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP311.13[自动化与计算机技术—计算机科学与技术]