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

• 作者: 戴彩艳 汤克明 陈岐
• 来源期刊: 南京大学学报：自然科学版
• 学科: 工学
• 关键词: 不确定数据 数据流 Top-K查询 滑动窗口
• 年，卷（期）: 2012,（3）
• 所属期刊栏目: 流体包裹体专栏
• 页码范围: 351-359
• 分类号: TP311.1
• 语种: 中文

摘要

由于不确定数据流在诸如移动计算、无线射频识别技术和传感器网络等实际应用中广泛存在,如何利用有限存储空间进行快速查询处理是不确定数据流管理的重要问题.本文研究基于滑动窗口模型的不确定数据流Top-K查询的问题,提出了相应的算法.该算法利用滑动窗口数据模型存储不确定流数据,建立3个概要表,当前窗口中的元组分别按照它们出现的顺序、它们的得分值的大小、它们的出现概率值的大小存入这3个表中.算法逐次在得分值最高的前若干个元组中选取概率值最高的前k项元组集合,并计算它们的发生概率.我们在理论上证明了,这些前k项元组集合中概率最高的就是Top-K查询结果.实验结果表明,所提出的查询算法在时间与空间复杂性方面优于其他类似的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	戴彩艳	南京航空航天大学计算机科学与技术学院	4	9	2.0	3.0
2	汤克明		1	7	1.0	1.0