靳鳳營，張豐，杜震洪＊，劉仁義，李榮亞（1．浙江大學浙江省資源與環(huán)境信息系統(tǒng)重點實驗室，浙江杭州310028；2．浙江大學地理信息科學研究所，浙江杭州310027）

?

基于Spark的土地利用矢量數(shù)據(jù)空間疊加分析方法

靳鳳營1，2，張豐1，2，杜震洪1，2＊，劉仁義1，2，李榮亞1，2
（1．浙江大學浙江省資源與環(huán)境信息系統(tǒng)重點實驗室，浙江杭州310028；2．浙江大學地理信息科學研究所，浙江杭州310027）

摘 要：針對海量土地利用矢量數(shù)據(jù)空間疊加分析的效率問題，提出了基于Spark的土地利用矢量數(shù)據(jù)空間疊加分析方法，通過彈性分布式數(shù)據(jù)集實現(xiàn)索引過濾與疊加計算，為解決空間疊加分析的瓶頸問題做了新的嘗試．實驗結果表明，相較基于Oracle數(shù)據(jù)管理的疊加分析方法，該方法顯著提高了空間疊加分析效率，更適合面向海量土地利用矢量數(shù)據(jù)的疊加分析．

關 鍵 詞：Spark；土地利用；疊加分析；矢量數(shù)據(jù)

0 引 言

土地利用矢量數(shù)據(jù)是土地調查產(chǎn)生的主要成果數(shù)據(jù)，其數(shù)據(jù)量隨著一年一度變更調查工作的開展而逐年增加．以浙江省為例，自第二次全國土地調查以來產(chǎn)生了200G左右的土地利用矢量數(shù)據(jù)，并以每年30G左右的速度增加．空間疊加分析是土地利用現(xiàn)狀系統(tǒng)的重要功能，是在相同空間坐標系下，將2個空間上有重疊的圖層相互套合，并按照一定規(guī)則（如Union，Intersect，Identity等）產(chǎn)生一個新圖層的過程［1］．

關于空間疊加分析，很多學者開展了相關研究．文獻［2］提出了基于GPU的并行MBR過濾算法與多邊形剪裁算法；文獻［3］在現(xiàn)有點面、線面和面面疊加分析算法的基礎上，提出了矢量數(shù)據(jù)疊加分析算法；文獻［4］在均勻網(wǎng)格索引疊加分析算法的基礎上，提出了基于非均勻多級網(wǎng)格索引疊加分析算法，包括索引構建、網(wǎng)格過濾、疊加計算、拓撲構面4個部分；文獻［5］通過引入四叉樹索引，實現(xiàn)了新的基于改進四叉樹的矢量地圖疊加分析雙重循環(huán)算法；文獻［6］提出了基于計算幾何的矢量數(shù)據(jù)疊加分析算法．

這些研究工作大多基于單臺計算機，計算能力有限，無法有效滿足海量土地利用矢量數(shù)據(jù)高效疊加分析的需求．

針對上述難題，本文將云計算［7］技術引入土地利用矢量數(shù)據(jù)管理分析領域，利用云計算技術強大的、可彈性擴展的計算能力［8］開展土地利用矢量數(shù)據(jù)高效空間疊加分析研究．提出了一種基于Spark的土地利用矢量數(shù)據(jù)空間疊加分析方法，包括索引過濾與疊加計算．該方法通過改變數(shù)據(jù)的底層存儲，以WKT模型在HDFS分布式文件系統(tǒng)上存儲土地利用矢量數(shù)據(jù)，并構建四叉樹［9］索引，在疊加分析方法的執(zhí)行過程中過濾掉不需要參與疊加計算的空間對象，以提高計算效率．

第1節(jié)，設計了云環(huán)境下的土地利用矢量數(shù)據(jù)存儲方法；第2節(jié)，基于Spark實現(xiàn)土地利用矢量數(shù)據(jù)四叉樹索引的批量并行構建算法并設計了基于Spark的土地利用矢量數(shù)據(jù)空間疊加分析方法；第3節(jié)，實例測試空間疊加分析方法，并與基于Oracle的系統(tǒng)作了對比，最后對研究內容進行了總結．

