基于空間填充曲線排列碼劃分的并行緩沖區(qū)算法

申金鑫，吳 燁，陳 犖，景 寧

(國防科技大學(xué) 電子科學(xué)與工程學(xué)院， 湖南 長沙 410073)

0 引 言

進(jìn)入大數(shù)據(jù)時(shí)代，空間數(shù)據(jù)呈現(xiàn)“爆炸式”增長，對現(xiàn)有計(jì)算資源及分析方法造成了巨大挑戰(zhàn)。OSM（OpenStreetMap）全球道路網(wǎng)數(shù)據(jù)已經(jīng)達(dá)到了1億條以上，且在不斷完善更新。因此，傳統(tǒng)分析計(jì)算和架構(gòu)在應(yīng)對這樣日趨海量、日益復(fù)雜的空間數(shù)據(jù)時(shí)已經(jīng)越來越“捉襟見肘”。相較之下，依托日益成熟的并行技術(shù)的高性能計(jì)算方法日益顯露出優(yōu)越性，得到廣泛關(guān)注。

矢量緩沖區(qū)分析確定近鄰度，是GIS空間分析中的一個(gè)重要的基本功能，應(yīng)用廣泛[1]。如計(jì)算通信基站覆蓋范圍、河流水患影響區(qū)域、公共交通服務(wù)保障面積等。

在矢量數(shù)據(jù)緩沖區(qū)生成算法研究方面，很多工作基于平行雙線算法。文獻(xiàn)[2-5]針對平行雙線算法遇到的特定問題進(jìn)行了改進(jìn)。此外，文獻(xiàn)[6-7]分別使用邊約束三角網(wǎng)輔助法和緩沖區(qū)方程近似描述方法提高了緩沖區(qū)生成效率。但是，這些方法大多基于單機(jī)串行進(jìn)行，應(yīng)對更大規(guī)模的海量數(shù)據(jù)時(shí)性能提升有限。

并行計(jì)算方法研究方面。制定并行計(jì)算策略主要考慮數(shù)據(jù)劃分和任務(wù)分解兩方面問題，因而在并行緩沖區(qū)分析應(yīng)用中，計(jì)算流程可以分為數(shù)據(jù)劃分、任務(wù)分解、緩沖區(qū)計(jì)算、緩沖區(qū)合并等流程，且已有一些相關(guān)研究。

文獻(xiàn)[8]主要聚焦數(shù)據(jù)劃分以及空間聚集特性保持，提出了基于圖層和地理空間區(qū)域的任務(wù)分解方法，在網(wǎng)格環(huán)境下實(shí)現(xiàn)了緩沖區(qū)的并行計(jì)算，但容易導(dǎo)致子任務(wù)間粒度差異大。

文獻(xiàn)[9-10]針對并行計(jì)算中任務(wù)劃分和合并的問題，基于MPI提出了基于節(jié)點(diǎn)數(shù)量的任務(wù)劃分和二叉樹任務(wù)合并的優(yōu)化方法。此外，文獻(xiàn)[11]通過裁剪算法將單條數(shù)據(jù)切分成多個(gè)幾何部件，而后進(jìn)行合并得到該對象的緩沖區(qū)范圍。但是，這兩種方法在任務(wù)劃分時(shí)都沒有涉及數(shù)據(jù)空間聚集特性的保持。

文獻(xiàn)[11]著重考慮了數(shù)據(jù)任務(wù)分解過程中的負(fù)載均衡，根據(jù)線面數(shù)據(jù)的復(fù)雜性特點(diǎn)，在集群環(huán)境下，利用MPI和GRASSGIS實(shí)現(xiàn)了等弧段分解任務(wù)，但是在保持空間關(guān)系以及更大規(guī)模數(shù)據(jù)集的執(zhí)行效率等方面還有待驗(yàn)證。

基于此，綜合考慮并行優(yōu)化方法，得到以下研究思路。首先，保持空間數(shù)據(jù)鄰近關(guān)系，在此基礎(chǔ)上進(jìn)行劃分?jǐn)?shù)據(jù)，同時(shí)避免數(shù)據(jù)傾斜問題；然后，合理分解數(shù)據(jù)塊，保持負(fù)載均衡；最后，結(jié)果合并時(shí)，設(shè)計(jì)調(diào)度方法充分利用并行計(jì)算資源。

