Journal of Frontiers of Computer Science and Technology ›› 2009, Vol. 3 ›› Issue (2): 162-172.DOI: 10.3778/j.issn.1673-9418.2009.02.005

• 学术研究 • Previous Articles     Next Articles

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

DING Xiaofeng+, LU Yansheng, ZHAO Na   

  1. Department of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-03-15 Published:2009-03-15
  • Contact: DING Xiaofeng

基于TPU-tree的Skyline分支定界查询算法

丁晓锋+,卢炎生,赵 娜   

  1. 华中科技大学 计算机科学与技术学院,武汉 430074
  • 通讯作者: 丁晓锋

Abstract: 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.

Key words: skyline query, probabilistic query processing, uncertain moving objects, TPU-tree

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

关键词: 轮廓查询, 概率查询处理, 不确定移动对象, TPU树