面向不确定感知数据的频繁项查询算法  

Frequent Items Query Algorithm for Uncertain Sensing Data

作　　者：王爽[1,2] 王国仁[2] 

机构地区：[1]东北大学软件学院沈阳110819 [2]东北大学信息科学与工程学院沈阳110819

出　　处：《计算机学报》2013年第3期571-581,共11页Chinese Journal of Computers

基　　金：国家自然科学基金重点项目(60933001);国家杰出青年科学基金项目(61025007);国家自然科学基金青年科学基金项目(61100022)资助~~

摘　　要：随着计算机网络技术的快速发展,无线传感器网络产生了大量的感知数据流.同时,传感器自身的特点使得感知数据具有不确定的特征,因此需要对传感器网络中不确定感知数据流处理技术进行研究.在传感器网络中,频繁项查询在环境监控和关联规则挖掘等方面具有重要意义.文中首先提出了基本算法,用以连续维护传感器网络中的概率阈值频繁项查询结果.针对基本算法需要维护所有元素的问题,又提出了一种优化算法,算法在两方面进行了优化:(1)设计了一种通过预测元素概率上界的方法进行候选集的构造,仅维护必要信息从而提高查询效率;(2)设计了一种新的cp-list结构,可以压缩不同窗口候选集中的重复元素,降低存储开销.实验结果表明文中提出的算法可以减少连续维护传感器网络中频繁项查询的计算代价和存储空间.With advances in technology, large amounts of streaming data can be generated con tinuously by sensors. Due to the inherited limitation of sensors, these continuous sensing data can be uncertain. This calls for stream mining of uncertain sensing data. Frequent items query is valuable in wireless sensor networks （WSNs） and it can be widely used in environmental monito- ring, association rules mining, and so on. A basic algorithm which continuously maintains sliding window frequent items over WSNs is proposed. However the basic algorithm needs to maintain all items in the window. Due to this, an improved algorithm is further proposed by optimizing in two aspects： （1） the pruning rules by predicting the upper bound of items probability is devel- oped, which can reduce the candidate set and improve the query efficiency; （2） the large amount of the same items in different window can be compressed by cp-list structure in order to minimize

关 键 词：无线传感器网络 不确定数据流 频繁项 概率阈值 过滤 物联网 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]