Spark平臺下的凸包問題研究

李格非，馬蔚吟，李 力

1.上海交通大學 計算機科學與工程系，上海 200240

2.南京醫(yī)科大學 基礎醫(yī)學院，南京 211166

3.上海交通大學 軟件學院，上海 200240

1 概述

空間數(shù)據(jù)無處不在。在過去的十年里，隨著移動互聯(lián)網(wǎng)的發(fā)展，從移動設備、衛(wèi)星等設備獲取到的空間數(shù)據(jù)數(shù)量呈現(xiàn)出爆炸性增長的趨勢。凸包問題是空間數(shù)據(jù)處理中的一個重要問題，在模式識別、圖像處理等多個領域中有重要應用。當數(shù)據(jù)量從GB數(shù)量級增加到TB，甚至PB數(shù)量級時，如何高效率地在這些數(shù)據(jù)上進行凸包查詢成為一個挑戰(zhàn)。最開始時，人們使用單臺計算機進行空間數(shù)據(jù)的凸包查詢，隨著空間數(shù)據(jù)的數(shù)據(jù)量越來越大，單臺計算機的計算和存儲能力逐漸成為瓶頸。于是分布式計算的概念發(fā)展起來，用來解決單臺計算機計算能力的瓶頸問題。Hadoop[1]是一個廣為使用的分布式計算框架，有許多基于Hadoop的系統(tǒng)，如CG_Hadoop[2]等，被提出解決凸包查詢問題。但是Hadoop基于硬盤數(shù)據(jù)讀取的計算，使其適用于離線的分析任務，針對一些實時的查詢分析，應用Hadoop在吞吐量和響應時間上的要求遠不能達到數(shù)據(jù)分析學者的要求。

Apache Spark[3]（后文簡稱Spark）是一個常見的用來實現(xiàn)高吞吐低延時查詢的框架，其基于內(nèi)存計算的特性，使得Spark在性能上超過Hadoop多個數(shù)量級。Spark使用彈性分布式數(shù)據(jù)集（Resilient Distributed Dataset，RDD[3]）實現(xiàn)基于內(nèi)存的數(shù)據(jù)存儲和計算，使用譜系圖（Lineage Graph）[4]保持框架計算的容錯性。現(xiàn)有的一些基于Spark的空間幾何計算引擎[5-7]使用RDD API調用Spark的計算引擎，為用戶提供計算接口完成凸包查詢。

這些引擎遠遠不能滿足數(shù)據(jù)分析學者的分析需求。首先，這些系統(tǒng)的接口對用戶不友好，用戶需要花很多時間來學習理解，甚至閱讀源代碼才能正確地使用這些系統(tǒng)。其次，這些系統(tǒng)沒有形成一個整體，不支持多層嵌套查詢，即某一次分析的結果作為下一次分析操作的輸入數(shù)據(jù)。深層次來說，這些系統(tǒng)將Spark視為一個黑盒，忽略其自身的分區(qū)、容錯等特性，由此設計出的系統(tǒng)，接口友好性和計算性能遠不能滿足用戶需求。

本文在框架下拓展SparkSQL的查詢引擎，給出平面點集的凸包解決方案。為了提供一個對用戶友好的查詢接口，從多個層次上拓展SparkSQL引擎。本文有如下貢獻：

（l）提供一個完整的空間數(shù)據(jù)查詢系統(tǒng)，從空間數(shù)據(jù)導入存儲，到空間數(shù)據(jù)的凸包計算，到計算結果的進一步關系型數(shù)據(jù)的分析，用戶可以十分便捷地利用系統(tǒng)完成需求。

（2）針對空間上點集的凸包問題，實現(xiàn)多種平臺下的不同算法，最終得到一個高效率的Spark平臺解決方案。

（3）拓展常見的SQL語句和SparkSQL的DataFrame API，用戶可以通過簡單的SQL語句或者SparkSQL系統(tǒng)無縫地完成數(shù)據(jù)導入和數(shù)據(jù)計算操作。

