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

黄伯虎; 张海宾; 逄涛; 聂鹏程

您当前的位置：

首页 >

文章列表页 >

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

信息工程 | 更新时间：2023-11-14

- 基于枢轴选择策略的多核并行skyline算法
- A Multi-core Parallel Skyline Algorithm Based on Pivot Selection
- 工程科学与技术 2011年43卷第1期页码：109-115
- 作者机构：
  
  西安电子科技大学
- 作者简介：
- 基金信息：
  
  国家重点基础研究发展计划973资助项目(2010CB328102);国家自然科学基金重大国际合作资助项目(60910004);国家自然科学基金资助项目(60873018)
- DOI：
  中图分类号：
- 纸质出版日期：2011，
  
  网络出版日期：2010-9-19，
扫描看全文
黄伯虎,张海宾,逄涛,聂鹏程.基于枢轴选择策略的多核并行skyline算法[J].工程科学与技术,2011,43(1):109-115.

Huang Bo-hu, 张海宾, 逄涛, et al. A Multi-core Parallel Skyline Algorithm Based on Pivot Selection[J]. Advanced Engineering Sciences, 2011,43(1):109-115.
黄伯虎,张海宾,逄涛,聂鹏程.基于枢轴选择策略的多核并行skyline算法[J].工程科学与技术,2011,43(1):109-115. DOI：

Huang Bo-hu, 张海宾, 逄涛, et al. A Multi-core Parallel Skyline Algorithm Based on Pivot Selection[J]. Advanced Engineering Sciences, 2011,43(1):109-115. DOI：

摘要

中文摘要: 针对当前大规模高维数据集skyline计算效率不高的问题，提出了一种多核并行算法MPSSI(Multi-core Parallel Skyline computation based on Sorting and Incomparability)。首先对数据集进行预排序处理，简化了后续计算过程；并通过精心选择枢轴点，将数据空间划分为若干区域，利用区域支配关系，减少了数据点之间的支配测试次数；同时在多核平台上对计算过程进行并行化处理，进一步提高了效率。MPSSI算法处理过程简洁、渐进性好、可扩展性强。实验结果表明，对大规模高维数据集，算法效率有大幅提升，相对加速比接近线性。

Abstract

Abstract:For 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)

is proposed. The given dataset is first pre-ordered to simplify the whole algorithm. Then the dataset space is divided into several disjoint regions via a carefully selected pivot point

and by the dominance relations among regions

the number of dominance testing is reduced. Finally

all functions in MPSSI have been paralleled on multi-core platform to improve efficiency. MPSSI is characterized by simple process

good progressiveness and nice scalability. The experiment results show that

on enormous and high-dimensional datasets

MPSSI can significantly improve efficiency and almost reach linear relative speedup.

关键词

skyline计算多核并行算法排序信息检索

Keywords

skyline computingmulti-coreparallel algorithmssortinginformation retrieval

references

Borzsonyi S;Kossmann D;Stocker K,The skyline operator,Heidelberg:IEEE,2001.

Chomicki J;Godfrey P;Gryz J,Skyline with presorting,Bangalore:IEEE,2003.

朱琳;关估红;周水庚.Skyline计算研究综述[J].计算机工程与应用,2008(6)doi:10.3778/j.issn.1002-8331.2008.06.049

Rabhi F A;Gorlatch S,Patterns and skeletons for parallel and distributed computing,Beilin:Springer-Verlag,2003.

Park S;Kim T;Park J,Parallel skyline computation on multicore architectures,上海:IEEE,2009.

Lee J;Hwang S-W,BSkytree:Scalable skyline computation using a balanced pivot selection,Lausanne:ACM,2010.

Papadias,D;Tao,Y.F;Fu,G;Seeger,B,Progressive skyline computation in database systems,ACM Transactions on Database Systems

Kossmann D;Ramsak F;Rost S,Shooting stars in the sky:an online algorithm for skyline queries,Hong Kong:Morgan Kaufmann,2002.

Dagum, L. ；Menon, R.,OpenMP: an industry standard API for shared-memory programming,IEEE computational science & engineering

Jones S P,Haskell 98 language and libraries:The revised report,New York:cambridge University Press,2003.

Lee K C K;Zheng Baihua;Li Huajing,Approaching the skyline in Z order,Vienna:ACM,2007.

更多指标>

浏览量

下载量

CNKI被引量

文章被引用时，请邮件提醒。

提交

工具集

关联资源

航班延迟推出策略及虚拟队列长度灵敏度分析