一种最优的相互skyline查询算法  

Optimal algorithm for mutual skyline queries

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

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

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

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

摘　　要：提出了一种最优的相互skyline搜索算法OMS,它的主要思想是R-tree搜索堆重用技术、窗口查询堆重用技术和高效的修剪策略.OMS与相互skyline算法RIBBS相比,它表现出更高的性能和效率.这是因为OMS消除了多次的动态skyline计算且挽救了更多的I/O成本.理论分析证明OMS计算相互skyline是最优的.在真实数据集上的大量实验结果表明,OMS算法是有效的且保持了较高的效率.An optimal algorithm of mutual skyline search, called optimal mutual skyline （OMS）, is introduced, which is based on the reuse technology and some efficient pruning policies. Compared with reuse information for branch and bound skyline （RIBBS） algorithm proposed firstly, OMS provides higher performance and efficiency because OMS eliminates the computation of multiple dynamic sky- lines and saves more I/O cost. The analysis of theory proves that OMS is optimal algorithm of mutual skyline. The results of extensive experiments conducted on several real datasets show that OMS algorithm is effective and has highest efficiency, varying the dimension and the cardinality of different datasets.

关 键 词：算法 查询处理 搜索 动态skyline 可逆skyline 相互skyline 

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