本文提到的算法和Spark的重要組件SparkSQL深度集成，并沒有直接對Spark內(nèi)核進行修改，因此可以較為便捷地遷移到新版本的Spark系統(tǒng)。本文充分利用SparkSQL的各種高級特性來保證數(shù)據(jù)計算效率以及系統(tǒng)容錯性等，也針對常見的數(shù)據(jù)完成一些對比實驗，驗證本文算法優(yōu)于一些單機條件和其他系統(tǒng)上的算法效率。

2 背景知識

本章主要介紹已有的凸包算法和Spark平臺相關的基礎背景。

2.1 凸包

對于二維空間中的點集X，所有包含X的凸集的交集S被稱為X的凸包。X的凸包可以用X內(nèi)所有點(x1,x2,…,xn)的線性組合來構造：

二維空間中，凸包可以想象為一條剛好包圍所有點的橡皮圈，如圖1所示。

圖1 凸包

凸包問題在模式識別、圖像處理、統(tǒng)計學、地理信息系統(tǒng)、博弈論、圖論等領域中被廣泛使用。計算幾何學中的一個典型應用是最遠點對問題的求解，因為點集的最遠點對一定在凸包上，由這一性質可以利用凸包算法和Rotating Caliper[8]算法解決最遠點對問題。

2.2 Spark與Spark SQL

Spark是伯克利AMPLab在2011年提出的開源類Hadoop的MapReduce框架的通用并行計算模型，擁有MapReduce所具有的所有優(yōu)點，同時改進Hadoop的MapReduce任務中shuffle數(shù)據(jù)中間結果策略，從HDFS的硬盤讀寫轉成為內(nèi)存讀寫，達到計算性能上的提升。Spark使用RDD的數(shù)據(jù)集合抽象，用來存儲和計算數(shù)據(jù)。RDD是一種高度抽象的內(nèi)存數(shù)據(jù)分布式數(shù)據(jù)集合，用戶可以在忽略RDD的實現(xiàn)細節(jié)的情況下，充分利用集群內(nèi)存。Spark在RDD層次上完成需要集群并行級別的優(yōu)化，對RDD的基礎操作，如map、filter等，通過集群計算的特性，實時分發(fā)任務到所有節(jié)點，保證計算的并行性，并對RDD之間的轉換操作（transformation）采用惰性求值處理進行優(yōu)化，每次遇到一個需要將RDD轉換成其他對象的行動操作（action），如內(nèi)存中的整型數(shù)、數(shù)組，或者磁盤上的文件，才會并行地優(yōu)化執(zhí)行現(xiàn)有的轉換操作，生成一個運算結果。RDD通過譜系圖的方式保證數(shù)據(jù)的容錯性，每次進行轉換操作或者行動操作時，驅動程序的內(nèi)存中維護一個有向無環(huán)的RDD轉換圖，在集群中某一節(jié)點宕機之后，可以根據(jù)這個有向無環(huán)圖重新生成缺失的分區(qū)，達到恢復丟失數(shù)據(jù)的目的。

SparkSQL是Spark開發(fā)組的成員針對關系型數(shù)據(jù)開發(fā)的一套庫軟件，其前身是支持Hadoop的關系型數(shù)據(jù)庫引擎Shark。SparkSQL的整體架構圖如圖2中藍色部分所示，主要由API調用、語法解析、物理映射等部分組成。SparkSQL在數(shù)據(jù)存儲上采用列存的方式優(yōu)化數(shù)據(jù)存儲，采用Catalyst引擎完成SQL語句的解析和用戶調用的解析，完成SQL語句到抽象語法樹，到邏輯計劃的維護、優(yōu)化過程。優(yōu)化之后的邏輯計劃根據(jù)其執(zhí)行特點，進一步映射到Spark的物理計劃，使用Spark作為底層執(zhí)行引擎完成SQL語句的執(zhí)行。

2.3 凸包計算的研究

現(xiàn)有一些凸包計算方法以單機環(huán)境下的計算為主，主要有Jarvis步進法[9]、Graham 掃描法[10]、快包算法[11]、Andrew單調鏈算法[12]等，文獻[8，13]對這些算法進行了總結。總體來說，這些算法[8-12，14]的缺點在于單節(jié)點的存儲和計算能力十分有限。近期也有基于Hadoop的CG_Hadoop等算法平臺的研究，其運行性能遠不能達到數(shù)據(jù)實時分析的需求。

