Skyline查询应用扩展及其优化算法  

Efficient processing of κ-quasi skyline query

作　　者：林正奎[1] 黄震华[2] 向阳[2] 

机构地区：[1]大连海事大学信息科学技术学院,大连116026 [2]同济大学电子与信息工程学院,上海201804

出　　处：《系统工程理论与实践》2012年第5期1098-1106,共9页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(60903032,70771077);国家863计划(2008AA04Z106);教育部博士点专项基金(20090072120056);上海市信息委专项基金(200801015);辽宁省自然科学基金(20092145)

摘　　要：Skyline查询处理是近年来信息管理和数据库交叉学科的一个研究重点和热点,其广泛应用于多标准决策支持系统、城市导航系统、数据挖掘和可视化以及信息推荐系统等领域,然而,在实际的联机查询应用中,skyline查询的结果具有固定和多用户共享特性,因此,随着时间的推进,查询结果的可选择性逐步降低,从而最终导致查询结果无法满足用户的需求.为此,提出k一quasi skyline查询,来丰富传统skyline查询的结果集,并与目前主流关系数据库产品无缝集成.为了提高任意维空间上k-quasi skyline查询的效率.设计了基于正规格索引的计算方法EARG(efficient algorithmbased on regular grid).EARG算法通过格之间的支配关系来缩减对象间的比较次数,从而显著降低k-quasi skyline计算的时间开销.理论分析和实验结果表明,EARG算法具有有效性和实用性.Skyline query processing has recently received a lot of attention in information management and database communities.Its result is widely applied in many applications,such as multi-criteria decision making,data mining and visualization,and information recommender systems.In most online query applications,however,the skyline result is changeless and shared by multiple users,and hence the skyline set can not efficiently satisfy the needs of users.Motivated by this fact,we propose a new kind of query,kquasi skyline query,to enrich the traditional skyline set and strengthen the SQL query engine of RDBMSs. In order to improve the efficiency of arbitrary subspace k-quasi skyline query,an effective algorithm EARG （cell-dominance computation algorithm） which utilizes the regular grid index is proposed.The EARG algorithm reduce the number of comparisons between objects by pruning all the cells which are dominated by any other ones,and hence can dramatically decrease the computation cost of k-quasi skyline query. Furthermore,we present detailed theoretical analyses and extensive experiments that demonstrate our proposed algorithm is both efficient and effective.

关 键 词：决策支持 k-quasi SKYLINE查询 正规格索引 性能优化 

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