| 摘要: |
| 研究概率数据流上的q-skyline 计算问题.与只支持滑动窗口数据流模型的已有方法相比,所提出的方法能够支持更为通用的n-of-N 数据流模型.采用将q-skyline 查询转换为区间树上刺入查询的方法支持n-of-N 数据流模型.提出PnNM 算法维护支持n-of-N 数据流模型所需的相关数据结构,高效处理了不确定对象候选集合更新和区间更新等维护工作;提出PnNCont 算法实现连续查询处理.理论分析和实验结果表明,算法能够有效地支持概率数据流n-of-N 模型上的q-skyline 查询处理. |
| 关键词: 概率数据流 skyline n-of-N 模型 滑动窗口 连续查询 |
| DOI：10.3724/SP.J.1001.2012.04050 |
| 分类号: |
| 基金项目:国家自然科学基金(60873215); 国家重点基础研究发展计划(973)(2011CB302601); 湖南省自然科学杰出青年基金 (S2010J5050); 高等学校博士学科点专项科研基金(200899980003) |
|
| 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
|
| 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. |
| Key words: probabilistic data stream skyline n-of-N model sliding window continuous query |
