Spark平臺下的凸包問題研究

李格非，馬蔚吟，李 力

1.上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200240

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

3.上海交通大學(xué) 軟件學(xué)院，上海 200240

1 概述

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

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

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

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

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

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

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

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

2 背景知識

本章主要介紹已有的凸包算法和Spark平臺相關(guān)的基礎(chǔ)背景。

2.1 凸包

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

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

圖1 凸包

凸包問題在模式識別、圖像處理、統(tǒng)計(jì)學(xué)、地理信息系統(tǒng)、博弈論、圖論等領(lǐng)域中被廣泛使用。計(jì)算幾何學(xué)中的一個(gè)典型應(yīng)用是最遠(yuǎn)點(diǎn)對問題的求解，因?yàn)辄c(diǎn)集的最遠(yuǎn)點(diǎn)對一定在凸包上，由這一性質(zhì)可以利用凸包算法和Rotating Caliper[8]算法解決最遠(yuǎn)點(diǎn)對問題。

2.2 Spark與Spark SQL

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

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

2.3 凸包計(jì)算的研究

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

3 整體結(jié)構(gòu)

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

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

3.1 用戶查詢接口

在圖2所示的架構(gòu)中，對Spark兩種常見的調(diào)用方式進(jìn)行拓展，在SQL語句層次上，加入凸包關(guān)鍵字ST_ConvexHull，在DataFrame API調(diào)用層次上，加入一些針對DataFrame層次的調(diào)用。兩個(gè)使用示例如下：

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

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

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

圖3 線性分類模型

3.2 空間關(guān)鍵字解析器

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

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

3.3 物理執(zhí)行引擎

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

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

4 兩個(gè)對比實(shí)現(xiàn)算法

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

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

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

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

圖4 Andrew單調(diào)鏈算法

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

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

4.2 Spark平臺下的凸包算法CHSpark

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

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

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

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

5.1 一個(gè)重要的觀察

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

圖5 空間的STR劃分方法

5.2 CHGeom算法

利用5.1節(jié)的結(jié)論，CHGeom算法解析SQL表達(dá)式或DataFrame的查詢后，利用Spark的filter操作，剪枝一些不可能在結(jié)果集合中的點(diǎn)，利用剪枝之后的點(diǎn)集運(yùn)行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ù)采樣和邊界點(diǎn)的確定：該步驟利用Spark的RDD sample方法，獲取一個(gè)來自點(diǎn)集的1%左右的點(diǎn)（上限10 000個(gè)點(diǎn)），對其運(yùn)行STR分區(qū)方法，獲取其邊界P1和P2兩個(gè)點(diǎn)。

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

全局操作：Driver段完成所有局部結(jié)果的收集之后，運(yùn)行全局的Andrew單調(diào)鏈算法，返回結(jié)果給用戶。

5.3 CHGeom算法分析

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

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

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

6 實(shí)驗(yàn)

6.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

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

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

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

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

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

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

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

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

6.4 與SpatialHadoop的實(shí)驗(yàn)對比

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

圖9 CHGeom和SpatialHadoop算法運(yùn)行時(shí)間對比

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

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

7.1 最遠(yuǎn)點(diǎn)對

最遠(yuǎn)點(diǎn)對問題是凸包問題的一個(gè)自然拓展，因?yàn)辄c(diǎn)集的最遠(yuǎn)點(diǎn)對一定落在凸包上面[10]，可以直接利用凸包的計(jì)算結(jié)果，求得凸包上最遠(yuǎn)的點(diǎn)對，即可得到全局的最遠(yuǎn)點(diǎn)對結(jié)論。

7.2 星形線

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

7.3 Spark平臺下的幾何計(jì)算平臺

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

8 結(jié)束語

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