1 基于HDFS的矢量數(shù)據(jù)存儲

采用WKT模型在HDFS分布式文件系統(tǒng)上存儲土地利用矢量數(shù)據(jù)．空間要素采用ID字段作為唯一標識符，屬性數(shù)據(jù)以普通文本格式存儲，空間數(shù)據(jù)以WKT格式存儲．本文采用TSV格式，以TAB鍵分隔字段，將空間數(shù)據(jù)與屬性數(shù)據(jù)存儲為一行．

1．1 點數(shù)據(jù)存儲

點數(shù)據(jù)的屬性字段采用文本格式存儲，空間字段采用WKT模型中的POINT（X Y）存儲．點的X坐標和Y坐標之間以空格分隔，具體存儲結構如表1所示．

表1　點數(shù)據(jù)存儲Table 1 The storage of point

1．2 線數(shù)據(jù)存儲

線數(shù)據(jù)的屬性字段存儲同點數(shù)據(jù)，采用文本格式，空間字段的存儲則采用WKT模型中的LINESTRING（X1 Y1，X2 Y2）存儲．整條線由點坐標對的形式組成，坐標X和Y之間以空格分隔，2個點之間以“，”分隔，具體存儲結構如表2所示．

表2　線數(shù)據(jù)存儲Table 2 The storage of polyline

1．3 面數(shù)據(jù)存儲

面數(shù)據(jù)的屬性字段同樣采用文本格式存儲，由于面要素比較復雜，有包含離散面多邊形的情況，因此統(tǒng)一采用WKT模型中的MULTIPOLYGON（（（X1 Y1，X2 Y2，X3 Y3，X1 Y1），（X4 Y4，X5 Y5，X6 Y6，X4 Y4）），（X7 Y7，X8 Y8，X9 Y9，X7 Y7））存儲空間字段．MULTIPOLYGON可以表示多個分離的空間面多邊形，同樣采用點集的形式表示，坐標點的X和Y值之間采用空格分隔，坐標點之間采用“，”分隔．如果一個面要素含有多個離散面多邊形，則屬于同一個環(huán)的點集采用“（）”與其他點集分隔，離散面多邊形之間也采用“（）”分隔，具體存儲結構如表3所示．

表3　面數(shù)據(jù)存儲Table 3 The storage of polygon

2 基于Spark的空間索引構建與疊加分析

2．1 基于Spark批量并行構建四叉樹索引算法

采用Spark技術批量并行構建土地利用矢量數(shù)據(jù)空間索引的方式，以提升空間索引的構建效率．在四叉樹索引中，為了快速檢索空間對象，其節(jié)點存儲的數(shù)據(jù)為原始空間對象的最小邊界矩形．

Spark批量并行構建土地利用矢量數(shù)據(jù)四叉樹索引算法流程如下：

首先循環(huán)遍歷全部行政區(qū)的土地利用矢量數(shù)據(jù)，將每一行政區(qū)的土地利用矢量數(shù)據(jù)圖層作為Spark輸入數(shù)據(jù)源；在Map函數(shù)中讀取空間對象數(shù)據(jù)并轉換為Geometry，獲取Geometry的最小邊界矩形；在Reduce函數(shù)中將空間對象的BSM及最小邊界矩形插入四叉樹并序列化到HDFS，其中每一土地利用矢量數(shù)據(jù)圖層對應一個四叉樹索引文件．

Spark在運行階段將土地利用矢量數(shù)據(jù)讀入內存，以RDD（彈性分布式數(shù)據(jù)集）的形式存儲，并通過MapReduce并行計算框架，實現(xiàn)空間索引的并行構建，加快了空間索引的構建速度．

Spark批量并行構建土地利用矢量數(shù)據(jù)四叉樹索引的關鍵偽代碼如下：

Map階段：

Input：〈土地利用矢量數(shù)據(jù)〉