3 整體結構

本文提出一種用戶友好的空間查詢框架，與Spark-SQL層耦合，提供SQL語句和DataFrame API兩個層次對凸包查詢的支持，整體SparkSQL的框架如圖2中橙色部分所示。首先，平臺在已有的SparkSQL的SQL語句上拓展凸包相關的關鍵字和DataFrame的用戶編程接口，在用戶查詢層支持凸包查詢。然后，在SQL解析器層次支持空間關鍵字節(jié)點。最后，在物理執(zhí)行引擎層次，從Spark算法的角度支持凸包查詢操作。

圖2 基于SparkSQL的凸包查詢框架

3.1 用戶查詢接口

在圖2所示的架構中，對Spark兩種常見的調用方式進行拓展，在SQL語句層次上，加入凸包關鍵字ST_ConvexHull，在DataFrame API調用層次上，加入一些針對DataFrame層次的調用。兩個使用示例如下：

在模式分類中，線性分類模型是一種比較常見的模型（如圖3所示），在線性分類模型中有求樣本集間最近點對的過程，這個過程可以利用凸包操作來加速。可以將原始數(shù)據(jù)集導入SparkSQL中存儲在表t中，表t中包含描述點集特征的兩列x和y，以及描述點分類的tag信息，則求t中tag為1的所有點特征的凸包，可以用如下SQL語句查詢：

類似的，可以通過調用SparkSQL DataFrame API查詢，查詢示例如下：

dataframe.filter（$“tag”=1）.covnexHull（Point（x，y））

圖3 線性分類模型

3.2 空間關鍵字解析器

在SparkSQL的Parser層，系統(tǒng)加入了針對空間幾何關鍵的一些映射，如POINT關鍵字，將空間上點的屬性名稱聚合成為一個點對象，通過ST_ConvexHull關鍵字表示凸包操作的查詢。

解析器的作用在于把一個SQL語句解析成為對應的邏輯計劃節(jié)點，供物理執(zhí)行引擎直接引用。

3.3 物理執(zhí)行引擎

物理執(zhí)行引擎為空間幾何算法實現(xiàn)的關鍵部分，框架在這一部分展開了較多的算法層次的研究。本文將在這一層次展開優(yōu)化。為了說明算法效率，首先給出了一個單機下的解決方案CHStand算法，該算法應用于單機平臺，接著給出Spark平臺下實現(xiàn)比較簡單的CHSpark算法，并通過優(yōu)化改進CHSpark算法，得到最終的優(yōu)化版CHGeom算法。

值得注意的是，在物理執(zhí)行引擎層次提出的Spark平臺下的算法均不對Spark內(nèi)核進行改變，只存在對SparkSQL內(nèi)核的改變，這在一定程度上保證了系統(tǒng)的移植性，可以十分方便地移植到Spark其他版本的系統(tǒng)中。

4 兩個對比實現(xiàn)算法

本章主要介紹兩種實驗對比算法，基于Andrew單調鏈的單機平臺的凸包算法CHStand，以及結合單機平臺實現(xiàn)思想和Spark平臺特點的分布式算法CHSpark，分析兩種實驗算法各自的優(yōu)缺點，優(yōu)化并補充各算法的缺陷可以得到下一章介紹的CHGeom實現(xiàn)算法。

4.1 單節(jié)點環(huán)境下的凸包算法CHStand

如第2章介紹，在單機環(huán)境下，有多種解決凸包問題的算法，如Jarvis步進法、Graham掃描法、快包（quickhull）、Andrew單調鏈算法等。由于凸包運算滿足交換律和結合律[15]，任意單機版算法可以很自然地作為一個局部算法拓展到Spark平臺上，本文采取一種常見的Andrew單調鏈算法作為單節(jié)點條件下的CHStand算法的實現(xiàn)。

