Journal of Software:2012.23(3):550-564

n-of-N 数据流模型上高效概率Skyline 计算
(国防科学技术大学 计算机学院 并行与分布处理国家重点实验室,湖南 长沙 410073)
Efficient Probabilistic Skyline Computation Against n-of-N Data Stream Model
YANG Yong-Tao,WANG Yi-Jie
(National Key Laboratory for Parallel and Distributed Processing, College of Computer, National University of Defense Technology, Changsha 410073, China)
Chart / table
Similar Articles
Article :Browse 2691   Download 2792
Received:February 10, 2010    Revised:August 13, 2010
> 中文摘要: 研究概率数据流上的q-skyline 计算问题.与只支持滑动窗口数据流模型的已有方法相比,所提出的方法能够支持更为通用的n-of-N 数据流模型.采用将q-skyline 查询转换为区间树上刺入查询的方法支持n-of-N 数据流模型.提出PnNM 算法维护支持n-of-N 数据流模型所需的相关数据结构,高效处理了不确定对象候选集合更新和区间更新等维护工作;提出PnNCont 算法实现连续查询处理.理论分析和实验结果表明,算法能够有效地支持概率数据流n-of-N 模型上的q-skyline 查询处理.
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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(60873215); 国家重点基础研究发展计划(973)(2011CB302601); 湖南省自然科学杰出青年基金 (S2010J5050); 高等学校博士学科点专项科研基金(200899980003) 国家自然科学基金(60873215); 国家重点基础研究发展计划(973)(2011CB302601); 湖南省自然科学杰出青年基金 (S2010J5050); 高等学校博士学科点专项科研基金(200899980003)
Foundation items:
Reference text:

杨永滔,王意洁.n-of-N 数据流模型上高效概率Skyline 计算.软件学报,2012,23(3):550-564

YANG Yong-Tao,WANG Yi-Jie.Efficient Probabilistic Skyline Computation Against n-of-N Data Stream Model.Journal of Software,2012,23(3):550-564