关键词: Spark平台, 分布式计算, 空间几何查询, 凸包运算

Abstract: With the arrival of mobile Internet era, more and more spatial data need to be stored and processed. How to conduct spatial geometrical queries on massive spatial data becomes a challenge in recent years. The convex hull problem becomes a focus for research on its wide usage in visual pattern matching, image processing, statistics, geographic information system, game theory and graph theory fields. The solution for convex hull problem starts with algorithms running on single computer, and then comes to some disk-based distributed systems, such as Hadoop. But bottlenecked by the storage and computing ability for single computer, the frameworks can not satisfy the demand for data scientists. This paper introduces an in-memory cluster computing framework Apache Spark to solve convex hull problem, the framework optimizes SparkSQL for geometrical operation from query interface, syntax parsing and physical execution. Firstly, a standalone algorithm CHStand on single computer is brought up to solve this problem, which is a na?ve solution on Spark named CHSpark. Then an optimized CHGeom algorithm is come up to solve the convex hull problem. Additional experiments show that CHGeom runs much faster than algorithms on single computer. Some ideas mentioned in this paper can be easily extended to other spatial geometrical operation.

Key words: Spark platform, distributed computing, spatial geometrical query, convex hull operation