CHStand算法的整體思想如圖4所示。算法首先將需要求解的凸包分為上下兩部分，分別叫作上殼（Upper Hull）和下殼（Lower Hull），對上殼和下殼分別求邊界鏈，之后將兩者拼接起來即得到完整的凸包。具體實現(xiàn)如下：對點集按照x、y坐標的字典序進行排序，得到一系列點，連接點集的最左端和最右端的點作為遍歷的起點和終點。第一次遍歷點集，構建上殼，對任意字典序的三個點，如果三個點構成順時針的次序，如圖4中A1、A2、A3三個點，構成順時針方向，則點A1一定是上殼的一部分，將A1作為上殼的一部分放入結果集合中。下一組點則考慮A2、A3、A4，以此類推。如果連續(xù)的三個點構成逆時針方向，如圖4中 A3、A4、A5所示，則 A4一定不是凸包的一部分，需繼續(xù)考慮A3、A5、A6。下殼也具有類似的性質，用類似算法可以求解出下殼的集合，將兩條單調鏈首尾拼接起來即得到最終的凸包。

圖4 Andrew單調鏈算法

該算法排序可采用快速排序[16]的方法進行，其時間復雜度是O(N ln N)，對上殼和下殼的求解分別需要O(N)時間，綜合時間復雜度是O(N ln N)。

CHStand算法的缺點在于并行度不高，只能并行處理上殼和下殼的計算，而且需要了解并行計算框架的特點才能設計出最大并行度為2的算法。

4.2 Spark平臺下的凸包算法CHSpark

鑒于CHStand算法的并行度不高問題，本文考慮在Spark上面實現(xiàn)一種高效率的凸包算法。可以觀察到，凸包運算滿足結合律，那么對于原始數(shù)據(jù)集的一個劃分，每個劃分上求出凸包之后，對所有劃分求凸包的結果和原始數(shù)據(jù)集上直接求凸包的操作結果一致。

算法整體分為數(shù)據(jù)導入、局部計算和全局計算三部分。第一步數(shù)據(jù)導入，Spark通過HDFS獲取數(shù)據(jù)之后，數(shù)據(jù)集按照一定的分區(qū)方式，存儲在集群各節(jié)點的內(nèi)存中，為減少這個過程中的數(shù)據(jù)混洗耗時，采用默認的數(shù)據(jù)導入方式，即利用HDFS的數(shù)據(jù)分區(qū)方式，每個塊數(shù)據(jù)64 MB（或可設定成128 MB）作為一個分區(qū)，導入內(nèi)存中。這個過程利用Spark默認的數(shù)據(jù)導入方式，結合HDFS的分區(qū)大小，保證每個節(jié)點的負載盡量均衡。第二步局部計算過程，為保證實驗具有可對比性，在每個分區(qū)中，利用Spark的mapPartition方法聚合所有元素，利用Andrew單調鏈算法，計算每個分區(qū)內(nèi)部點的凸包結果，發(fā)送到Driver端，Driver收集到所有的局部結果之后，進行第三步。第三步為全局計算，將第二步中計算的局部結果聚合起來，為所有的點運行Andrew單調鏈算法，得到最終的結果。后面部分的實驗也證明了凸包運算的結果和單機運行的單調鏈算法結果一致。

5 進一步優(yōu)化算法

通過第4章對CHStand和CHSpark算法的分析，初步看出一些凸包的解決方案各自有其特點。CHStand算法利用單節(jié)點的Andrew單調鏈算法，其數(shù)據(jù)處理受限于單節(jié)點的性能，但是CHStand是單節(jié)點平臺下的一種可行的解決方案。CHSpark算法將其拓展到Spark平臺上，充分利用凸包的結合性質，利用Spark平臺的特點，增加并行度，高效率地完成凸包過程的計算。但是觀察發(fā)現(xiàn)，對于分區(qū)內(nèi)部的一些點，在計算過程中可以采取一定的方式過濾掉，得到一定的性能上優(yōu)化。本章通過采樣和STR（Sort-Tile-Recursive[18]）的方式過濾掉一些點，由此得到一種高效的解決方案CHGeom。