由于MPI模型多進(jìn)程編程較復(fù)雜，在可擴(kuò)展的并行緩沖區(qū)計(jì)算上存在瓶頸[10]。近年來，MapReduce、Spark等大數(shù)據(jù)處理框架，以其良好可擴(kuò)展性、高效迭代等優(yōu)點(diǎn)提升了數(shù)據(jù)處理效率。雖然這些框架本身不支持對空間數(shù)據(jù)的處理，但在其基礎(chǔ)上，各種空間數(shù)據(jù)處理方法不斷提出并完善。如GeoSpark[12]提供了SRDD，支持kNN和空間連接操作，并且能夠添加網(wǎng)格和R樹索引。此外還有SpatialSpark[13]和Simba[14]等。上述系統(tǒng)支持很多基本的空間操作，但并沒有針對緩沖區(qū)計(jì)算等基本的空間分析功能進(jìn)行設(shè)計(jì)與改進(jìn)。

本文以分布式內(nèi)存計(jì)算框架為基礎(chǔ)，結(jié)合整體計(jì)算流程提出了一種基于空間填充曲線排列碼進(jìn)行數(shù)據(jù)劃分的并行緩沖區(qū)分析算法（SPBM，SFC-based Partition Buffer Method）。本文的主要工作如下：

1）引入空間填充曲線排列碼對空間矢量對象劃分，進(jìn)一步提出了一種基于Hilbert編碼的自適應(yīng)的劃分方法，為了應(yīng)對邊界相交問題，針對線矢量數(shù)據(jù)提出了一種近似切割的空間數(shù)據(jù)劃分策略；

2）在基于數(shù)據(jù)點(diǎn)數(shù)量的任務(wù)分解方法基礎(chǔ)上，采取了設(shè)定深度參數(shù)下的“樹狀”結(jié)果合并方法。

3）在一系列真實(shí)數(shù)據(jù)集上，與多種緩沖區(qū)分析方法進(jìn)行單機(jī)和集群環(huán)境下的對比實(shí)驗(yàn)，驗(yàn)證了本文方法的有效性。

1 問題描述

空間矢量數(shù)據(jù)可以表示為集合D={di|i=1,2,…,N}，其中d表示單個(gè)矢量對象，N表示數(shù)據(jù)集總數(shù)量。集粗粒度下，緩沖區(qū)分析可以表示為描述為Fs(D,r)，如式（1），其中，F(xiàn)s表示串行計(jì)算映射函數(shù)，輸入包括數(shù)據(jù)D和緩沖區(qū)距離r。就屬性而言，可以分為兩個(gè)步驟，單個(gè)對象緩沖區(qū)計(jì)算Fbuffer，和緩沖區(qū)合并Funion。

在并行計(jì)算時(shí)，如式（2），數(shù)據(jù)劃分成了p份，可以描述為Fp(D,r,p)，其中，F(xiàn)p表示并行計(jì)算映射函數(shù)，計(jì)算過程中數(shù)據(jù)被分成了p塊。并行計(jì)算中，顯而易見，F(xiàn)buffer不涉及節(jié)點(diǎn)間通信，但是如何將D分布到c個(gè)計(jì)算節(jié)點(diǎn)上需要考慮以下3個(gè)問題：

問題1：空間數(shù)據(jù)聚集性

數(shù)據(jù)分塊后，D→{Di|i=1,2,…,p}，數(shù)據(jù)塊Di對應(yīng)的緩沖區(qū)計(jì)算結(jié)果Gi空間重疊應(yīng)當(dāng)盡量小，否則后續(xù)Funion開銷很大。因此，需要按照空間屬性來進(jìn)行二維劃分。應(yīng)當(dāng)滿足條件：空間上鄰近的數(shù)據(jù)劃分到相同的Di中。

問題2：切分?jǐn)?shù)據(jù)塊合理性

