一种ρ-支配轮廓查询的高效处理算法  

An Efficient Processing Algorithm for ρ-Dominant Skyline Query

作　　者：信俊昌[1] 白梅[1] 东韩[2] 王国仁[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110819 [2]国家海洋信息中心,天津300171

出　　处：《计算机学报》2011年第10期1876-1884,共9页Chinese Journal of Computers

基　　金：国家自然科学基金重点项目(60933001);国家自然科学基金面上项目(61073063);国家杰出青年科学基金项目(61025007);中央高校基本科研业务费专项资金(N090304007)资助~~

摘　　要：近年来,作为重要的多目标决策手段的轮廓查询逐渐得到学术界的重视,相继提出了基于不同支配关系的多种轮廓变体查询.首先,通过对实际应用需求进行分析,提出了基于元组对应数值间比例值大小的ρ-支配关系的定义,进而提出了ρ-支配轮廓查询的概念.其次,对ρ-支配轮廓的基本性质进行了细致而深入的分析,在此基础上,提出了基于分支定界的ρ-支配轮廓查询算法(Branch and Boundρ-Dominant Skyline Algorithm,BBDS),避免了对R-树索引的多次访问,从而提高了ρ-支配轮廓查询的执行效率.最后,通过大量的仿真实验对ρ-支配轮廓查询的语义进行分析,并对BBDS算法的性能进行验证.实验结果表明,ρ-支配轮廓查询是轮廓查询语义的扩展和补充,而提出的BBDS算法则是求解ρ-支配轮廓查询的高效算法.In recent years,as an important operator for multi-decision making,skyline query has attracted much attention from the academia gradually,and a variety of skyline variants based on different dominance relationships have been proposed successively by the database researchers.In this paper,firstly,through making the analysis of practical applications＇ requirements,the ρ-dominance relationship based on the ratio of corresponding values between the tuples is defined,and then the concept of ρ-dominant skyline query based on the ρ-dominance relationship is proposed.Next,by making a detailed and in-depth analysis of ρ-dominance＇s basic properties,a novel algorithm,named Branch and Bound ρ-Dominant Skyline Algorithm（BBDS）,is developed.The BBDS algorithm avoids visiting R-tree index too many times,which can improve the ρ-dominant skyline query implementation efficiency greatly.Finally,through a large number of simulation experiments,the semantic of the ρ-dominant skyline query is analyzed,and meanwhile the performance of BBDS algorithm is verified by the simulation experiments.The simulation experimental results show that ρ-dominant skyline query based on ρ-dominance relationship is a new extension and complement of the traditional skyline query semantic and the BBDS algorithm proposed in this paper is proved to be a highly effective algorithm for solving ρ-dominant skyline queries.

关 键 词：轮廓查询 轮廓变体 ρ-支配关系 ρ-支配轮廓 分支定界 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]