5.1 一個重要的觀察

使用STR分區(qū)方式對任意分布的數(shù)據(jù)集劃分，即將空間等分為N份，首先在x軸方向將空間等分成個切片，每個切片內(nèi)部將按照y軸方向相等劃分成份。取第一個切片的最大x坐標，最后一個切片的最小x坐標，每個切片的第一份的y坐標最大值，每個切片的最后一份的y坐標最小值，組成一個矩形（圖5中P1和P2構成的矩形），矩形內(nèi)部所有的點，不可能是凸包結果的一部分。

圖5 空間的STR劃分方法

5.2 CHGeom算法

利用5.1節(jié)的結論，CHGeom算法解析SQL表達式或DataFrame的查詢后，利用Spark的filter操作，剪枝一些不可能在結果集合中的點，利用剪枝之后的點集運行CHSpark算法，性能可以得到比較大的提升。算法偽代碼如下。

算法1 CHGeom

Input：a point set ps，with geometrical info

Output：the ConvexHull for point set ps

1.rdd=load ps to RDD

2.sampled=rdd.sample（min（rdd.size*0.01，1 0000）/rdd.size）

3.str_bound=str_partition（sampled）

4.P1，P2=getEdgePoint（str_bound）

5.pruned=rdd.filter（_.isNotInside（P1，P2））

6.local_res=pruned.mapPartition（part=＞CHStand（part））

7.global_res=CHStand（local_res.collect（））

8.return global_res

算法整體分為以下步驟：

數(shù)據(jù)采樣和邊界點的確定：該步驟利用Spark的RDD sample方法，獲取一個來自點集的1%左右的點（上限10 000個點），對其運行STR分區(qū)方法，獲取其邊界P1和P2兩個點。

局部操作：每個分區(qū)內(nèi)部過濾掉在矩形P1和P2之間的部分后，局部求解凸包，之后把結果發(fā)送到Driver端。

全局操作：Driver段完成所有局部結果的收集之后，運行全局的Andrew單調鏈算法，返回結果給用戶。

5.3 CHGeom算法分析

本節(jié)從時間復雜度和拓展性兩方面分析CHGeom算法。

拓展性分析：在拓展性方面，由圖2整體架構中可以看出，算法基于Spark平臺，在框架上可以直接拓展到Spark平臺支持的任意節(jié)點數(shù)量。在數(shù)據(jù)規(guī)模上，Spark自身利用磁盤交換技術，將不能保存到內(nèi)存中的數(shù)據(jù)通過磁盤保存，需要使用時讀入硬盤，來保證數(shù)據(jù)規(guī)模上的拓展性。這些行為對用戶隱藏，只需要設定緩存級別參數(shù)即可完成調整。通過代碼片段CHGeom算法實現(xiàn)上來看，所有代碼直接調用Spark API，不對Spark核心代碼進行修改，因此代碼的移植性較好。

CHGeom算法利用一個矩形剪枝掉不可能在結果集合中的部分，通過全局過濾的方式來加速查詢性能。STR分區(qū)方式可以適用于非均勻分布的點集，本文實驗部分會通過非均勻分布的數(shù)據(jù)集OSM的查詢對比來說明這一點。

6 實驗

6.1 實驗環(huán)境

本文采用由17個節(jié)點構成的集群運行對比實驗，由于實驗設備購置時間不一致，主要包含以下三類不同配置的機器節(jié)點：（1）6核Intel Xeon E5-2620 2.00 GHz，192 GB內(nèi)存的Dell R720服務器兩臺；（2）6核Intel E5-2603 v3 1.6 GHz，20 GB內(nèi)存的Dell R630服務器8臺；（3）6核Intel Xeon E5-2609 v3 1.9 GHz，16 GB內(nèi)存的Dell R630服務器7臺。各節(jié)點具有相同的軟件配置：（1）Ubuntu 14.04.2 LTS；（2）Apache Hadoop 2.4.1；（3）Apache Spark 1.6.2。選取一臺具有硬件配置（1）的較大內(nèi)存服務器作為主節(jié)點，其余節(jié)點作為從節(jié)點。所有Spark任務均在Standalone運行模式下運行，主節(jié)點默認使用150 GB內(nèi)存，用來存儲Driver程序的內(nèi)存對象，所有從節(jié)點內(nèi)存默認使用15 GB（平均每核2.5 GB內(nèi)存）作為從節(jié)點計算和存儲的內(nèi)存。