Di應(yīng)當(dāng)花費(fèi)大致相同計(jì)算時(shí)間，否則會造成阻塞?，F(xiàn)實(shí)情況卻是，實(shí)際矢量數(shù)據(jù)空間分布不均衡，線、面數(shù)據(jù)長度len(d)不一，按照對象數(shù)量的分解方式效果不佳。優(yōu)化方法應(yīng)當(dāng)包含：①數(shù)據(jù)傾斜處理，避免出現(xiàn)單條大數(shù)據(jù)；②負(fù)載均衡考慮，單個(gè)Di的計(jì)算量以及p與c的合理配置。

問題3：結(jié)果合并并行化

Funion合并應(yīng)當(dāng)避免串行方式，否則會“滾雪球”方式不能充分利用資源。

2 基于區(qū)域劃分的并行矢量緩沖區(qū)分析算法

緩沖區(qū)分析算法可以分成數(shù)據(jù)劃分、邊界數(shù)據(jù)處理、任務(wù)分解，以及結(jié)果合并等幾個(gè)步驟，如圖1所示。數(shù)據(jù)讀入后，進(jìn)行空間填充曲線數(shù)據(jù)劃分，得到〈Sc，d〉形式的數(shù)據(jù)，其中，Sc是空間填充曲線編碼值；按照Sc排序，即可體現(xiàn)聚集特性。然后，對跨越網(wǎng)格的數(shù)據(jù)進(jìn)行切分處理，避免出現(xiàn)單條大數(shù)據(jù)。之后，根據(jù)輸入數(shù)據(jù)總數(shù)據(jù)量N對數(shù)據(jù)進(jìn)行分解，得到數(shù)據(jù)量分別為B1,B2,…,Bi（i∈[1,p]）的子任務(wù)D1,D2,…,Di，使得B1,B2,…,Bi基本相等，以避免出現(xiàn)負(fù)載不均衡的問題。最后，進(jìn)行結(jié)果合并，由于串行的方法將導(dǎo)致計(jì)算過程中的等待，本文采用指定歸并樹深度的“樹狀”歸并方法，將每個(gè)Di計(jì)算得到的結(jié)果Gi(i∈[1,p])逐級歸并，最終將結(jié)果輸出。

圖1 基于區(qū)域劃分的并行矢量緩沖區(qū)分析算法框架圖Fig.1 Flow chart of parallel vector buあer analysis algorithm based on region partitionc

2.1 基于空間填充曲線的數(shù)據(jù)劃分

在并行計(jì)算時(shí)，需盡可能保證空間聚類特性，避免將空間相鄰的數(shù)據(jù)分配到不同的計(jì)算節(jié)點(diǎn)上，以此來減少網(wǎng)絡(luò)開銷?？臻g填充曲線在保持空間鄰近特性方面有著無可比擬的優(yōu)點(diǎn)，包含Hilbert曲線、Z-order曲線等，其中Hilbert曲線的空間鄰近性更好[15-16]。本文基于Faloutsos[17]等提出的Hilbert曲線編碼生成算法對空間數(shù)據(jù)進(jìn)行數(shù)據(jù)劃分。按照Hilbert曲線劃分排序后，可以保持空間聚集特性，為后續(xù)任務(wù)分解過程提供組織模式，為緩沖區(qū)合并過程減少了拓?fù)渑袛嚅_銷。文獻(xiàn)[10]表明，基于Hilbert編碼的數(shù)據(jù)劃分方法是其并行緩沖區(qū)優(yōu)化算法尚待繼續(xù)研究的問題。

在選定空間填充曲線的類型SFC基礎(chǔ)上，需要設(shè)定合理的空間曲線層級Li。Li設(shè)定的目標(biāo)是每個(gè)網(wǎng)格內(nèi)的數(shù)據(jù)量差異不會太大，以緩解數(shù)據(jù)傾斜問題帶來的影響。為了針對不同分布特征的數(shù)據(jù)集得到最佳的空間填充曲線層級，本文提出了一種基于空間填充曲線編碼的自適應(yīng)數(shù)據(jù)劃分算法。最終的算法描述如算法1。

算法1．基于空間填充曲線編碼的自適應(yīng)數(shù)據(jù)劃分算法．

輸入：初始輸入空間矢量數(shù)據(jù)，空間填充曲線SFC，初始選定層級Lk，閾值Tsc；

