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