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

Skyline查询处理是近年来信息管理和数据库交叉学科的一个研究重点和热点, 其广泛应用于多标准决策支持系统、城市导航系统、数据挖掘和可视化以及信息推荐系统等领域. 然而, 在实际的联机查询应用中, skyline查询的结果具有固定和多用户共享特性, 因此, 随着时间的推进, 查询结果的可选择性逐步降低, 从而最终导致查询结果无法满足用户的需求. 为此, 提出k-quasi skyline查询, 来丰富传统skyline查询的结果集, 并与目前主流关系数据库产品无缝集成.为了提高任意维空间上k-quasi skyline查询的效率, 设计了基于正规格索引的计算方法EARG (efficient algorithm based on regular grid).EARG算法通过格之间的支配关系来缩减对象间的比较次数, 从而显著降低k-quasi skyline计算的时间开销.理论分析和实验结果表明, EARG算法具有有效性和实用性.

Efficient processing of κ-quasi skyline query

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.