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

?

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

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

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

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

0 引 言

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

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

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

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

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

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

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

1．1 點(diǎn)數(shù)據(jù)存儲(chǔ)

點(diǎn)數(shù)據(jù)的屬性字段采用文本格式存儲(chǔ)，空間字段采用WKT模型中的POINT（X Y）存儲(chǔ)．點(diǎn)的X坐標(biāo)和Y坐標(biāo)之間以空格分隔，具體存儲(chǔ)結(jié)構(gòu)如表1所示．

表1　點(diǎn)數(shù)據(jù)存儲(chǔ)Table 1 The storage of point

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

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

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

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

面數(shù)據(jù)的屬性字段同樣采用文本格式存儲(chǔ)，由于面要素比較復(fù)雜，有包含離散面多邊形的情況，因此統(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））存儲(chǔ)空間字段．MULTIPOLYGON可以表示多個(gè)分離的空間面多邊形，同樣采用點(diǎn)集的形式表示，坐標(biāo)點(diǎn)的X和Y值之間采用空格分隔，坐標(biāo)點(diǎn)之間采用“，”分隔．如果一個(gè)面要素含有多個(gè)離散面多邊形，則屬于同一個(gè)環(huán)的點(diǎn)集采用“（）”與其他點(diǎn)集分隔，離散面多邊形之間也采用“（）”分隔，具體存儲(chǔ)結(jié)構(gòu)如表3所示．

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

2 基于Spark的空間索引構(gòu)建與疊加分析

2．1 基于Spark批量并行構(gòu)建四叉樹索引算法

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

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

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

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

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

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）為例詳細(xì)描述基于Spark的土地利用矢量數(shù)據(jù)空間疊加分析方法的執(zhí)行過程，框圖見圖1．

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

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

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

索引過濾的關(guān)鍵偽代碼如下：

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

Intersect計(jì)算的關(guān)鍵偽代碼如下：

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í)驗(yàn)與分析

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

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

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

圖2　空間Intersect時(shí)間對比圖Fig．2 Time comparison chart of Intersect

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

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

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

4 結(jié) 語

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

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

參考文獻(xiàn)（References）：

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

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

［3］ 朱效民，趙紅超，劉焱，等．矢量地圖疊加分析算法研究［J］．中國圖象圖形學(xué)報(bào)，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］ 王少華，鐘耳順，盧浩，等．基于非均勻多級(jí)網(wǎng)格索引的矢量地圖疊加分析算法［J］．地理與地理信息科學(xué)，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ìn)四叉樹索引的矢量地圖疊加分析算法［J］．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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］ 毛定山．基于計(jì)算幾何的矢量數(shù)據(jù)疊加分析算法研究［D］．濟(jì)南：山東科技大學(xué)，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］ 李喬，鄭嘯．云計(jì)算研究現(xiàn)狀綜述［J］．計(jì)算機(jī)科學(xué)，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)基礎(chǔ)研究．

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

收稿日期：2015－05－06．

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

中圖分類號(hào)：P 208

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008－9497（2016）01－040－05