基于重用技术的相互Skyline查询算法  

Reusing technology-based mutual Skyline query algorithm

作　　者：张彬[1] 蒋涛[2,3] 乐光学[3] 李国徽[2] 

机构地区：[1]衡阳师范学院计算机科学系,湖南衡阳421008 [2]华中科技大学计算机科学与技术学院,湖北武汉430074 [3]嘉兴学院数学与信息工程学院,浙江嘉兴314000

出　　处：《华中科技大学学报（自然科学版）》2010年第7期111-114,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家高技术研究发展计划资助项目(2007AA01Z309);湖南省教育厅科研资助项目(09C176)

摘　　要：提出了一种新的Skyline查询,即相互Skyline查询(MSQ).给定一个对象集合P和一个查询对象q,MSQ返回一个对象集合,它的每个对象既在q的动态Skyline中,同时也在q的可逆Skyline中.基于传统的R-tree索引、重用堆信息技术以及启发式的修剪策略,显著降低了I/O成本,改进了基于BBS算法和BBRS算法实现的MSQ算法.几个真实数据集的实验表明提出的算法有效而高效,比一般MSQ算法快几个数量级.A novel Skyline query,namely,mutual Skyline query （MSQ） was proposed. Given a set of objects P and a query object q,a MSQ returns from P,the set of objects that were among the dynamic Skyline of q; meanwhile,among the reverse Skyline of q. Although MSQ has played an important role in many applications,such as multi-criteria decision making,market analysis,and task allocation,it cannot be efficiently computed by existing Skyline query algorithms. The first piece of work for tackling MSQ efficiently was presented. A conventional data-partitioning index （e.g.,R-tree,etc） on the data sets was used in this approach; the state-of-the-art Skyline query techniques including BBS （branch and bound Skyline） and BBRS （branch and bound reverse Skyline） algorithm were employed,the reuse heap technique and heuristic search policy were used so as to deduce the I/O cost. An extensive empirical study demonstrates the efficiency and effectiveness of our proposed algorithm. It outperforms the simple algorithm usually by orders of magnitude under all problem instances.

关 键 词：查询算法 重用技术 动态Skyline查询 可逆Skyline查询 相互Skyline查询 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]