Output：〈FileIndex〈BSM，minX，minY，maxX，maxY〉〉

begin

Geometry Geom＝GeometryFromWkt（）；

Envelope Env＝new Envelope（）；

Env＝Geom．QueryEnvelope（）；

Context．write（FileIndex，BSM，env．minX，env．minY，env．maxX，env．maxY）；

end；

Reduce階段：

Input：〈FileIndex〈BSM，minX，minY，maxX，

maxY〉〉

Output：〈FileQuadTree〉

begin

QuadTree Quadtree＝new QuadTree（）；

f

or（Text val：values）

｛

String［］arr＝val．toString（）．split（“，”）；

Quadtree．insert（arr［0］．toInt（），new Envelope（arr ［1］．todouble（），arr［2］．todouble（），arr［3］．todouble（），arr ［4］．todouble（）））；

｝

end for

SaveQuadTree（Quadtree）；end；

2．2 基于Spark的空間疊加分析方法

下文將以土地利用矢量數(shù)據(jù)的空間相交（Intersect）為例詳細描述基于Spark的土地利用矢量數(shù)據(jù)空間疊加分析方法的執(zhí)行過程，框圖見圖1．

基于Spark的土地利用矢量數(shù)據(jù)Intersect運算過程包括索引過濾與Intersect計算．

圖1　基于Spark的矢量數(shù)據(jù)空間疊加分析Fig．1 Vector data spatial overlay analysis based on Spark

索引過濾：首先循環(huán)讀取輸入數(shù)據(jù)源InputData1和InputData2下的文件夾，將每一相應文件夾下的地類圖斑數(shù)據(jù)以及InputData2地類圖斑數(shù)據(jù)的四叉樹索引文件分別讀入RDD中，然后調用flatMapToPair函數(shù)處理InputData1，遍歷Input－Data1地類圖斑數(shù)據(jù)并與InputData2地類圖斑數(shù)據(jù)的四叉樹索引相比較．對于每一條InputData1地類圖斑數(shù)據(jù)，從InputData2地類圖斑數(shù)據(jù)的四叉樹索引中取出與其相交的InputData2數(shù)據(jù)的BSM，并對兩者做Join操作，其結果為多條InputData2數(shù)據(jù)的BSM與每一條InputData1的數(shù)據(jù)連接．對于InputData2的地類圖斑數(shù)據(jù)則進行mapToPair操作，獲取其BSM與空間列．將Map處理后的InputData1與InputData2地類圖斑數(shù)據(jù)的RDD做Join操作，其結果為多條InputData2數(shù)據(jù)與每一條Input－Data1數(shù)據(jù)連接．

索引過濾的關鍵偽代碼如下：

Input：〈InputData1，InputData2，IndexData2〉

Output：〈RddJoin〈BSM，Geom1，Geom2〉〉

begin

RDD Rdd1＝Featureclass1．flatMapToPair（｛

QuadTree Quadtree＝ReadQuadtree（FileQuad）；

QuadIterator Quaditer＝Quadtree．Iterator（）；

QuadTreeQuery（）；｝）；

RDD Rdd2＝Featureclass2．mapToPair（）；

RDD RddJoin＝Rdd1．join（Rdd2）；

end；

Intersect計算：對索引過濾后的RDD做Map操作，在Map階段，將結果中的空間列取出并轉換成Geometry，然后對其做Intersect操作．由于空間索引存儲的是圖形的最小邊界矩形，進行Intersect操作存在2個圖形不相交的情況，因此對于不相交的圖形，將其返回結果設為“null”，并在做完Map操作后統(tǒng)一處理．最后，開啟一個新進程執(zhí)行結果數(shù)據(jù)寫入功能，以使當前主進程繼續(xù)執(zhí)行下一個MapReduce操作．

Intersect計算的關鍵偽代碼如下：

Input：〈RddJoin〈BSM，Geom1，Geom2〉〉

Output：〈FileIntersect〉

begin

RDD JoinMap＝Rddjoin．map（｛

