首页 | 本学科首页   官方微博 | 高级检索  
     

n-of-N 数据流模型上高效概率Skyline 计算
引用本文:杨永滔,王意洁. n-of-N 数据流模型上高效概率Skyline 计算[J]. 软件学报, 2012, 23(3): 550-564
作者姓名:杨永滔  王意洁
作者单位:国防科学技术大学计算机学院并行与分布处理国家重点实验室,湖南长沙,410073
基金项目:国家自然科学基金(60873215);国家重点基础研究发展计划(973)(2011CB302601);湖南省自然科学杰出青年基金(S2010J5050);高等学校博士学科点专项科研基金(200899980003)
摘    要:研究概率数据流上的q-skyline计算问题.与只支持滑动窗口数据流模型的已有方法相比,所提出的方法能够支持更为通用的n-of-N数据流模型.采用将q-skyline查询转换为区间树上刺入查询的方法支持n-of-N数据流模型.提出PnNM算法维护支持n-of-N数据流模型所需的相关数据结构,高效处理了不确定对象候选集合更新和区间更新等维护工作;提出PnNCont算法实现连续查询处理.理论分析和实验结果表明,算法能够有效地支持概率数据流n-of-N模型上的q-skyline查询处理.

关 键 词:概率数据流  skyline  n-of-N模型  滑动窗口  连续查询
收稿时间:2010-02-10
修稿时间:2010-08-13

Efficient Probabilistic Skyline Computation Against n-of-N Data Stream Model
YANG Yong-Tao and WANG Yi-Jie. Efficient Probabilistic Skyline Computation Against n-of-N Data Stream Model[J]. Journal of Software, 2012, 23(3): 550-564
Authors:YANG Yong-Tao and WANG Yi-Jie
Affiliation:(National Key Laboratory for Parallel and Distributed Processing,College of Computer,National University of Defense Technology,Changsha 410073,China)
Abstract:This paper studies the problem of computing q-skylines against probabilistic data streams.Compared with the existing methods,which only support the sliding window model,this method can support the more general n-of-N data stream model.This method of transforming q-skyline queries is used for the stabbing queries on an interval tree to support n-of-N model.The paper proposes an algorithm,named PnNM,to maintain the data structures,which is needed for supporting n-of-N model.The PnNM algorithm can efficiently handle the update of the candidate set of uncertain data objects and the updates of the intervals.An algorithm,named PnNCont,is also proposed to handle continuous q-skyline queries against n-of-N model.The theoretical analyses and extensive experiments demonstrate that this algorithms can be very efficient in handing q-skyline queries against probabilistic data streams under n-of-N model.
Keywords:probabilistic data stream  skyline  n-of-N model  sliding window  continuous query
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号