Spark平台下的凸包问题研究

• 作者: 李力 李格非 马蔚吟
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: Spark平台 分布式计算 空间几何查询 凸包运算
• 年，卷（期）: 2018,（22）
• 所属期刊栏目: 大数据与云计算
• 页码范围: 67-73,112
• 页数: 8页
• 分类号: TP311.133.1
• 字数: 7144字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1708-0293

摘要

随着移动互联网时代的到来,越来越多的含地理位置信息的空间数据需要处理,如何在海量的空间数据中进行常见的几何查询成为一个挑战,凸包问题因其在模式识别、图像处理、统计学、地理信息系统、博弈论、图论等领域中被广泛应用成为近些年研究的一个热点.凸包问题的研究始于单机版的算法,进而过渡到Hadoop等基于硬盘的分布式系统,但是受限于单节点的计算存储能力的瓶颈以及Hadoop平台基于硬盘的特性,其计算性能尚不能达到人们的在线实时计算的需求.研究基于内存的分布式计算框架Spark下的凸包问题,给出基于Spark平台的凸包查询整体框架,框架从查询接口、语法解析和物理执行等多方面结合SparkSQL引擎.随后,给出基于Andrew单调链算法的单机算法CHStand,分析单机算法并行度上的问题后,提出基于Spark的CHSpark算法,进一步优化算法并提出一种Spark平台下的优化算法CHGeom.通过实验对比说明三种算法的相对性能提升,实验发现Spark平台下的解决方案相对传统的单机平台下的解决方案有着较大的性能提升,所提算法具有良好的拓展性和广泛的实际应用价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马蔚吟	南京医科大学基础医学院	10	24	2.0	4.0
2	李力	上海交通大学软件学院	14	111	5.0	10.0
3	李格非	上海交通大学计算机科学与工程系	2	8	2.0	2.0