Branch and Bound Processing of Skyline Queries Based on TPU-tree
Na Zhao · Jisuanji kexue yu tansuo · 2009
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 B2CPS is given for processing such queries by using a multidimensional indexing structure TPU-tree.First,use the B2CPS 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 B2CPS,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.