Geomerty GeoIntersect＝Intersect（Geom1，Geom2，SpatialReferece）；

If（！GeoIntersect．is Empty（））

Stringutils．join（arr）；

else return“null”；｝）；

RDD JoinFilter＝JoinMap．filter（）；

List Results＝JoinFilter．collect（）；

SpatialIntersectWriteThread Writethread＝new SpatialIntersectWriteThread（Results）；

Writethread．start（）；

end；

3 實驗與分析

采用云計算技術管理土地利用矢量數(shù)據(jù)，設計了基于Spark的土地利用矢量數(shù)據(jù)空間疊加分析方法，并與基于Oracle＋ArcSDE的系統(tǒng)進行了性能對比．本次測試的硬件環(huán)境為：1個主節(jié)點、4個數(shù)據(jù)節(jié)點，每個節(jié)點配置Intel i7 950＠3．07GHz處理器、16G內存、1T硬盤．軟件環(huán)境為：操作系統(tǒng)SUSE Linux Enterprise Server 11SP2（x86＿64），運行環(huán)境Hadoop 2．4．0、Spark 1．0．1．

本次實驗以2個年份土地利用矢量數(shù)據(jù)地類圖斑層的Intersect為例測試圖層疊加分析的性能，實驗數(shù)據(jù)為浙江省2010和2012年多個縣級行政區(qū)土地利用矢量數(shù)據(jù)中的地類圖斑數(shù)據(jù)．

圖2為Spark與Oracle＋ArcSDE的性能對比圖．由圖2可知，Spark的性能明顯優(yōu)于Oracle＋ArcSDE，其所需的時間與數(shù)據(jù)量也呈線性關系，并且消耗時間要遠少于Oracle＋ArcSDE．

圖2　空間Intersect時間對比圖Fig．2 Time comparison chart of Intersect

圖3所示為2個節(jié)點和4個節(jié)點下的土地利用矢量數(shù)據(jù)Intersect對比圖．由圖3可知，Spark在2個節(jié)點上與在4個節(jié)點上運行，所需的時間與數(shù)據(jù)量均線性相關，并且2個節(jié)點的效率與4個節(jié)點的效率呈一定比例關系．

圖3　空間Intersect節(jié)點對比圖Fig．3 Nodes comparison chart of Intersect

通過以上實驗測試，可以得到如下結論：在海量土地利用矢量數(shù)據(jù)疊加分析方面，Spark性能明顯優(yōu)于Oracle＋ArcSDE，并且隨著節(jié)點數(shù)量的增加，Spark性能呈一定比例提高．

4 結 語

將云計算引入土地利用矢量數(shù)據(jù)管理分析領域，嘗試解決現(xiàn)有海量土地利用矢量數(shù)據(jù)疊加分析中效率低的問題．首先，基于HDFS提出了一種矢量數(shù)據(jù)存儲方法，實現(xiàn)了海量土地利用矢量數(shù)據(jù)的分布式存儲；其次，結合Spark技術研究土地利用矢量數(shù)據(jù)空間索引的批量構建算法，提出了基于Spark的土地利用矢量數(shù)據(jù)疊加分析方法，較好地完成了索引過濾和疊加計算，顯著提升了疊加分析效率．對比實驗表明，本文提出的疊加分析方法更適合海量土地利用矢量數(shù)據(jù)．

本文基于四叉樹索引實現(xiàn)空間對象的過濾，但四叉樹在數(shù)據(jù)空間分布不均勻的情況下，存在檢索效率低的問題，下一步筆者將引入R樹索引，以提高索引過濾效率．

參考文獻（References）：

［1］ 陳述彭，魯學軍，周成虎．地理信息系統(tǒng)導論［M］．北京：科學出版社，1999．CHEN Shupeng，LU Xuejun，ZHOU Chenghu．Introduction to Geographic Information Systems［M］．Beijing：Science Press，1999．

［2］ 趙斯思，周成虎．GPU加速的多邊形疊加分析［J］．地理科學進展，2013（1）：114－120．ZHAO Sisi，ZHOU Chenghu．Accelerating polygon overlay analysis by GPU［J］．Progress in Geography，2013（1）：114－120．