輸出：空間填充曲線層級k．

for (l=k) do

根據(jù)k，按SFC算法生成填充曲線

if (data.type=POINT)

根據(jù)公式（2）計(jì)算Scki

else if (data.type=LINE)

拆分?jǐn)?shù)據(jù)為多個(gè)X&Y坐標(biāo)對Vij(j∈[1,len(Di)])，按公式（2）分別計(jì)算Sckij

end if

對得到的〈Scki,Di〉按不重復(fù)的Scki(i∈[1,m])分為m組

統(tǒng)計(jì)Scki對應(yīng)的數(shù)據(jù)量Ti

if (max(Ti)＞Tsc)

k=k+1

else

輸出結(jié)果

end if

end for

2.2 邊界數(shù)據(jù)切分

在劃分過程中，不可避免地遇到跨越網(wǎng)格的d，為了避免這些數(shù)據(jù)因?yàn)檫z漏而造成結(jié)果錯誤，需要對在網(wǎng)格邊界上的點(diǎn)和線數(shù)據(jù)采取不同的處理方式。當(dāng)前并行分布式計(jì)算方法中，主要有指定網(wǎng)格法和復(fù)制法兩種處理方法[18]。本文對點(diǎn)矢量數(shù)據(jù)采用指定網(wǎng)格方法。然而，實(shí)際線矢量數(shù)據(jù)長度差異明顯，且存在單條長矢量數(shù)據(jù)，跨越多個(gè)網(wǎng)格?；诖?，指定網(wǎng)格法無法避免單條長d造成的數(shù)據(jù)傾斜問題；復(fù)制法既不能解決數(shù)據(jù)傾斜問題，而且會帶來計(jì)算量的增長。即便采取按照網(wǎng)格邊界切分法，這需要考慮到線d與多個(gè)網(wǎng)格的拓?fù)潢P(guān)系，計(jì)算復(fù)雜度大。因此，結(jié)合之前Hilbert編碼網(wǎng)格劃分方式，本文采取一種近似切分方式。

線矢量數(shù)據(jù)近似切分。通過幾何部件劃分合并的方式可以得到單個(gè)對象的緩沖區(qū)范圍[10]，進(jìn)一步，可按照網(wǎng)格在單條線數(shù)據(jù)的節(jié)點(diǎn)處進(jìn)行切分，并為每一條新得到的數(shù)據(jù)計(jì)算其對應(yīng)的編碼值Sc。這樣大的數(shù)據(jù)就分解成了對應(yīng)多個(gè)網(wǎng)格的多條數(shù)據(jù)，從而進(jìn)一步破解計(jì)算瓶頸，得到總數(shù)量為M的新數(shù)據(jù)。算法描述如算法2。設(shè)定一個(gè)不切分?jǐn)?shù)據(jù)的閾值F，在順序計(jì)算各個(gè)節(jié)點(diǎn)Sc時(shí)，從Sc變化的節(jié)點(diǎn)進(jìn)行切割。為了保持最終計(jì)算結(jié)果的正確性，分割節(jié)點(diǎn)既是上一條數(shù)據(jù)的終點(diǎn)，又是下一條數(shù)據(jù)的起點(diǎn)。

算法2．線矢量數(shù)據(jù)近似切分算法．

輸入：輸入空間數(shù)據(jù)di(i∈[1,N])，空間SFC的層級k；

輸出：處理完邊界問題后的〈Sci,di〉(i∈[1,M])數(shù)據(jù)對．

按照k生成SFC

for each di

計(jì)算數(shù)據(jù)長度len(di)

if (len(di)＜F)/* F對一般實(shí)際空間數(shù)據(jù)設(shè)為3即可*/

Sci=OF(Vij|j=[ F/2]), 輸出〈Sci,di〉

else

for Vijin di

if (OF(Vij)!= OF(Vi(j-1)))

在Vij處切割,得到切割數(shù)據(jù)dix/*Vij既是切割數(shù)據(jù)終點(diǎn),又是原數(shù)據(jù)起點(diǎn)*/