實驗使用的數(shù)據(jù)主要分為兩類：一類是實際數(shù)據(jù)集，擬采用OpenStreetMap（OSM-POINT）歐洲地區(qū)路網(wǎng)端點作為原始數(shù)據(jù)集，大小為164 GB，數(shù)據(jù)記錄數(shù)約為22億，每條記錄包含定長的記錄ID，兩個雙精度浮點數(shù)表示的經(jīng)緯度坐標，以及兩個定長的文本信息塊，用來記錄其他信息，對原始數(shù)據(jù)集隨機采樣，得到一些大小不一樣的不同數(shù)據(jù)集，作為不同大小的數(shù)據(jù)源集合。第二類數(shù)據(jù)集是生成的SYNTH數(shù)據(jù)集，根據(jù)不同的點分布，采取不同的生成策略，生成大小分級的數(shù)據(jù)集，進行算法時間對比。

6.2 OSM-POINT數(shù)據(jù)集下三種實驗性能對比

本實驗關注的是三種實驗算法在真實數(shù)據(jù)下運行的性能對比，實驗運行在OSM-POINT數(shù)據(jù)集下，變化點集中的記錄數(shù)量，記錄程序運行時間，得到圖6所示的運行時間圖。

圖6 OSM-POINT數(shù)據(jù)集實驗對比

圖6 中，CHStand算法數(shù)據(jù)量達到15億時，運行時間已經(jīng)超過10小時，因此在圖中未標出。從圖中可以近似看出，在數(shù)據(jù)量從2.5億（250×106）增加到5億到10億時，單機版的算法CHStand的執(zhí)行時間呈指數(shù)型增長，CHSpark有一定的優(yōu)化，CHGeom算法相比CHStand和CHSpark都有更加明顯的優(yōu)化。在使用完整數(shù)據(jù)集22億（132 GB）數(shù)據(jù)集時，CHSpark算法運行時間仍在2 000 s以上，相比之下，CHGeom算法運行時間約240 s，有了十分明顯的性能提升。從圖中還可以看出，在數(shù)據(jù)集較小的情況下，CHSpark和CHGeom算法的性能差距不太大，說明CHGeom剪枝效果在數(shù)據(jù)集較小的情況下，剪枝的比例比較小，對比來說，計算STR邊界和內(nèi)部矩形的時間較長，因此運行時間近似相同。

6.3 不同數(shù)據(jù)分布下的算法運行時間

CHGeom算法中存在使用采樣和STR分區(qū)兩個因素的影響，本實驗重點研究幾個不同數(shù)據(jù)分布下的算法性能。主要研究的數(shù)據(jù)分布如圖7所示。

圖7 不同的數(shù)據(jù)分布

均勻分布是一種最簡單的分布，本文在坐標系中x在0～1 000范圍內(nèi)和y在0～1 000范圍內(nèi)隨機生成一些數(shù)據(jù)量的點；高斯分布是一種正態(tài)分布，本文使用java隨機庫的nextGaussian方法生成兩組均值為0，標準差為1.0的數(shù)據(jù)集，分別作為點集的橫縱坐標；對角分布和反對角分布均為在矩形對角線附近分布的點集，均勻分布生成器生成一個x坐標之后，生成高斯分布的距離d，在對角線的x坐標處，截取d距離的點集即可得到三角分布和反三角分布的兩組數(shù)據(jù)集。在這四個數(shù)據(jù)集下運行CHGeom算法得到圖8所示的實驗結果圖。

圖8 不同數(shù)據(jù)分布下的CHGeom算法運行時間

