CG_Hadoop：基于MapReduce的計算幾何
摘要：Hadoop使用了MapReduce編程范式，目前已經被公認為是分布 式環境中分析大數據的標準框架。然而，它并不能很好的應用于大規模的計算幾何處理。本文介紹的CG_Hadoop是一套可伸縮的和高效的 MapReduce算法，用于處理各種基本計算幾何問題，例如多邊形合并、skyline（輪廓線）、convex hull(凸包)、farthest pair(最遠相對)以及最近相對等，這些都是其它幾何算法的基礎。對于每一個計算幾何操作，CG_Hadoop有兩個版本，一個基于Apache Hadoop系統，一個基于SpatialHadoop系統。CG_Hadoop更適合空間操作。這些提出的算法形成了一個全面的計算幾何操作 MapReduce庫。大量的實驗結果表明CG_Hadoop達到了29倍和260倍，比使用Hadoop和SpatialHadoop都具有更好的性 能。試驗采用25臺機器組成的集群，數據集大小為128GB。
1、引言
Hadoop[17]是在分布式環境下高效處理大量數據的一個框架，采用了MapReduce編程范式，是通過兩個函數，即Map和Reduce， 進行的并行程序。Map函數將單一數據記錄映射為一組key/Value組對<k,v>，而Reduce函數是將同一Key值的所有 Value中取出并產生最終結果。MapReduce范式的簡便性和靈活性使得Hadoop能夠應用在一些大規模的應用中，如機器學習[13]，兆字節文 件排序[29]以及圖像處理[14]等。
與此同時，隨著設備和應用程序的大量出現，也產生了巨量的空間數據，例如智能手機、空間望遠鏡[6]和社交工具[28,35]等。如此大量的空間數 據需要充分利用MapReduce編程范式[11]的優勢去解決各種空間操作。在計算幾何算法中，最重要的空間操作就是對空間范圍內的幾何實體進行表達和 操作。這些操作包括：多邊形合并、skyline（輪廓線）、convex hull(凸包)、farthest pair( 最遠相對)以及最近相對等。這對這些問題盡管已經存在了很多優秀的計算幾何算法，但是，這些算法并不能很好的處理包含數億點的現有空間數據集。例如，計算 4億個點數據集的凸多邊形，如果采用傳統的方法可能需要花費三個小時，計算合并500萬個多邊形需要花費1個小時，對于更大的數據集可能會出現內存溢出， 計算失敗。
本文介紹的CG_Hadoop，具有一系列可伸縮而且效率高的MapReduce算法用于解決各種基礎計算幾何問題，如polygonunion, skyline ,convex hull,farthest pair, and closest pair等，這些算法都是其他幾何計算的基礎[5,33]。CG_Hadoop與傳統的計算地理算法相比，在處理大尺度空間數據時表現更好的性能。針對每 一個計算幾何算法，本文都介紹了CG_Hadoop的兩個版本，一個基于Apache Hadoop系統部署[17]，另外一個基于開源的SpatialHadoop進行部署[12]。前者是一個開源的MapReduce項目，已經廣泛應用 于MapReduce應用[9,13,14,19,20,29]。后者是一個基于Hadoop系統進行了封裝，采用了空間索引，使其更適合空間操作。
在CG_Hadoop中所有算法的主要思想是充分利用許多計算幾何算法分而治之的思想。分而治之的特性適合MapReduce環境，該環境是在一個 計算機器集群中多個節點并行處理。因此，在MapReduce環境中，CG_Hadoop必須適應傳統計算算法來更好的工作。例如，不想傳統算法那樣將輸 入數據一分為二進行多次計算，而CG_Hadoop將輸入劃分為更小的組塊，確保在每一個MapReduce中都被計算出結果，這樣對于Hadoop和 SpatialHadoop來說都比較適合。另外，本文采用了SpatialHadoop中分布式空間索引，通過先將輸入分塊但不會影響計算幾何操作的結 果，只要有可能，加快計算的速度，。
CG_Hadoop是SpatialHadoop（http://spatialhadoop.cs.umn.edu/）可用代碼的一部分，形成了 計算幾何操作中綜合MapReduce的核心部分。CG_Hadoop具有開源性質，將作為一個研究載體供其他研究者建立更多的基于MapReduce編 程范式的計算幾何算法。實驗環境使用25臺機器的一個集群，真實數據和合成的數據多達128GB，實驗表明基于Hadoop和SpatialHadoop 的CG_Hadoop比傳統的算法達到了29倍和260倍,都具有更好的性能。
本文剩余內容組織如下。第二節簡單介紹了所需環境。從第3節到第7節分別介紹了基于MapReduce的各種算法操作，包括多邊形合并，Skyline,凸多邊形，最遠組對和最近組對。第8節進行了實驗評價。第9節進行了討論。最后一節是本文的結論。
2、背景
本章節給出了關于Hadoop和SpatialHadoop兩個系統的背景信息。CG_Hadoop中一系列的計算幾何操作同時在這兩個平臺上使用。
2.1 Hadoop
Hadoop[17]是一個基于大集群進行數據處理的開源框架。一個Hadoop集群包含了一個主節點和幾個從節點。主節點存儲文件的元信息（如名 稱和訪問權限等），而從幾點存儲了文件中實際的數據（如記錄等）。一個文件在處理之前，一般是被切分為64M（稱之為塊）的大塊，然后加載到Hadoop 分布式文件系統（HDFS）上。主節點將跟蹤文件如何被分塊和每一塊存儲的位置，而從節點存儲數據塊。類比普通的文件系統，主節點存儲文件配置表和索引節 點，從節點存儲文件數據。
MapReduce程序配置一個MapReduce工作并將其提交給主節點。一個MapReduce工作包含一系列配置參數，如Map函數和輸入文 件等。主節點將這個工作分為幾個Map任務，然后分解這些任務并在每一個從節點上執行每一個任務。這也將輸入的文件分塊，然后分配每快給一個從節點去作為 一個Map任務去處理。Map任務通過配置的記錄讀取函數解析配置塊，然后生成一系列的Key-value組對<k1,v1>，這些組對會通 過Map函數生成一系列中間組對<k2,v2>。中間組對通過K2進行分組，然后reduce函數收集所有同一關鍵值的中間記錄，然后經過處 理生成最終記錄<k3,v3>集,并將其存儲在HDFS文件中。
MapReduce和Hadoop已經被許多主流的公司使用，如Google[11]、Yahoo![9]、微軟的Dryad[19]，以及 推ter[20]。同時在一些大規模的應用中也很受歡迎，如機器學習[13]，兆字節文件排序[29]以及圖像處理[14]等。
2.2 SaptialHadoop
SpatialHadoop是基于Hadoop的一個全面擴展，能夠實現空間操作的高效處理。重要的是，SpatialHadoop在Hadoop 存儲層提供了兩層空間索引，實現了基于格網文件[26]、R-tree[16]索引。豐富了MapReduce層，嵌入了兩個新的組件，在該層允許使用空 間索引。SpatialHadoop通過建立索引來提高一些空間操作的算法效率。
SpatialHadoop的空間索引包括一個全局索引和多個局部索引。全局索引通過集群節點數據劃分數據，而局部索引在每一個節點內部組織數據。 在MapReduce層新嵌入的組件通過全局和局部索引來修剪文件的分區和記錄，但不會影響操作結果。修剪的標準取決于用于定義的過濾功能，這個可以通過 MapReduce程序來提供。
2.3 計算幾何操作
正如上文所述，CG_Hadoop形成了計算幾何操作的全面MapReduce庫的核心部分。目前，CG_Hadoop包括5個基礎的操作，即合并、Skyline、凸多邊形、Farthest pair、和closest pair。下面對他們進行簡單的定義。
合并：對一組多邊形集合S進行合并，就是集合S中至少一個多邊形內部所有點集合，僅僅保留所有點中的邊界點，刪除內部的所有點。圖1（a）給出了一個示例對輸入的多邊形進行合并作為一組壓縮代碼區域,圖1(b)是合并的結果。
Skyline(輪廓):例如圖1中的點集合P。如果點Pi的坐標至少在一個維度（縱坐標或橫坐標）不小于Pj的坐標，那么Pi在點P集合中就主導點Pj。點集合P的輪廓線是有這些主導點構成的（如圖1(d)）。在計算幾何領域，輪廓線通常被稱之為最大點集合[33]。
ConvexHull（凸包）：一個點集合P的凸包是指包含這些點的最小凸多邊形，如圖1(e)所示。凸包操作的輸出就是所有點按照順時針的方向形成凸包（MRB）。
FarthestPair：給定一組點P，最遠組對是所有點對中，兩點之間的歐幾里得距離最大的一對點。如圖1(e)所示，最遠的一對點在凸包上。
ClosestPair：給定一個組點P，最近組對是所有點對中，兩點之間的歐幾里得距離最小的一對點。如圖1(e)所示。
3、合并
傳統算法為多邊形合并操作[33]計算兩個多邊形的合并通過計算所有邊緣交叉，刪除所有內部部分,僅留下周邊的部分。對于兩個以上的多邊形合并，首 先合并兩個多邊形，然后與下一個多邊形合并直到所有的多邊形都合并成一個多邊形。PostGIS[32]中，通過以下SQL查詢語句來執行這個操作，每一 列geom存儲了每一個ZIP代碼的多邊形信息。
SELECT ST_Union(zip_codes.geom)FROM zip_codes;
本節介紹了基于Hadoop和SpatialHadoop的兩個多邊形合并算法。以圖1(a)中的數據集作為輸入。為了便于說明，同時保持代表性，實例中的多邊形不存在重疊現象。
3.1 Hadoop中的合并
Hadoop中多邊形合并算法核心思想是允許每一臺機器累加多邊形的子集，然后讓一臺機器將所有機器的結果都收集起來并計算出最終答案。算法步驟如 下：分區、局部分區和全局分區。第一步分區是將輸入的多邊形分為更小的子集存儲在每一臺機器上。該步驟由Hadoop加載文件命令執行，可以將文件劃分為 64MB大小的組塊存儲在每一個從節點上。第二步是建立局部索引。每一臺機器通過傳統的內存中多邊形合并算法計算該機器上多邊形合并。因為每一個數據塊最 大為64MB，所以內存算法實現跟輸入文件的大小無關。這些步驟作為一個聯合功能再Hadoop中實現，運行在每一臺機器中。當執行完局部合并之后，每一 臺機器會生成一組多邊形作為該機器上分配的所有多邊形的合并結果。全局合并在Hadoop中是以reduce功能來實現的，這個過程是在一臺機器上計算最 終的而結果。Reduce函數取出所有局部計算的合并結果，然后合并成一個，對他們再通過傳統的內存計算算法進行合并。每一臺機器最終將生成只有幾個多邊 形，這樣可以使用內存算法進行多邊形合并。
通過充分利用并行機器的優勢，而不是在一臺機器上完成所有的工作，本文提出的算法與傳統的算法相比具有明顯的優勢。盡管將數據分配到每臺機器上，再 從每一臺機器上搜索結果都會有所開銷，這樣的開銷可以通過并行機器的成本抵消掉，而且也可以用來處理更大尺度的空間數據集。對于更感興趣，而且也比較熟悉 MapReduce編程范式的讀者，附件A.1.給出了基于Hadoop的多邊形合并算法的源代碼。
圖2給出了圖1(a)的輸入數據集通過四個集群計算節點進行分區和局部合并的過程，四個節點每一個多邊形分配到一個節點。決定哪個節點屬于哪個分區完全取決于Hadoop負載文件組件，基本上是隨機分配多邊形到每一個節點上。
通過圖中的結果，可以發現分配到一個節點的多邊形合并后完全保持獨立。在這種情況下，素有的多邊形都作為輸出結果。然后，所有節點的輸出結果將通過一個單獨的機器進行計算得出最終的答案，如圖1(b)所示。
3.2 SpatialHadoop中的合并
SpatialHadoop中多邊形合并算法和Hadoop中的算法具有一樣的三個步驟。唯一不同的地方是在SpatialHadoop中進行數據 集分塊含有一種空間思想的行為，如圖3所示，相鄰的多邊形被分配在了一臺機器上。這主要是因為在SpatialHadoop中利用了潛在的空間索引結構去 為每個節點分配多邊形。尤其是，在SpatialHadoop中采用R-tree索引，每一個R-tree節點的大小為64MB，每一個集群節點存儲每一 個R-tree節點中的所有條目。因此，根據定義，每一個R-tree節點提供一簇相鄰的多邊形，特別是，在SpatialHadoop中所有R- trees批量加載也能夠保證同一個節點上的所有多邊形是相鄰的。
盡管局部和全局合并步驟一樣，但在SpatialHadoop中變的更加簡潔。其局部合并通常生成輸出一個多邊形，而在Hadoop中往往輸出多個 多邊形。在本文的實例中，通過Hadoop的局部合并后生成了28個多邊形，而在SpatialHadoop中僅僅生成了4個多邊形，這就使得最終的算法 計算的更快。SpatialHadoop中多邊形合并算法的源代碼完全和Hadoop中一樣（附件A.1.）。
4、Skyline(輪廓線)
傳統的內存中二維輪廓算法是采用分而治之的思想，首先將所有點按照X坐標進行排序，并通過一條垂直線將所有點分為兩個大小相等的子集。每一半的輪廓 通過遞歸計算，最終的輪廓線通過兩者合并計算得到。合并兩條輪廓線，左邊輪廓線的點按照非遞減X順序進行掃描，也就是按照非遞增Y順序進行掃描，每一個都 和右邊輪廓線最左邊的點進行比較。一旦左邊軌跡線的點占優勢，那么就刪除掉左邊輪廓線上的所有后續點，兩條輪廓線上剩余的點鏈接在一起。在數據庫管理系統 中是不支持輪廓線操作符的。然而，在數據庫中這些主要基于磁盤的算法具有非常大的意義（例如[7, 31]）通過非標準SQL查詢。
SELECT * FROM points SKYLINEOF d1 MAX, d2 MAX;
本節介紹了兩種輪廓線算法，一種基于Hadoop，一種基于SpatialHadoop。以圖1(c)中的數據為輸入數據集。
4.1 Hadoop中的Skyline
本文Hadoop中的skyline算法是傳統分而治之skyline算法的一種演變[33]，是將輸入的數據劃分為多個（多于兩個）部分，每一部 分可以通過一臺機器來處理。通過這樣的方式，輸入的數據通過所有機器需要一次被劃分，確保結果能夠在一次MapReduce迭代過程中得到。類似于 Hadoop多邊形合并算法，Hadoop輪廓線算法分為三步來執行：劃分、局部輪廓線和全局輪廓線。劃分步驟將輸入的數據集劃分為64MB大小的更小組 塊，并將它們分配到每一臺機器上。局部輪廓線步驟是指每一臺機器通過傳統的算法計算本機器上的數據組塊輪廓線，僅輸出非主導地位的點。最終通過全局輪廓線 步驟，一臺機器收集所有局部輪廓線的點，然后計算這些點的最終輪廓線。值得注意的是，不能夠通過內存算法來進行合并這些局部輪廓線，因為局部輪廓線不是通 過一條垂直線進行分開的，實際上他們之間有可能重疊。通過Hadoop劃分數據塊是隨機劃分的，并沒有考慮數據之間的空間位置。全局輪廓線步驟計算最終的 結果，通過傳統的輪廓線算法將局部輪廓線中的所有點合并成一個要素集。熟悉MapReduce編程的用戶可以參考附件A.2的源代碼。
該算法允許多臺機器進行獨立并行運算，大大提高了輪廓線計算效率，同時也減少了輸入要素集（全局計算時）的大小。對于n個點大小的均勻分布的數據 集，大約在輪廓線上的點的數量是O(logn)[4]。在實踐中，一個64MB大小的分區大約有7000000個點，輪廓線中真實的和統一生成數據集僅僅 包含幾十個點。考慮到這些數據量比較小，也適合將所有收集的點再一臺機器上進行單獨的計算得出最終的結果。
4.2 SpatialHadoop中的Skyline
SpatialHadoop中Skyline算法與前面描述的Hadoop算法非常相似，但也有兩個主要的變化。首先是在劃分階段，后者采用了 SpatialHadoop劃分器當數據加載到集群時。這樣確保了會根據一個R-tree索引進行劃分，而并不是隨機劃分的，這就意味著每臺機器上生成的 輪廓線是沒有重復的。其次，在局部輪廓步驟之前采用了額外的過濾步驟。過濾步驟在主節點上執行，需要輸入所有分區的R-tree索引單元的最小外包矩形 (MBRS)，并清除這些單元，但并不會影響最終輪廓線的結果。
新過濾步驟的主要思想是如果在Ci中至少有一個點主導Cj中所有的點，那么Cj可以刪除，單元Ci主導另外一個單元Cj。如圖4所示，由于C5左下 角主導了C1中右上角，則C5主導了C1。輪廓線支配關系的傳遞性意味著在C5中的所有點主導C1中的所有點。同理，C6主導C4，C6的左上角主導了 C4的右上角。這就是說C6上邊緣的點主導了C4左上角的點，因此主導了C4中所有的點。因為一個單元的邊界是最小的（因為R-tree分區），所有每一 個邊界至少有一個P中的點。類似于C2主導了C3。因此在過濾步驟中刪除方法是通過一個嵌套循環一起測試每一對的細胞Ci和Cj。通過對比Cj的右上角和 Ci的左下角、右下角以及左上角。如果任何一個角主導了Cj的右上角，就在下一步對比中刪除Cj，不發給任何一個節點。因此，對局部skyline不進行 計算，也不認為他在全局輪廓線這個步驟中。
值得需要注意的是，在Hadoop中應用過濾步驟不會有多大的影響，因為在Hadoop中使用的分區方案針對不同的單元不會產生如此分割的 MBRs。基于SpatialHadoop輪廓線算法比相應的Hadoop算法具有更好的性能，因為過濾步驟減少了許多不需要處理的單元。感興趣的讀者可 以參考附件A.2過濾步驟的源代碼。
5、凸包（CONVEX HULL）
圖1(e)中所示的凸包采用Andrew’s Monotone Chain算法對兩個鏈進行合并計算。說先，它將所有點按照x坐標進行排序，并標識最左邊和最右邊的點。然后，凸包的上鏈通過檢查每三個連續點 p，q，r，反過來，從左到右。如果三個點是逆時針反向，然后，當中間點q不是上鏈的一部分，它是被跳過的，然后算法將考慮P，r，s三個點，r是成功的 一個點。否則，算法繼續檢查下三個連續的點q，r，s。一旦到達最右邊的點，算法通過同樣的方式繼續計算更低的鏈，來檢查P中所有點，從右到左，并做相同 的檢查。采用PostGIS[32]，凸包，可以通過單獨的SQL語句ST_ConvexHull功能來實現。由于這個函數需要一個記錄作為參數，所以， 這些點必須先通過ST_Makeline功能將其組合成一行字符串。
SELECTST_ConvexHull(ST_Makeline(points.coord)) FROM points;
本節中，介紹了兩種凸包算法，一種是基于Hadoop，一種是基于SpatialHadoop。圖1（c）中的數據集作為案例的實驗輸入數據。
5.1 Hadoop中的凸包
Hadoop中的凸包算法與其中的輪廓線算法非常相似，首先需要進行分區，將輸入的數據劃分為更小的數據塊，每一塊都適合進行內存計算。然后，每一 個子集的局部凸包采用傳統的方法進行內存算法計算[3]，只保留形成凸包的點。這些凸包上的所有點將在一臺單機上進行全局凸包計算，通過傳統的內存凸包算 法生成最終結果。與輪廓線很相似，凸包上點的個數估計為所有的數據的O(logn)[10]，使得在計算局部凸包時，刪除大多數點算法非常高效，并且允許 全局凸包在一個節點上進行計算。
5.2 SpatialHadoop中的凸包
Hadoop中凸包算法沒有必要處理更多文件分區。直觀地說，文件的中心部分不影響結果。SpatialHadoop中，通過提前刪除一些分區從而 提高了凸包算法而且也不影響結果。核心的思想是凸包上的任何點都必須是數據集（大大、小大、大小和小小）的四個輪廓線中的至少一個的一部分[33]。一個 大/小-大/小輪廓線考慮最大/最小點在x-y維是首選。這個屬性允許重用的4.2節中輪廓線過濾步驟。如圖5所示，應用輪廓算法四次去選擇分區，四個輪 廓線所需要的，并將它們素有這些分區作為一個去處理。顯然,一個分區，不影響四個輪廓線的任何一個，也不會影響最終的結果。一旦要處理的分區被選擇后，算 法將通過計算每一個分區的凸包，類似于5.1小節的Hadoop算法，然后在每臺機器上計算局部凸包，再計算全局凸包。SpatialHadoop算法的 獲取來源于空間意識分區方案，這樣允許在過濾步驟中進行數據修剪，因此在局部和全局進行凸包計算時可以節約成本。感興趣的讀者可以查看附件A.3中。
6、最遠組對
最遠組對的很好屬性是這兩個點組成的組對必須落在所有點的凸包上[34]。這個屬性可以通過首次計算凸包加速最遠組對操作，然后通過旋轉卡尺算法掃描凸包來查找最遠組對[33]。在本節中，將介紹Hadoop和SpatialHadoop中最遠組對算法。
6.1 Hadoop中最遠組對算法
本節首先主要討論基于Hadoop的旋轉持卡方法[33]計算凸包算法。然后通過一臺單獨的機器對凸包上所有點進行掃描，這在凸包上所有點的個數上 可能是個瓶頸。在這種情況下，最好是開發一個基于并行處理的最遠組對算法來實現Hadoop算法，這種方法是計算每一個可能的點對中兩點之間的距離，并選 擇其最大值。對于大文件蠻力強迫方法代價較高，然而，如果在旋轉卡方法下不適合一臺機器從凸包的點中去計算最遠組對，這個時候可以使用該方法。總的來說， 蠻力強迫和旋轉卡尺的方法在Hadoop中實現具有各自的缺點。
6.2 SpatialHadoop中最遠組對算法
SpatialHadoop中的算法工作模式與輪廓線和凸包算法類似，也分為四個步驟，即分區、過濾、局部最遠組對和全局最遠組對。在分區階段，主 要采用SptialHadoop分區方案。在過濾步驟中，采用了專門的規則過濾。主要的思想如圖6所示。對于單元中的每一對組對，Ci和Cj，計算他們之 間最小（最大）距離最為pi∈ci和pj∈cj(圖6(a))中任意兩點之間可能最小(最大)的距離。然后，鑒于兩個單元組對C1 =<c1, c2>和 C2 = <c3, c4>，如果C1中的最小距離不小于C2中的最大距離，那么我們就說C1主導C2。在這種情況下，C2的組對將被刪除，因為他的數據集中不包含最遠 的組對。如圖6(b)所示，C1中最遠的組對必須有一個距離大于C2中最遠的組對。在這種情況下，<C3，C4>單元中的組對將不影響最終結 果，因此在下步處理過程中將不予考慮。
一旦所有主導的單元組對都處理完畢后，算法將通過尋找局部凸包為每一個備選的單元組對計算局部最遠組對，然后應用旋轉卡尺算法計算結果[33]。重 要的是要注意，當每一個組對的大小是有界單元大小的兩倍時，通過內存算法計算局部凸包是可行的。最終，算法通過收集所有局部最遠組對并選擇出最遠距離的組 對，計算出全局最遠組對。對于感興趣的讀者，最遠組對算法如附件A.4所示。
7、最近組對
任何數據集中最近組對(圖1（e）)都可以通過分而治之的算法[25]。這種思想是將所有點按照x坐標進行排序，然后基于中位數，將點分為兩個子 集，P1和P2，大小大致相當，在每個子集中通過計算最近組對。基于找出的兩個最近組對，算法將計算P1中的p1所有點的最近組對和P2中的最近組對，他 們之間的距離比兩個已經存在的更小。最終，算法返回三個組對中最優組對。本節介紹基于Hadoop和SpatialHadoop的最近組對算法。
7.1 Hadoop中最近組對算法
在Hadoop中采用以上描述的分而治之的思想是非常珍貴的。首先，它需要整個數據集進行與分類，就其本身而言，它需要兩輪 MapReduce[29]。此外，合并的要求對經過排序的坐標點進行隨機訪問，這在Hadoop文件系統中是一個眾所周知的瓶頸。一方面，采用 Hadoop默認的加載去劃分數據，并在每一個分區中計算局部最近組對（類似于最遠組對算法）可能導致交叉結果。這是因為數據劃分是隨機的，這就以為這在 在不同分區的兩個點可能是最近的組對。最后，在5.1章節提到的最遠組問題，蠻力的方法可以解決，但對于大文件還需要更多的計算。
7.2 SpatialHadoop中最近組對算法
在SpatialHadoop中最近組對算法采用了傳統最近組對分而治之算法[25]。算法分為三個步驟，劃分、局部最近組對和全局最近組對。在劃 分階段，輸入數據集是通過SpatialHadoop加載，如圖7所示將數據劃分為多個單元。每一個分區的大小只有64MB，算法通過傳統分而治之的思想 對每個單元中局部最近組對計算，然后返回兩點形成一個組對。另外，算法也必須返回所有候選點，當加上從鄰近的單元點，通過這些候選點可能產生更近的一對。 從圖7可以看出，假設C1中最近的組對距離為&1，在C1周圍做內部緩沖區，半徑為&1，然后返回緩沖區內所有點作為候選點，其他的點都 可以刪除。值得注意的是，形成最近組對的兩個點然會的比較早，而且不受刪除步驟的影響。例如，每一個單元Ci在單元內部可能具有基于最近組對的不同緩沖區 大小&i。對于計算所有緩沖區來說，盡管所有&中最小值可能是最好的值，但它不能夠使用，因為MapReduce框架強制所有的Map任 務是獨立工作，這就使得框架在調度任務的時候更靈活。最終，在全局最近組對計算步驟中，從所有單元返回的所有點將在一臺機器上進行計算，通過傳統分而治之 算法計算最近組對?p，?q。
為了使得算法正確，單元必須不能夠重復，采用SpatialHadoop劃分方法得到的單元能夠確保。這樣確保了點p被移除，沒有其他任何點更近比 同一單元的距離。否則，如果單元重疊，重疊區域點p可能比其他點離點q更近，因此就會沒有點被刪掉。對于熟悉MapReduce范式的讀者，可以查看附件 A.5源代碼。
8、實驗設計
本節將通過實驗來研究CG_Hadoop的效率和性能。Hadoop和SpatialHadoop均是采用Apache Hadoop1.2.0和java1.6。所有的實驗在擁有25節點的學校內部集群上執行。機器的硬盤大小從50GB到200GB不等，內存是2GB到 8GB不等，處理速度范圍是2.2GHz到3GHz。單臺機器實驗室用2TB的硬盤，16GB的隨機存取存儲器和8核的3.4GHz處理器。
實驗數據分為三類：(1)OSM1：從OpenStreetMap上提取的數據集[30]包含164M的多邊形（如湖泊和公園），總大小為 80GB。(2)OSM2：從OpenStreetMap上提取的數據集包含全球17億個點數據（如路口和興趣點）,總共大小為52GB。 (3)SYNTH：在1M*1M的單元內采用不同分布如均勻、高斯、正相關、負相關和循環等（見圖8）隨機生成的合成數據集。均勻和高斯是模擬許多真實現 實系統應用最廣泛的分布。正相關和負相關是用來計算輪廓線最優的案例。循環數據專門用于最遠組對操作，產生的凸包是非常大，不容易進行計算。最大的數據集 大小有128GB，包含3.8億個點。
本文采用所有執行時間作為主要的性能指標。有時，如果操作運行出現內存溢出，或數據太大導致不同算法之間的差異不容易區別，單機實驗的結果可以不算。對真實數據和合成數據操作的實驗結果分別有8.1和8.2節給出。
8.1 真實數據
本節給出了運行OSM真實數據集處理操作的性能結果。多邊形合并算法的結果通過多邊形來運行，而其他四個操作主要是針對點數據集。
8.1.1 多邊形合并
圖10(a)給出了不同輸入大小的多邊形合并操作處理時間。從OSM1數據集中提取出來的不同大小的數據子集為 250MB，1GB，4GB，10GB。如圖10(a)所示，單機多邊形合并算法沒有規模，而且對于大的數據集迅速出現了內存溢出異常導致失敗。盡管 4GB的數據集適合內存計算，但是該算法采用需要更多的內存的內部數據結構，容易導致程序崩潰。CG_Hadoop算法在集群存儲計算和內存開銷方面擁有 更好懂得負載分布。另外，CG_Hadoop基于SpatialHadoop運行時表現更好，因為空間劃分可以加速局部和全局合并步驟。如3.2章節描 述，空間劃分有利于減小中間數據的大小（如局部合并輸出結果）這也會影響算法的整個性能。
8.1.2 其他操作
圖10(b)展示了對OSM2數據集進行不同操作的結果。結果表明CG_Hadoop擁有優于傳統技術幾個數量級。基于SpatialHadoop 的CG_Hadoop的運行在圖中采用實體柱狀圖標識，但是很難看出，因為它與單機算法相比處理時間非常少。對于輪廓線和凸包操作，當分別在Hadoop 和SpatialHadoop運行CG_Hadoop達到了平均8倍和80倍的加速度。最遠組對首先計算出凸包，然后采用循環旋轉卡尺方法，該方法更適合 凸包大小比較小的情況。這就導致了最遠組對運行時間和凸包運行時間非常相似，因為循環旋轉卡尺算法針對小的凸包需要非常短的時間。之后，本文給出了最遠組 對實驗，對于該方法來說，凸包太大了。最后，針對最近組對，僅給出了基于SpatialHadoop的CG_Hadoop的結果，因為單機算法出現了內存 溢出異常。
8.2 合成數據
本節分別給出了生成數據的每一個操作更多的詳細結果。沒有針對合成數據進行多邊形合并，因為他需要更多先進的生成器，這個超出了本文的范圍。本文展示了四個操作，輪廓線、凸包、最遠組對和最近組對。數據集大小從4GB到128GB，生成的數據分布如圖8所示。
圖9是單機算法和CG_Hadoop進行輪廓線操作的性能圖。單機算法循環讀取輸入點，當物理內存緩沖區滿時，使用的緩沖區的大小將減少。這使得與 算法可以處理任意大小的數據。盡管單機能夠完成實驗，但是省略了一些結果來調整它的規模。當CG_Hadoop以Hadoop標準來部署，由于采用了集群 多臺機器并行計算，獲得的幾個數量級的性能。局部輪廓線步驟在刪除大多數點僅僅留下全局所需的點時非常有效。CG_Hadoop能夠達到兩個數量級的性 能，當部署在SpatialHadoop上時。如此好的性能主要是由于過濾步驟能夠刪除分區而不硬性記過，減少了處理區塊的總個數。
凸包算法的處理時間如圖11所示。凸包算法通過循環讀取輸入點，如果內存緩沖滿，通過凸包算法的一次迭代和僅保留的結果內存使用有限。 CG_Hadoop中凸包算法描述如圖5.1所示，由于凸包通過集群中分布式計算所以必單機算法要快很多。CG_Hadoop在 SpatialHadoop中運行更有效，因為過濾步驟允許使其最小化修剪的分區處理不會影響結果。盡管不是這里顯示的清晰圖，部署在 SpatialHadoop上的CG_Hadoop達到260倍加速比傳統的系統。
8.2.3最遠組對
在CG_Hadoop中通過兩種技術計算最遠組對。第一個是通過循環卡尺算法計算凸包[33]，這是只適用當凸包的大小是有限的。本文采用這項技術 進行單機實驗。第二個方法是6.2節中描述的修改蠻力方法。圖12(1)不同的輸入大小進行比較兩種方法的性能。本文通過生成如圖8(e)中的循環數據集 去獲取最大的凸包。如圖所示，第一個技術更有效，因為他需要圍繞凸包單獨掃描。然而，當凸包非常大數據大小超過主存容量時，將會失敗。另外一方面，修改后 的蠻力的方法在CG_Hadoop中是低效的，因為它需要大量計算點之間的距離選擇最遠距離的組對。然而，它有一個可伸縮性優勢因為它需要相比非常小的內 存占用單機算法。只有當旋轉卡尺使用方法不適用，建議修改后的蠻力。
8.2.4 最近組對
如圖12(b)是不同輸入數據大小的最近組對實驗結果。傳統的單機算法不能擴展到大文件，因為它已經加載整個數據集內存。如實驗所示，當數據量達到 16GB時，傳統算法將失敗。CG_Hadoop由于兩個原因達到了最好的性能。第一個，最近組對計算時通過集群并行算法加快了整個算法。第二，每一臺機 器刪除了計算最近組對許多不再需要考慮的點。如圖所示，CG_Hadoop具有可伸縮性，因為每一臺機器僅僅處理每一個分區，在有限的時間內，需要內存使 用的大小，不會有內存問題。
9、 相關工作
在計算幾何領域使用MapReduce從理論的角度討論了[15]表明模擬MapReduce中Bulk-Synchronous平行(BSP)，并應用他解決了一些計算幾何問題，如凸包等。然而，沒有提供實際的實施，沒有給出如何實現其他不依賴BSP模型的算法。
據我們所知，我們在CG_Hadoop工作是第一個針對不同計算幾何問題提供詳細的MapReduce實現。與此同時，還充分利用了Hadoop的 優勢去支持空間數據。在MapReduce中目前支持空間數據的方法可以分為兩類：(1)解決特定的空間操作和(2)提供一個空間數據框架。
特定的空間操作。現有的這類工作主要集中在Hadoop中的MapReduce上實現特定的空間操作。這些工作 實例主要集中在R-tree建立[8]、空間查詢點[38]、空間查詢軌跡數據[24]、KNN[2,38]、ANN查詢[36]、RNN查詢[2]、空 間鏈接[38]、精確KNN鏈接[23]、和模糊KNN鏈接[37]。
統一的空間操作框架。針對不同的空間操作存在四個相近的系統：（1）Hadoop-GIS[1]是一個空間數據 倉庫系統，主要集中處理醫療數據。（2）Parallel-Secondo[22]是一個并行空間數據庫管理系統，采用Hadoop作為一個分布式任務調 度者，當所有的存儲和空間查詢處理通過運行在集群節點上的空間DBMS實例。（3）MD-HBase[27]擴展了HBase去支持多維索引，允許非常高 效的使用范圍和字段式查詢檢索點。（4）通過格網文件和R-Tree索引擴展Hadoop，提供新的MapReduce組件允許在空間MapReduce 程序中使用這些索引。
本文的工作，CG_Hadoop,基于以上兩個部分。首先，并沒有完全集中在一個特定的空間操作上。而是涵蓋了5個不同和基礎的計算幾何空間操作。 第二，沒有提供一個新的系統。而是提供了一個基于SpatialHadoop的多種計算幾何算法的高效實施，這樣可以利用提供的空間索引得到更高的性能。 總之，CG_Hadoop形成了綜合的MapReduce類庫的核心，來進行計算幾何操作。它的開源特性也使得他能夠成為一個研究載體，供研究者去建立更 多的計算幾何算法，充分發揮MapReduce范式的優勢。
10、 結論
本文介紹了CG_Hadoop；一套可伸縮的和高效的MapReduce算法，對各種基本計算幾何操作，即，多邊形合并、凸包、最遠墜和最近組對。 對于每一種操作，CG_Hadoop具有兩個版本：基于Apache Hadoop系統和基于SpatialHadoop系統。CG_HAdoop中的算法采用了分而治之的方法，利用Hadoop和分布式并行環境 SpatialHadoop，從而比相應的傳統算法達到更好的性能。同時，SpatialHadoop算法明顯優于Hadoop算法，因為他們利用 SpatialHadoop之內空間索引和組件。總的來說，CG_Hadoop形式一個全面的MapReduce計算幾何類庫操作。在一群25臺機器集群 中的，數據達到了128GB，廣泛的實驗結果表明使用Hadoop和SpatialHadoop系統的CG_Hadoop比傳統算法分別達到了29倍和 260倍。