［3］ 朱效民，趙紅超，劉焱，等．矢量地圖疊加分析算法研究［J］．中國圖象圖形學報，2010（11）：1696－1706．ZHU Xiaomin，ZHAO Hongchao，LIU Yan，et al． Research on vector map overlay［J］．Journal of Image and Graphics，2010（11）：1696－1706．

［4］ 王少華，鐘耳順，盧浩，等．基于非均勻多級網(wǎng)格索引的矢量地圖疊加分析算法［J］．地理與地理信息科學，2013（3）：17－20，69．WANG Shaohua，ZHONG Ershun，LU Hao，et al．Vector map overlay analysis algorithm based on non－uniform multi－level grid index［J］．Geography and Geo－Information Science，2013（3）：17－20，69．

［5］ 董鵬，李津平，白予琦，等．基于改進四叉樹索引的矢量地圖疊加分析算法［J］．計算機輔助設計與圖形學學報，2004（4）：530－534，609．DONG Peng，LI Jinping，BAI Yuqi，et al．Vector map overlay algorithm based on improved quadtree indexing［J］．Journal of Computer Aided Design ＆Computer Graphics，2004（4）：530－534，609．

［6］ 毛定山．基于計算幾何的矢量數(shù)據(jù)疊加分析算法研究［D］．濟南：山東科技大學，2007．MAO Dingshan．Algorithm Study of Vector Data Overlaying Analysis Based on Computational Geometry［D］．Jinan：Shandong University of Science and Technology，2007．

［7］ HAYES B．Cloud computing［J］．Communications of the ACM，2008（5）：23－25．

［8］ 李喬，鄭嘯．云計算研究現(xiàn)狀綜述［J］．計算機科學，2011（4）：32－37．LI Qiao，ZHENG Xiao．Research survey of cloud computing［J］．Computer Science，2011（4）：32－37．

［9］ FINKEL R A，BENTLY J L．Quad trees a data structure for retrieval on composite keys［J］．Acta Informatica，1974，4（1）：1－9．

Spatial overlay analysis of land use vector data based on Spark

JIN Fengying1，2，ZHANG Feng1，2，DU Zhenhong1，2，LIU Renyi1，2，LI Rongya1，2（1．Zhejiang Provincial Key Lab of GIS，Zhejiang University，Hangzhou 310028，China；2．Department of Geographic Information Science，Zhejiang University，Hangzhou310027，China）

Journal of Zhejiang University（Science Edition），2016，43（1）：040－044

Abstract：To increase the spatial overlay analysis efficiency of massive land use vector data，we proposes a method of land use vector data spatial overlay analysis based on Spark．The method realizes index filtering and overlay calculating of land use vector data by resilient distributed datasets（RDD），which is a basic data structure of Spark．It makes a new attempt to overcome the bottleneck of land use vector data spatial overlay analysis．Comparing with the traditional overlay analysis based on Oracle data management，the approach increases the spatial overlay analysis efficiency significantly，which is more suitable for spatial overlay analysis with massive land use vector data，and can help us to manage and analyse the massive land use vector data．

Key Words：Spark；land use；overlay analysis；vector data

通信作者＊，E－mail：duzhenhong＠zju．edu．cn．

作者簡介：靳鳳營（1990－），男，碩士研究生，主要從事國土資源地理信息系統(tǒng)基礎研究．

基金項目：國家自然科學基金資助項目（41471313，41101356）；浙江省科技攻關計劃項目（2013C33051）；國家海洋公益性行業(yè)科研專項經(jīng)費資助項目（2015418003，201305012）；國家科技基礎工作專項（2012FY112300）；中央高?；A科研業(yè)務費專項（2013QNA3023）．

收稿日期：2015－05－06．

DOI：10．3785／j．issn．1008－9497．2016．01．007

中圖分類號：P 208

文獻標志碼：A

文章編號：1008－9497（2016）01－040－05