一种基于滑动窗口的不确定数据流Top-K查询算法  

A Top-K queries algorithm for uncertain data streams based on sliding-window

作　　者：汤克明[1,2] 戴彩艳[1] 陈崚[3,4] 

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京210016 [2]盐城师范学院信息科学与技术学院,盐城224002 [3]扬州大学计算机科学系,扬州225009 [4]南京大学计算机软件新技术国家重点实验室,南京210093

出　　处：《南京大学学报（自然科学版）》2012年第3期351-359,共9页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金(61070047);江苏省自然科学基金(BK2008206)

摘　　要：由于不确定数据流在诸如移动计算、无线射频识别技术和传感器网络等实际应用中广泛存在,如何利用有限存储空间进行快速查询处理是不确定数据流管理的重要问题.本文研究基于滑动窗口模型的不确定数据流Top-K查询的问题,提出了相应的算法.该算法利用滑动窗口数据模型存储不确定流数据,建立3个概要表,当前窗口中的元组分别按照它们出现的顺序、它们的得分值的大小、它们的出现概率值的大小存入这3个表中.算法逐次在得分值最高的前若干个元组中选取概率值最高的前k项元组集合,并计算它们的发生概率.我们在理论上证明了,这些前k项元组集合中概率最高的就是Top-K查询结果.实验结果表明,所提出的查询算法在时间与空间复杂性方面优于其他类似的算法.Due to the existence of uncertain data streams in wide spectrum of real-world applications,such as mobile computing, radio frequency identification technology and wireless sensor networks, uncertain data streams management has become an important problem in stream data mining. This paper tackles the problem of answering maximal probabilistic Top-K tuple set （MPTopKTS） queries on uncertain data streams based on a sliding-window model. We present an algorithm for processing sliding-window MPTopKTS queries on uncertain data streams. Based on the sliding-window model,we designed three synopses table to process each tuple which contains data item 3c, score item f（x） ,and existential probability p（x）. The tuples are stored in the tables according to their arrival times, their scores, and their probabilities respectively. The algorithm selects the k tuples with the highest probabilities from the sets of different numbers of the tuples with the highest scores. After that, the algorithm computes existential probability of the Top-K tulpes,and chooses the one with the highest probability as the answer of MPTopKTS. We theoretically proved the correctnesss of the algorithm presented. Our experimental results show that our algorithm requires lower time and space complexity than other similar algorithms.

关 键 词：不确定数据 数据流 TOP-K查询 滑动窗口 

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