南京大学学报：自然科学版2012，Vol.48Issue(3)：351-359,9.
一种基于滑动窗口的不确定数据流Top-K查询算法
A Top-K queries algorithm for uncertain data streams based on sliding-window
摘要
Abstract
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查询/滑动窗口Key words
uncertain data/data streams/Top-K queries/sliding-window分类
信息技术与安全科学引用本文复制引用
汤克明,戴彩艳,陈岐..一种基于滑动窗口的不确定数据流Top-K查询算法[J].南京大学学报：自然科学版,2012,48(3):351-359,9.基金项目
基金项目：国家自然科学基金（61070047）,江苏省自然科学基金 （）
