n-of-N 数据流模型上高效概率Skyline 计算

研究概率数据流上的q-skyline计算问题.与只支持滑动窗口数据流模型的已有方法相比,所提出的方法能够支持更为通用的n-of-N数据流模型.采用将q-skyline查询转换为区间树上刺入查询的方法支持n-of-N数据流模型.提出PnNM算法维护支持n-of-N数据流模型所需的相关数据结构,高效处理了不确定对象候选集合更新和区间更新等维护工作；提出PnNCont算法实现连续查询处理.理论分析和实验结果表明,算法能够有效地支持概率数据流n-of-N模型上的q-skyline查询处理.

Efficient Probabilistic Skyline Computation Against n-of-N Data Stream Model

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.