李格非，馬蔚吟，李 力

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

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

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

1 概述

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

Apache Spark[3]（后文簡(jiǎn)稱Spark）是一個(gè)常見(jiàn)的用來(lái)實(shí)現(xiàn)高吞吐低延時(shí)查詢的框架，其基于內(nèi)存計(jì)算的特性，使得Spark在性能上超過(guò)Hadoop多個(gè)數(shù)量級(jí)。Spark使用彈性分布式數(shù)據(jù)集（Resilient Distributed Dataset，RDD[3]）實(shí)現(xiàn)基于內(nèi)存的數(shù)據(jù)存儲(chǔ)和計(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)的接口對(duì)用戶不友好，用戶需要花很多時(shí)間來(lái)學(xué)習(xí)理解，甚至閱讀源代碼才能正確地使用這些系統(tǒng)。其次，這些系統(tǒng)沒(méi)有形成一個(gè)整體，不支持多層嵌套查詢，即某一次分析的結(jié)果作為下一次分析操作的輸入數(shù)據(jù)。深層次來(lái)說(shuō)，這些系統(tǒng)將Spark視為一個(gè)黑盒，忽略其自身的分區(qū)、容錯(cuò)等特性，由此設(shè)計(jì)出的系統(tǒng)，接口友好性和計(jì)算性能遠(yuǎn)不能滿足用戶需求。

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

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

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

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

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

2 背景知識(shí)

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

2.1 凸包

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

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

圖1 凸包

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

2.2 Spark與Spark SQL

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

SparkSQL是Spark開(kāi)發(fā)組的成員針對(duì)關(guān)系型數(shù)據(jù)開(kāi)發(fā)的一套庫(kù)軟件，其前身是支持Hadoop的關(guān)系型數(shù)據(jù)庫(kù)引擎Shark。SparkSQL的整體架構(gòu)圖如圖2中藍(lán)色部分所示，主要由API調(diào)用、語(yǔ)法解析、物理映射等部分組成。SparkSQL在數(shù)據(jù)存儲(chǔ)上采用列存的方式優(yōu)化數(shù)據(jù)存儲(chǔ)，采用Catalyst引擎完成SQL語(yǔ)句的解析和用戶調(diào)用的解析，完成SQL語(yǔ)句到抽象語(yǔ)法樹(shù)，到邏輯計(jì)劃的維護(hù)、優(yōu)化過(guò)程。優(yōu)化之后的邏輯計(jì)劃根據(jù)其執(zhí)行特點(diǎn)，進(jìn)一步映射到Spark的物理計(jì)劃，使用Spark作為底層執(zhí)行引擎完成SQL語(yǔ)句的執(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]對(duì)這些算法進(jìn)行了總結(jié)?？傮w來(lái)說(shuō)，這些算法[8-12，14]的缺點(diǎn)在于單節(jié)點(diǎn)的存儲(chǔ)和計(jì)算能力十分有限。近期也有基于Hadoop的CG_Hadoop等算法平臺(tái)的研究，其運(yùn)行性能遠(yuǎn)不能達(dá)到數(shù)據(jù)實(shí)時(shí)分析的需求。

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

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

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

3.1 用戶查詢接口

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

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

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

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

圖3 線性分類模型

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

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

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

3.3 物理執(zhí)行引擎

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

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

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

本章主要介紹兩種實(shí)驗(yàn)對(duì)比算法，基于Andrew單調(diào)鏈的單機(jī)平臺(tái)的凸包算法CHStand，以及結(jié)合單機(jī)平臺(tái)實(shí)現(xiàn)思想和Spark平臺(tái)特點(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)境下，有多種解決凸包問(wèn)題的算法，如Jarvis步進(jìn)法、Graham掃描法、快包（quickhull）、Andrew單調(diào)鏈算法等。由于凸包運(yùn)算滿足交換律和結(jié)合律[15]，任意單機(jī)版算法可以很自然地作為一個(gè)局部算法拓展到Spark平臺(tái)上，本文采取一種常見(jiàn)的Andrew單調(diào)鏈算法作為單節(jié)點(diǎn)條件下的CHStand算法的實(shí)現(xiàn)。

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

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

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

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

4.2 Spark平臺(tái)下的凸包算法CHSpark

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

算法整體分為數(shù)據(jù)導(dǎo)入、局部計(jì)算和全局計(jì)算三部分。第一步數(shù)據(jù)導(dǎo)入，Spark通過(guò)HDFS獲取數(shù)據(jù)之后，數(shù)據(jù)集按照一定的分區(qū)方式，存儲(chǔ)在集群各節(jié)點(diǎn)的內(nèi)存中，為減少這個(gè)過(guò)程中的數(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è)過(guò)程利用Spark默認(rèn)的數(shù)據(jù)導(dǎo)入方式，結(jié)合HDFS的分區(qū)大小，保證每個(gè)節(jié)點(diǎn)的負(fù)載盡量均衡。第二步局部計(jì)算過(guò)程，為保證實(shí)驗(yàn)具有可對(duì)比性，在每個(gè)分區(qū)中，利用Spark的mapPartition方法聚合所有元素，利用Andrew單調(diào)鏈算法，計(jì)算每個(gè)分區(qū)內(nèi)部點(diǎn)的凸包結(jié)果，發(fā)送到Driver端，Driver收集到所有的局部結(jié)果之后，進(jìn)行第三步。第三步為全局計(jì)算，將第二步中計(jì)算的局部結(jié)果聚合起來(lái)，為所有的點(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)化算法

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

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

