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

Efficient Algorithm for Multiple Subspace Skyline Queries Processing

作　　者：王潇逸 秦小麟[1] 王宁[1] 史文浩[1] 

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京210016

出　　处：《计算机科学与探索》2016年第5期623-634,共12页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金Nos.61373015;61300052;41301047;江苏高校优势学科建设工程资助项目;南京航空航天大学研究生创新实验室开放基金No.kfjj20151607~~

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

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

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