基于网格索引的数据流子空间概率轮廓查询

摘要

在数据流子空间上的连续概率轮廓查询(CPSQS)基础上,提出一种基于网格索引结构的概率轮廓查询算法.采用适合于子空间轮廓计算的网格索引结构,将数据空间划分成若干个格,利用格间的支配关系,减少对象之间的比较次数.同时挖掘全空间与子空间上格的概率上下界关系,设计有效的剪枝策略提高CPSQS算法的性能.理论分析和实验结果表明,该算法能满足实际应用中用户的个性化查询要求,降低查询响应时间.%This paper proposes Continuous Probabilistic Skyline Query in Subspaces(CPSQS) over sliding window on uncertain data streams. Moreover, a novel algorithm using a regular grid index, which is adaptable for solving subspace skyline issue, is presented to reduce the dominating testing costs. At the same time, based on the subtle relationship between the probabilistic bounds of full space and an arbitrary subspace, a set of pruning strategies are developed to improve the performance of CPSQS. Analytical analysis and experimental results show that this algorithm can meet individuation query of users, reduce query response time.