基于枢轴选择策略的多核并行skyline算法  

A Multi-core Parallel Skyline Algorithm Based on Pivot Selection

作　　者：黄伯虎[1,2] 张海宾[1] 逄涛[1] 聂鹏程[1] 

机构地区：[1]西安电子科技大学计算理论与技术研究所,陕西西安710071 [2]西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安710071

出　　处：《四川大学学报（工程科学版）》2011年第1期109-115,共7页Journal of Sichuan University (Engineering Science Edition)

基　　金：国家重点基础研究发展计划资助项目(2010CB328102);国家自然科学基金重大国际合作资助项目(60910004);国家自然科学基金资助项目(60873018);陕西省科技攻关计划资助项目(2009K01-36);中央高校基本科研业务费专项资金资助项目(JY10000903004JY10000903014)

摘　　要：针对当前大规模高维数据集skyline计算效率较低的问题,提出了一种多核并行算法MPSSI(Multi-core Par-allel Skyline computation based on Sorting and Incomparability)。首先对数据集进行预排序处理,简化了后续计算过程;并通过精心选择枢轴点,将数据空间划分为若干区域,利用区域支配关系,减少了数据点之间的支配测试次数;同时在多核平台上对计算过程进行并行化处理,进一步提高了效率。MPSSI算法处理过程简洁、渐进性好、可扩展性强。实验结果表明,对大规模高维数据集,算法效率有大幅提升,相对加速比接近线性。Aiming at the low efficiency of skyline computation on enormous and high-dimensional datasets,a new multi-core parallel skyline algorithm,named MPSSI（Multi-core Parallel Skyline computation based on Sorting and Incomparability）,was proposed.To simplify the computational process,the given dataset was pre-ordered.Then the dataset space was divided into several disjoint regions via a carefully selected pivot point.By the dominance relations among regions,the number of dominance testing was reduced.Finally,all functions in MPSSI were paralleled on multi-core platform to improve efficiency.MPSSI was characterized by simple process,good progressiveness and nice scalability.Experiment results showed that on enormous and high-dimensional datasets,MPSSI can improve the efficiency of skyline computation and achieve good relative speedup.

关 键 词：SKYLINE计算 多核 并行算法 排序 信息检索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]