Scix=OF(Vi(j-1)), 輸出〈Scix,dix〉/*切分得到的數(shù)據(jù)對應(yīng)一個(gè)SFC編碼值*/

end if

end for

end if

end for

2.3 給定深度“樹狀”結(jié)果合并

空間緩沖區(qū)分析中，最后的步驟就是緩沖區(qū)計(jì)算結(jié)果的合并，先將d的單個(gè)緩沖區(qū)求出，后將其全部合并得到最終結(jié)果。該步驟與2.2節(jié)之間還有任務(wù)分解過程，本文對切分后數(shù)據(jù)按照均勻節(jié)點(diǎn)方法進(jìn)行分解。

并行計(jì)算過程中，F(xiàn)union合并需要考慮相互的空間位置和拓?fù)潢P(guān)系，涉及到大量網(wǎng)絡(luò)傳輸開銷，因而合并任務(wù)的調(diào)度成為一個(gè)性能提升的瓶頸。樹狀合并方法能夠起到優(yōu)化作用，使得計(jì)算復(fù)雜度由O(p)降為了O(logp)。文獻(xiàn)[9-10]中均采取的是二叉樹類似的進(jìn)程合并方式，在2z個(gè)進(jìn)程（z∈[1,5]）的情況下驗(yàn)證了優(yōu)化效果。不同于進(jìn)程合并，本文從數(shù)據(jù)塊樹狀合并的角度出發(fā)，使用了給定深度樹狀緩沖區(qū)合并方法。輸入給定深度參數(shù)h，按照該參數(shù)進(jìn)行近似“樹狀”任務(wù)合并。如圖2所示，首先，D1…D6先計(jì)算出數(shù)據(jù)塊中數(shù)據(jù)的緩沖區(qū)及其合并結(jié)果，得到數(shù)據(jù)塊的緩沖區(qū)計(jì)算結(jié)果集G1…G6。然后，根據(jù)給定的深度h開始樹狀歸并。由于給定深度的合并方法減少了合并過程中的數(shù)據(jù)塊數(shù)量，減少了網(wǎng)絡(luò)傳輸開銷，因而起到了明顯的優(yōu)化效果。

圖2 給定深度“樹狀”結(jié)果合并示例Fig.2 Example of tree-like task combination with given depth

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)置

在本節(jié)中，分別在單機(jī)和集群兩種不同環(huán)境下進(jìn)行了實(shí)驗(yàn)。代碼用Scala語言實(shí)現(xiàn)。實(shí)驗(yàn)基于Spark1.6.1，Hadoop2.6，Java1.8_101；QGIS版本為2.0；PostGIS版本為2.1；CitusData版本為5.2（是對PostGIS的集群擴(kuò)展）。實(shí)驗(yàn)硬件環(huán)境見表1。

表1 實(shí)驗(yàn)環(huán)境Tab.1 Experiment environment

實(shí)驗(yàn)使用了點(diǎn)、線等實(shí)際數(shù)據(jù)，其中線要素最大規(guī)模達(dá)到了60萬量級。數(shù)據(jù)匯總見表2?？紤]更大規(guī)模的數(shù)據(jù)集的計(jì)算結(jié)果十分復(fù)雜，對前端可視化造成巨大壓力，當(dāng)前實(shí)際應(yīng)用效果有限，因而并未進(jìn)行相關(guān)實(shí)驗(yàn)。其中，P1和P2是興趣點(diǎn)數(shù)據(jù)；L1是城市道路數(shù)據(jù)，長度比較均衡；L2是地區(qū)道路數(shù)據(jù)，較L1包含了更多單條長數(shù)據(jù)，由節(jié)點(diǎn)數(shù)量對比也可看出；L3與L2為同一地區(qū)，是該地區(qū)更全面的數(shù)據(jù)集；L4是國家道路網(wǎng)數(shù)據(jù)集。

表2 實(shí)驗(yàn)使用的數(shù)據(jù)集Tab.2 Datasets used in the experiment

3.2 實(shí)驗(yàn)結(jié)果對比分析