觀察圖8可以發(fā)現(xiàn)，針對單種分布的數(shù)據(jù)集，如對角分布的一組數(shù)據(jù)（圖中藍色部分），其運行時間整體隨時間呈現(xiàn)正相關，其余分布也能說明這一特點。縱向比較同一數(shù)據(jù)規(guī)模的不同分布的數(shù)據(jù)，可以得出基本結論，反三角分布的情況下耗時最長，三角分布次之，高斯分布和均勻分布的點集運行時間較短，基本不相上下。

分析其原因，在三角分布和反三角分布的情況下，數(shù)據(jù)在空間中具有一定的傾斜性，集中在某一/某些區(qū)域內(nèi)較多，造成STR分區(qū)對性能邊界不明顯，進而導致在Spark平臺上運行的整體剪枝效果不明顯，從而運行時間較長。在均勻分布和高斯分布的情況下則不存在如上問題，相對均勻情況下剪枝效果較好。實際數(shù)據(jù)集OSM-POINT主要為歐洲區(qū)域的路網(wǎng)端點信息，可能會存在一些噪聲數(shù)據(jù)，因此其分布具有很強的傾斜性，在歐洲部分經(jīng)緯度區(qū)域比較集中，其他區(qū)域比較分散，其運行時間會比反三角分布的點集運行時間更長，比較10億數(shù)據(jù)集下的反三角分布（圖8）和實際數(shù)據(jù)集（圖6）的運行時間，可以得到驗證。

6.4 與SpatialHadoop的實驗對比

SpatialHadoop自帶數(shù)據(jù)生成器，實驗中，采用Spatial-Hadoop自帶的隨機點集生成器，生成一組10 GB、50 GB、80 GB和100 GB的均勻分布空間數(shù)據(jù)集，以parquet格式存儲在HDFS上，在其上分別運行20次凸包操作，取平均時間，與CHGeom算法相同數(shù)據(jù)集下完成實驗對比，可以得到圖9的實驗結果。從圖中可以看出，在數(shù)據(jù)均勻分布，數(shù)據(jù)采用parquet格式存儲時，SpatialHadoop的運行時間是CHGeom的10倍左右。

圖9 CHGeom和SpatialHadoop算法運行時間對比

7 拓展性討論及未來工作展望

本文提出的一些基礎算法思想可以比較友好地拓展到一些常見的空間幾何算法中，如最遠點對、星形線（Skyline）的計算。

7.1 最遠點對

最遠點對問題是凸包問題的一個自然拓展，因為點集的最遠點對一定落在凸包上面[10]，可以直接利用凸包的計算結果，求得凸包上最遠的點對，即可得到全局的最遠點對結論。

7.2 星形線

星形線可以利用類似于CHGeom算法的思想進行計算，觀察到一定的結論之后剪枝，然后通過局部和全局兩個層次的運算，得出最終的結論。如城市規(guī)劃中使用無線傳感器網(wǎng)絡的居民區(qū)構成的星形線[19]計算可以通過以下SQL語句實現(xiàn)：

7.3 Spark平臺下的幾何計算平臺

除了一些基本算法的實現(xiàn)外，可以基于Spark搭建完整的空間幾何查詢平臺進行拓展，集成常用的算法，提供一個友好接口的軟件庫，供數(shù)據(jù)分析學家或相關人員使用。如圖3中線性分類模型中的最近點對通過以下SQL語句來實現(xiàn)：

8 結束語

本文提出了一個完整的基于Spark的凸包操作查詢框架，闡述了Spark平臺下的空間幾何中凸包算法的實現(xiàn)細節(jié)。從基礎的單機版的CHStand算法入手，分析其性能瓶頸，提出基于并行度優(yōu)化的Spark平臺的CHSpark算法，進一步優(yōu)化計算性能，剪枝大部分不可能在結果集合中的點，得到一個性能相對較優(yōu)的CHGeom算法，并討論數(shù)據(jù)分布下的CHGeom算法性能差異，驗證了在實際數(shù)據(jù)集中，CHGeom算法仍能保持比較好的性能。本文提出的一些算法思想可以很友好地拓展到一些其他常見空間查詢上，拓展之后形成空間幾何查詢平臺可供模式識別、地理信息系統(tǒng)等領域分析者使用。