Journal of Frontiers of Computer Science and Technology ›› 2016, Vol. 10 ›› Issue (5): 623-634.DOI: 10.3778/j.issn.1673-9418.1507077

Previous Articles     Next Articles

Efficient Algorithm for Multiple Subspace Skyline Queries Processing

WANG Xiaoyi+, QIN Xiaolin, WANG Ning, SHI Wenhao   

  1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
  • Online:2016-05-01 Published:2016-05-04

高效多子空间Skyline查询处理算法

王潇逸+,秦小麟,王  宁,史文浩   

  1. 南京航空航天大学 计算机科学与技术学院,南京 210016

Abstract: As Skyline queries are widely used, subspace Skyline query processing has attracted lots of attention. Aiming at meeting the need that users want to evaluate a dataset from multiple perspectives, this paper makes a full study of multiple subspace Skyline queries. Motivated by the deficiency of existing algorithms, this paper proposes the structure of subspace skycube group, and puts forward an efficient method called MSSC (multiple subspace skycube) based on that structure. The MSSC algorithm can efficiently process any number of subspace Skyline queries simultaneously. Firstly, the MSSC algorithm uses subspace candidate sets to share the results of different subspace Skyline queries in the subspace Skycube group. Then it adopts sum filter and max-value filter to cut and filter data, which further improves the performance of the MSSC algorithm. At last, the experiments conducted on both synthetic data sets and a real-life data set demonstrate that the MSSC algorithm can solve the multiple subspace Skyline queries problem efficiently.

Key words: multiple subspace Skyline queries, subspace list, subspace skycube group, subspace candidate set

摘要: 随着Skyline查询应用的增多,子空间Skyline查询成为热点。针对实际应用中用户从多角度审视某一数据集的需求,充分研究了多子空间Skyline查询问题。在分析现有子空间Skyline查询算法解决该问题不足的基础上,提出了子空间立方体群(subspace skycube group,SSG)结构,并给出了基于该结构的同时计算任意多个子空间Skyline查询的MSSC(multiple subspace skycube)算法。该算法采用子空间候选集(subspace candidate sets,SCS),并充分利用了子空间立方体群结构中各子空间Skyline结果间的共享关系;在此基础上,算法采用求和过滤以及最大值过滤等方法,对数据集进行剪枝和过滤,从而进一步提高算法效率。最后,分别用人造数据和真实数据对算法进行实验,并与现有算法进行比较,结果表明MSSC算法可以高效地解决多子空间Skyline查询问题。

关键词: 多子空间Skyline查询, 子空间序列, 子空间立方体群, 子空间候选集