實(shí)驗(yàn)1至實(shí)驗(yàn)3驗(yàn)證算法影響因素，并說明本文方法的科學(xué)性，在單機(jī)中進(jìn)行；實(shí)驗(yàn)4是算法對比實(shí)驗(yàn)，分別在單機(jī)和集群環(huán)境中進(jìn)行，以驗(yàn)證SPBM的高效性和可擴(kuò)展性。所有實(shí)驗(yàn)中，緩沖區(qū)距離r設(shè)置為200 m。

實(shí)驗(yàn)1 網(wǎng)格劃分方式對比實(shí)驗(yàn)

為驗(yàn)證空間填充曲線劃分方法帶來的性能提升，對無劃分方法（No Partition，NP）、普通網(wǎng)格的劃分方法（Grid Partition，GP）、Z曲線編碼網(wǎng)格劃分方法（Z-curve Partition，ZP）以及本文采取的Hilbert曲線編碼網(wǎng)格劃分方法（Hilbert-curve Partition，HP）等4種方法進(jìn)行了對比，其中，NP、GP以及HP方法采用相同的網(wǎng)格生成方法。為了隔離數(shù)據(jù)切分等優(yōu)化措施的影響，因而沒有采用線矢量數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，而是基于點(diǎn)矢量數(shù)據(jù)集P1和P2。由表3可知，3種網(wǎng)格劃分方法相較于NP都實(shí)現(xiàn)了很高的加速比。就GP、ZP和HP而言，HP方法因?yàn)榭臻g鄰近性更好而效率略高。在P2數(shù)據(jù)集上，由于數(shù)據(jù)密集帶來數(shù)據(jù)塊內(nèi)實(shí)際計(jì)算量增長，因而3種方法加速比下降。

表3 數(shù)據(jù)劃分方法對比實(shí)驗(yàn)結(jié)果Tab.3 Experiments on data partition methods.

為驗(yàn)證自適應(yīng)空間填充曲線層級設(shè)定的必要性，在P2數(shù)據(jù)集上進(jìn)行空間填充曲線層級影響實(shí)驗(yàn)。見表4，3種方法都受曲線層級的影響，趨勢大致相同，隨曲線層級增加，計(jì)算效率先顯著增加，然后稍微下降。當(dāng)層級過低，單個(gè)網(wǎng)格中的數(shù)據(jù)量過多，劃分不能起到相應(yīng)的效果，曲線層級L=11和L=12的實(shí)驗(yàn)結(jié)果相比，單個(gè)網(wǎng)格中最大數(shù)據(jù)量顯著降低，因而更好的空間聚集特性使得平均加速比達(dá)到了6.21。當(dāng)層級過高，劃分過密，反而增大了計(jì)算量，不會起到性能提升作用。

表4 曲線層級對實(shí)驗(yàn)結(jié)果影響Tab.4 Experiments on diあerent layers of SFC curve

實(shí)驗(yàn)2 跨網(wǎng)格數(shù)據(jù)處理方法對比實(shí)驗(yàn)

本實(shí)驗(yàn)對無網(wǎng)格劃分法（No Partition，NP）、指定網(wǎng)格法（Selected Copy，SC）、以及本文采用的近似切分法（Approximate Split，AS）3種方法進(jìn)行比較。由于復(fù)制法相較于指定網(wǎng)格方法而言復(fù)雜度更高，因此未參與比較。

實(shí)驗(yàn)結(jié)果見表5。在較小數(shù)據(jù)集L1測試時(shí)，SC和AS較NP處理效率高。但是由于城市道路網(wǎng)數(shù)據(jù)長度比較均衡，因而SC和AS間差距并不明顯。當(dāng)處理包含更多單條長數(shù)據(jù)的L2時(shí)，AS帶來的性能提升十分明顯，較SC實(shí)現(xiàn)了12.2的加速比。由于SC已經(jīng)按照其中間的節(jié)點(diǎn)得到了編碼值SC，因而相較于NP實(shí)現(xiàn)了明顯的計(jì)算效率提升。但當(dāng)處理更大的數(shù)據(jù)集L3時(shí)，NP和SC超過3個(gè)小時(shí)沒能返回結(jié)果，而AS依然能以較快的效率完成計(jì)算。

表5 跨越網(wǎng)格數(shù)據(jù)處理方法對比實(shí)驗(yàn)結(jié)果Tab.5 Experiments on cross-grid data processing methods

