基于TPU-tree的Skyline分支定界查询算法(英文)

Branch and Bound Processing of Skyline Queries Based on TPU-tree

提出了一种新的限定性skyline查询理念,并给出了高效的处理技术。分支定界方法是当前skyline查询处理效率较高的技术之一,在一种不确定移动对象的索引策略TPU-tree之上,基于分支定界方法提出了B2CPS可限定性skyline查询处理算法。实验结果表明,提出的基于TPU-tree的B2CPS算法可以很大程度地提高限定性skyline查询的效率,在移动对象频繁更新的情况下亦能保持较高的查询性能,因此具有较好的实用价值。

Based on the characteristics of uncertain moving objects, the concept of constrained probabilistic skyline query is introduced, and the efficient pruning approaches which can eliminate these unqualified skyline objects are proposed. A simple but powerful branch and bound searching algorithm B^2CPS is given for processing such queries by using a multidimensional indexing structure TPU-tree. First, use the B^2CPS algorithm to compute the initial skyline in uncertain moving data sets indexed by TPU-tree. Then, the dominance relationships between the updated objects are rechecked by B^2CPS, which provides an indicator of how to maintain the skyline results as objects moving. Theoretical analysis and extensive experiments demonstrate that the proposed algorithm can significantly enhance the query performance than the naive methods under various data distributions with different update frequencies