使用STR分區(qū)方式對(duì)任意分布的數(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è)來(lái)自點(diǎn)集的1%左右的點(diǎn)（上限10 000個(gè)點(diǎn)），對(duì)其運(yùn)行STR分區(qū)方法，獲取其邊界P1和P2兩個(gè)點(diǎn)。

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

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

5.3 CHGeom算法分析

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

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

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

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

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

本文采用由17個(gè)節(jié)點(diǎn)構(gòu)成的集群運(yùn)行對(duì)比實(shí)驗(yàn)，由于實(shí)驗(yàn)設(shè)備購(gòu)置時(shí)間不一致，主要包含以下三類不同配置的機(jī)器節(jié)點(diǎn)：（1）6核Intel Xeon E5-2620 2.00 GHz，192 GB內(nèi)存的Dell R720服務(wù)器兩臺(tái)；（2）6核Intel E5-2603 v3 1.6 GHz，20 GB內(nèi)存的Dell R630服務(wù)器8臺(tái)；（3）6核Intel Xeon E5-2609 v3 1.9 GHz，16 GB內(nèi)存的Dell R630服務(wù)器7臺(tái)。各節(jié)點(diǎn)具有相同的軟件配置：（1）Ubuntu 14.04.2 LTS；（2）Apache Hadoop 2.4.1；（3）Apache Spark 1.6.2。選取一臺(tái)具有硬件配置（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)存，用來(lái)存儲(chǔ)Driver程序的內(nèi)存對(duì)象，所有從節(jié)點(diǎn)內(nèi)存默認(rèn)使用15 GB（平均每核2.5 GB內(nèi)存）作為從節(jié)點(diǎn)計(jì)算和存儲(chǔ)的內(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億，每條記錄包含定長(zhǎng)的記錄ID，兩個(gè)雙精度浮點(diǎn)數(shù)表示的經(jīng)緯度坐標(biāo)，以及兩個(gè)定長(zhǎng)的文本信息塊，用來(lái)記錄其他信息，對(duì)原始數(shù)據(jù)集隨機(jī)采樣，得到一些大小不一樣的不同數(shù)據(jù)集，作為不同大小的數(shù)據(jù)源集合。第二類數(shù)據(jù)集是生成的SYNTH數(shù)據(jù)集，根據(jù)不同的點(diǎn)分布，采取不同的生成策略，生成大小分級(jí)的數(shù)據(jù)集，進(jìn)行算法時(shí)間對(duì)比。

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

本實(shí)驗(yàn)關(guān)注的是三種實(shí)驗(yàn)算法在真實(shí)數(shù)據(jù)下運(yùn)行的性能對(duì)比，實(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)對(duì)比

圖6 中，CHStand算法數(shù)據(jù)量達(dá)到15億時(shí)，運(yùn)行時(shí)間已經(jīng)超過(guò)10小時(shí)，因此在圖中未標(biāo)出。從圖中可以近似看出，在數(shù)據(jù)量從2.5億（250×106）增加到5億到10億時(shí)，單機(jī)版的算法CHStand的執(zhí)行時(shí)間呈指數(shù)型增長(zhǎng)，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算法的性能差距不太大，說(shuō)明CHGeom剪枝效果在數(shù)據(jù)集較小的情況下，剪枝的比例比較小，對(duì)比來(lái)說(shuō)，計(jì)算STR邊界和內(nèi)部矩形的時(shí)間較長(zhǎng)，因此運(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ù)分布

均勻分布是一種最簡(jiǎn)單的分布，本文在坐標(biāo)系中x在0～1 000范圍內(nèi)和y在0～1 000范圍內(nèi)隨機(jī)生成一些數(shù)據(jù)量的點(diǎn)；高斯分布是一種正態(tài)分布，本文使用java隨機(jī)庫(kù)的nextGaussian方法生成兩組均值為0，標(biāo)準(zhǔn)差為1.0的數(shù)據(jù)集，分別作為點(diǎn)集的橫縱坐標(biāo)；對(duì)角分布和反對(duì)角分布均為在矩形對(duì)角線附近分布的點(diǎn)集，均勻分布生成器生成一個(gè)x坐標(biāo)之后，生成高斯分布的距離d，在對(duì)角線的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)，針對(duì)單種分布的數(shù)據(jù)集，如對(duì)角分布的一組數(shù)據(jù)（圖中藍(lán)色部分），其運(yùn)行時(shí)間整體隨時(shí)間呈現(xiàn)正相關(guān)，其余分布也能說(shuō)明這一特點(diǎn)?？v向比較同一數(shù)據(jù)規(guī)模的不同分布的數(shù)據(jù)，可以得出基本結(jié)論，反三角分布的情況下耗時(shí)最長(zhǎng)，三角分布次之，高斯分布和均勻分布的點(diǎn)集運(yùn)行時(shí)間較短，基本不相上下。

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

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

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

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

7 拓展性討論及未來(lái)工作展望

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

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

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

7.2 星形線

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

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

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

8 結(jié)束語(yǔ)

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