實(shí)驗(yàn)3 樹狀合并方法對比實(shí)驗(yàn)

對順序合并方法（Sequential Merge，SM）、二叉樹合并方法（Binary Tree-like Merge，BTM），以及本文采用的給定深度樹狀合并方法（Depth-given Tree-like Merge，DTM）3種方法進(jìn)行對比，結(jié)果見表6。顯而易見，兩種樹狀合并方法均較順序合并方法優(yōu)越。當(dāng)數(shù)據(jù)量增加時(shí)，加速比更加明顯，BTM和DTM相較于SM在L3數(shù)據(jù)集上分別實(shí)現(xiàn)了4.2和5.4的加速比。這是由于數(shù)據(jù)量的增加，而BTM合并過程中的處理效率卻未提升，更加凸顯了順序合并方法的瓶頸。此外，DTM較BTM好，利用較DTM中小的深度h實(shí)現(xiàn)了更高的計(jì)算效率。這是由于深度增減小后，計(jì)算中間結(jié)果的等待時(shí)間以及網(wǎng)絡(luò)開銷也均減少了，在計(jì)算效率和計(jì)算資源間達(dá)到了較好的平衡。同時(shí)，除Funion操作外，3種方法的開銷時(shí)間基本相等。

表6 樹狀合并方法對比實(shí)驗(yàn)結(jié)果Tab.6 Experiments on tree-like merge methods

但是h設(shè)置需要綜合考慮數(shù)據(jù)總量以及數(shù)據(jù)分塊數(shù)量p。為了驗(yàn)證給定深度樹狀合并方法中h與數(shù)據(jù)集以及數(shù)據(jù)集分塊數(shù)量p之間的關(guān)系，相關(guān)實(shí)驗(yàn)結(jié)果見表7和表8，實(shí)驗(yàn)中c=32。表7得出，3個(gè)數(shù)據(jù)集在同等分塊（分塊足夠大）情況下，最優(yōu)的h均接近log2p-2，即p固定時(shí)，對于相同大小的數(shù)據(jù)集，h的最優(yōu)深度大致相同。類似的，根據(jù)表8，當(dāng)p變化時(shí)，最優(yōu)h隨著p的變化而變化。一步說明本文數(shù)據(jù)劃分方法的效果；實(shí)驗(yàn)1的結(jié)果已經(jīng)說明空間填充曲線帶來的明顯性能提升，這樣做方便對其他方法的優(yōu)化效果進(jìn)行說明。SPBM優(yōu)化前的方法為Algorithm3。由于線矢量數(shù)據(jù)更復(fù)雜、具有代表性，且Algorithm1原文中采用線矢量數(shù)據(jù)測試，因此，本文比較實(shí)驗(yàn)均基于線矢量數(shù)據(jù)進(jìn)行。

表7 固定p=256，不同數(shù)據(jù)集時(shí)深度參數(shù)h影響Tab.7 Fixed p=256, depth h impacted on the experiments on various data

表8 固定數(shù)據(jù)集L2，不同p時(shí)深度參數(shù)h影響Tab.8 Fixed data=L2, depth h impacted on the experiments on vary p

在單機(jī)環(huán)境中，實(shí)驗(yàn)結(jié)果如圖3所示，對于等待3個(gè)小時(shí)沒能返回結(jié)果的情況不予列出。SPBM在4個(gè)數(shù)據(jù)集上的計(jì)算效率均最高，且優(yōu)化效果隨著數(shù)據(jù)量增加而更加明顯。處理L1時(shí)，SPBM與Algorithm1、Algorithm2差異較小。但處理分布不均衡、存在很多單條大數(shù)據(jù)的L2時(shí)，SPBM的優(yōu)越性立馬體現(xiàn)出來。當(dāng)應(yīng)對更加密集的L3時(shí)，SPBM和Algorithm1較Algorithm2的優(yōu)勢進(jìn)一步擴(kuò)大，因?yàn)榍皟煞N方法采取了二叉樹狀合并，而后者的順序合并方法的瓶頸隨著數(shù)據(jù)量增加而愈加凸顯。由于沒有采取優(yōu)化措施，Algorithm3的缺點(diǎn)很明顯，在4個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)處理效率都不高。PostGIS是基于數(shù)據(jù)庫的方法，其中也采取了樹狀合并方法，性能比較穩(wěn)定且能夠應(yīng)對較大的數(shù)據(jù)集，優(yōu)勢隨著數(shù)據(jù)量增加而增加，在L3和L4上的計(jì)算效率超過了Algorithm2。實(shí)驗(yàn)結(jié)果也表明，相較之下QGIS的處理效率僅比Algorithm3稍好。

實(shí)驗(yàn)4 算法比較實(shí)驗(yàn)

在單機(jī)計(jì)算環(huán)境和集群環(huán)境下都進(jìn)行了比較分析。SPBM是本文提出的方法。Algorithm1基于文獻(xiàn)[9-10]中均采取的按節(jié)點(diǎn)數(shù)量的任務(wù)劃分和兩兩樹狀合并方式這兩種優(yōu)化措施；Algorithm2基于文獻(xiàn)[11]中采取的等弧段的任務(wù)劃分方式。這兩種方法只是部分優(yōu)化措施的使用，和原文有一定區(qū)別，既因?yàn)閷?shí)現(xiàn)平臺，又因?yàn)閿?shù)據(jù)不同且原文獻(xiàn)中沒有對緩沖區(qū)計(jì)算距離進(jìn)行說明。此外，Algorithm1和2均采取了本文提出的空間填充曲線編碼的劃分方法，有以下兩點(diǎn)原因，Algorithm2原文中未在超過1萬條的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，而在本實(shí)驗(yàn)中，將要應(yīng)對20萬條以上的數(shù)據(jù)集，這樣改進(jìn)也能進(jìn)

圖3 單機(jī)環(huán)境中算法性能比較Fig.3 Algorithm comparison in standalone environment

在集群環(huán)境中，與Algorithm1、Algorithm2、Algorithm3以及CitusData進(jìn)行了比較。實(shí)驗(yàn)結(jié)果如圖4所示，與單機(jī)環(huán)境中比較類似。其中CitusData采用先在從節(jié)點(diǎn)計(jì)算，再統(tǒng)一到主節(jié)點(diǎn)上合并的方法。由于任務(wù)分解以及分布式計(jì)算等帶來的優(yōu)化，CitusData在L2和L3上的性能較Algorithm2好；但是應(yīng)對L4時(shí)，由于子任務(wù)結(jié)果的結(jié)構(gòu)十分復(fù)雜，合并時(shí)效率受到影響，并未能計(jì)算出結(jié)果。綜合看來，SPBM的效率較其他Algorithm提升了50%以上。

圖4 集群環(huán)境中算法性能比較Fig.4 Algorithm comparison in cluster environment

4 結(jié)束語

在大規(guī)模數(shù)據(jù)緩沖區(qū)計(jì)算過程中，本文采取一種基于空間填充曲線排列碼進(jìn)行區(qū)域劃分的緩沖區(qū)分析并行算法（SPBM），在Hilbert空間填充曲線排列碼的基礎(chǔ)上實(shí)現(xiàn)了自適應(yīng)數(shù)據(jù)劃分；對造成數(shù)據(jù)傾斜的單條大數(shù)據(jù)進(jìn)行近似切分處理；此外，以負(fù)載均衡為目標(biāo)進(jìn)行任務(wù)分解；并通過給定深度的“樹狀”歸并方法最大化緩沖區(qū)計(jì)算效率。通過實(shí)驗(yàn)可以證明本方法的科學(xué)性和高效性。

空間緩沖區(qū)分析涉及大量拓?fù)潢P(guān)系判斷和迭代計(jì)算，通過實(shí)驗(yàn)比較確定了本文的優(yōu)化方法的可行性，也為其他空間分析方法提供了一種參考。由于空間緩沖區(qū)計(jì)算涉及點(diǎn)、線、面等多種數(shù)據(jù)類型，面數(shù)據(jù)的結(jié)構(gòu)更為復(fù)雜，針對空間面矢量數(shù)據(jù)的優(yōu)化方法是下一步的研究方向。