“格網索引+MapReduce”策略下的地理國情統計分析研究

林雅萍，杜震洪，張豐，劉仁義

(1. 浙江大學 浙江省資源與環境信息系統重點實驗室， 浙江 杭州 310028； 2. 浙江大學 地理信息科學研究所， 浙江 杭州 310027)

“格網索引+MapReduce”策略下的地理國情統計分析研究

林雅萍1,2，杜震洪1,2，張豐1,2*，劉仁義1,2

(1. 浙江大學 浙江省資源與環境信息系統重點實驗室， 浙江 杭州 310028； 2. 浙江大學 地理信息科學研究所， 浙江 杭州 310027)

地理國情統計分析是深度研究地理國情普查數據的首要前提.針對現有單機集中式數據存儲與處理方式存在耗時長、效率低甚至不支持的問題，設計了“格網索引+MapReduce”策略，基于規則格網設計普查數據文件的分塊組織與分布式存儲方式，研制了格網索引與空間分析相結合的雙層過濾機制，構建基于MapReduce的地理國情并行統計算法.最后，與無索引MapReduce、ArcGIS平臺進行性能對比測試，結果表明：“格網索引+MapReduce”方法的統計效率遠高于ArcGIS平臺，對無索引MapReduce方法亦有明顯的效率優勢，研究擬為地理國情普查數據的高性能、多類型、大批量統計分析提供優選方案.

地理國情統計分析；地理國情普查數據；格網索引；MapReduce

地理國情統計分析是將普查數據轉化為地理國情信息，再提升為國家決策服務的必要手段，有助于深化普查成果的全面應用，發揮普查成果對社會、經濟的推動作用，提升各相關領域、專業的創新能力[1].地理國情統計分析的基本對象是地理國情普查數據，主要包括地表覆蓋分類和重要國情要素兩大類，具有體量龐大、來源多樣、信息豐富、空間精度高、時效性強、應用層面廣等典型的大數據特征.

當前，地理國情統計分析工作的開展主要依靠各類統計分析軟件或應用系統[2-5]，大多采用單機模式獨立完成大規模普查數據的存儲與統計分析.但是，由于單機CPU資源性能有限，在耗費大量存儲空間的情況下，其執行統計分析任務則普遍存在耗時長、效率低下的問題，在數據量過大時甚至會出現宕機的情況.近年來，Hadoop云計算技術的發展逐漸成熟，在空間大數據領域尤其是柵格數據的高效存儲和處理方面已有大量應用[6-8]，但在矢量數據處理方面仍處于探索階段，利用Hadoop進行矢量數據存儲、索引構建、空間查詢、空間分析等探索是目前云GIS領域研究的熱點[9-11].

為改善現有普查數據在單機集中管理和統計分析處理性能上的局限性，有效提高地理國情統計分析效率，本研究基于Hadoop云平臺，提出“格網索引+MapReduce”策略，設計基于HDFS的數據分塊組織方式，并采用粗粒度格網過濾與細粒度空間分析相結合的雙層數據過濾機制，最終應用統計分析的并行算法模型，實現對地理國情統計的大批量、準實時、高效并行化處理，旨在為地理國情普查數據的后續深度研究提供基礎.

1 相關技術

HDFS[12]是Hadoop云計算平臺中的分布式文件系統，具有多副本冗余備份、數據完整性校驗、訪問權限控制、負載均衡等機制.HDFS系統遵循主/從式架構，由1個NameNode和若干DataNode服務器協同組成HDFS集群，數據文件由DataNode負責存儲，由NameNode統一調度.HDFS能夠為超大規模數據提供分布式文件存儲和管理服務.

MapReduce[13]是Hadoop云計算平臺中的分布式計算基本框架，采用“分而治之，大而化小”的思想，通過定義可高度并行的map和reduce函數，基于本地計算原則，將大規模數據的復雜計算任務分發至對應或靠近數據的存儲節點并行執行，由于其“遷移計算”代替“遷移數據”，降低了數據在網絡傳輸過程中對并行處理效率的影響，能夠支持大規模或超大規模數據的大批量高效并行處理.

借助HDFS的高可靠、高可擴的大數據存儲系統，和MapReduce模型的高吞吐、高容錯并行計算框架，能夠為地理國情普查大數據的高效處理提供支撐.但MapReduce訪問HDFS數據的常規方式是面向數據文件的，只能讀取整個數據文件，無法根據所需提取數據文件內的特定要素記錄，導致讀取的數據量增加，尤其是無效數據讀取量較大，數據有效提取性能較低.因此需要設計合適的數據組織和過濾機制才能有效支持地理國情統計分析的并行處理.

2 基于規則格網的地理國情普查數據分塊組織

2.1 地理國情普查數據的統一文本化表達

地理國情普查數據，是地理國情統計分析的基本對象，采用基于Geodatabase模型的矢量數據集形式存儲.而Hadoop MapReduce框架默認采用文本行的訪問方式讀取數據記錄，因此本研究首先對現有基于Geodatabase模型的國普矢量數據進行文本化處理，再采用統一的文本方式表達要素記錄的屬性信息與空間信息，并以文本行描述完整的普查數據要素記錄信息，降低數據的空間復雜度，以提高數據讀取與操作的便捷性.

首先，將一條要素記錄O包含的屬性信息文本O.Attributes按照順序排列，空間信息和拓撲信息O.Geometry則選用OGC(open geospatial consortium)簡單要素模型中的WKT(well-known text)編碼進行文本化，列于屬性文本之后組成文本行，一個文本行包含一個要素記錄的所有信息，最后形成TSV(tab-separated values，用制表符tab分隔值的文件)文本格式的國普數據文件.本文設計的國普數據文本格式為：

基于地理國情統計分析需求，將地表覆蓋分類數據文本化為LCRA.tsv文件，將重要國情要素數據文本化后整合為GNCF.tsv文件.

2.2 基于規則格網的地理國情普查數據文件分塊組織

規則格網是構建空間索引時廣泛使用的一種索引方式，其原理是將數據空間劃分為具有一定間隔的網格，通過網格與數據的包含關系，建立兩者之間的映射，并以網格作為數據之間空間關系的載體[14].為有效提高數據文件的訪問性能，避免過多無效數據讀取帶來的磁盤I/O消耗，本研究基于規則格網索引理念設計了普查數據文件的分塊組織方式.

首先，采用基于數據集要素對象數量的空間網格預估方法[15]確定劃分的網格數量，其算法模型為

(1)

式(1)中，P為劃分網格的數目，‖R‖為數據集R的數據對象基數，‖S‖為數據集S的數據對象基數，M為主存儲器的字節大小，Sizekp則表示平均單個數據對象大小.

其次，根據普查數據全空間范圍(Xmin,Xmax,Ymin,Ymax)，獲取格網單元大小w×l，并對數據空間進行格網劃分，共有((Xmax-Xmin)/w)×((Ymax-Ymin)/l)個網格，根據網格的行列號x和y設置網格的唯一標識編碼xy，并創建對應的物理存儲文件夾xy.根據每個網格的空間范圍，判斷國普數據文件中各要素所屬的網格編碼，將擁有相同編碼的要素文本放進對應編碼命名的文件夾中，如圖1所示.

圖1 地理國情普查數據分塊組織Fig.1 Blocking file structure of geographical condition survey data

國普矢量數據包含點、線、面3種幾何要素.點要素數據只會存儲在一個對應網格編碼命名的文件夾中，將邊界上的點要素劃分至其左側或左上側網格內.因線和面要素在空間中占據一定的區域范圍，通常跨越多個網格.為保留要素的完整性，保證地理國情普查數據的客觀性和權威性，本研究采用冗余存儲策略，將跨越網格單元的多邊形要素數據劃分至其覆蓋的多個網格內，并冗余存儲在網格編碼集合所對應的若干文件夾中.如圖2所示，多邊形LCRA1跨越了格網00，10，01，02，12，也即00，10，01，02，12編碼命名的文件夾中均存儲有此多邊形數據.

圖2 數據冗余存儲機制Fig.2 Mechanism of data redundancy storage

3 “格網索引+MapReduce”策略下的地理國情統計分析

地理國情統計分析，是根據所需的統計單元和統計對象，通過相應的統計指標計算、匯總得到成果的過程.針對單機資源與性能難以有效支撐數據的有效提取和大規模要素統計效率低下甚至無法完成的問題，本研究設計了“格網索引+MapReduce”策略，采用規則格網索引與精確分析相結合的雙層過濾機制，利用規則格網索引實現對普查數據的粗粒度空間過濾，在MapReduce的map任務階段對數據進行精確的空間分析和要素類型過濾，既利用了規則格網索引快速檢索的優勢，又避免了其他無用數據參與統計分析指標的計算.

3.1 基于規則格網索引與精確分析的雙層過濾機制

基于規則格網索引與精確分析的國普數據雙層過濾機制建立在數據分塊組織方式的基礎上.

基于規則格網索引的國普數據粗粒度過濾，根據當前統計單元的空間范圍R及其最小外包矩形(minimum bounding rectangle，MBR)RMBR，獲取rMBR覆蓋的網格集合GLst1，再獲取GLst1中與R存在拓撲相交關系的網格集合GLst，然后根據GLst中每個網格的空間位置Xgmin,Xgmax,Ygmin,Ygmax計算其編碼xy，網格編碼計算公式如式(2)(3)所示.最后，獲取GLst內網格編碼集合，并確定所需數據文件的路徑集合.

(2)

(3)

基于空間分析和要素類型判斷的精確分析機制為利用MapReduce框架讀取文件路徑集合中的各數據文件，通過map函數并行讀取數據文件中的要素記錄O，根據O.Attributes要素屬性過濾無效數據，再通過O.Geometry與R的疊加分析，過濾不相交的要素、提取相交的部分.對冗余存儲的要素采用參考點法[16]來規避重復計算問題，參考點表示如下：

pr=(max(oR.xl,oS.xl),min(oR.yh,oS.yh))，

(4)

式中，pr參考點為O與R重疊區域的左上角邊界點，只有當參考點與當前要素位于同一網格內時，才對要素進行提取.

3.2 基于MapReduce的地理國情統計分析并行化處理

地理國情統計分析處理過程中數據的空間分析處理和基本指標的計算匯總過程可并行化實現.以個數、面積、長度等基本要素指標的統計過程為例，以說明基于MapReduce的地理國情統計分析并行統計算法的基本思想.

將要素分類編碼所屬統計單元要素標識碼組裝為key值，要素各指標值拼裝成規則的字符串作為value值，輸出key-value鍵值對，reduce方法負責對相同單元和相同分類要素的value值集合進行各基本指標值的歸并，最終得到統計分析任務的基本指標結果.下面詳細描述基于MapReduce的地理國情統計分析并行算法的實現機制.

(1) 獲取研究區域范圍R、統計單元RList，利用基于規則格網索引的粗粒度數據過濾方法，向MapReduce框架輸入所需數據文件，啟動MapReduce并行統計任務.

(2) 采用map函數逐行讀取數據文件的要素記錄，基于要素屬性及其空間信息，利用精確分析方法判斷要素是否在研究區域內并屬于統計對象.接著計算參考點，若參考點與該要素位于同一網格，則對要素進行提取和裁切以獲取所需的有效數據，并對有效部分的面積、長度指標進行計算，將其分類編碼和所屬統計單元的標識碼組裝為key值，統計指標數值之間以“,”間隔組成value值，向reduce函數輸出key-value鍵值對.具體算法如下：

算法1地理國情統計Map算法

MapObject

1{

2 if Object.CC is in CCList

3 for eachr∈RList do

4 oG=Object.Geometry;

5 rG=r.Geometry;

6 if oG and rG intersect then

7 RP=reference point of oG and rG;

8 if RP in the grid then

9 p=overlay(oG,rG);

10 area=p.getArea();

11 length=p.getLength();

12 cc=p.getCC();

13 id=Object.ID;

14 index=id +“,”+area+“,”+length;

15 OID=cc+“,”+r.ID;

16 emit (OID, index);

17}

(3) reduce函數并行讀取map函數輸出的鍵值對集合，并按照相同key值進行歸并.對統一key值的value集合，按其拼裝規則進行分解和統計，得到一個分類對象的指標匯總結果，仍以分類編碼和所屬統計單元標識碼組裝為key值，指標統計值之間以“,”間隔組成value值，輸出key-value鍵值對.

算法2地理國情統計Reduce算法

Reduce(OID,list(index))

1{

2Sumarea=0.00;

3Sumlength=0.00;

4Sumcount=0;

5 for each index∈ list(index) do

6 if index.ID not repeat

7 Sumarea= Sumarea+index.area;

8 Sumlength=Sumlength+index.length;

9 Sumcount++;

10 emit (CC,List(Sumarea, Sumlength, Sumcount));

11}

(4) 輸出基本指標的統計結果，得到最終統計數據.

4 實驗過程與分析

研究了 “格網索引+MapReduce”策略下的地理國情統計方法，基于規則格網進行數據分塊組織，設計了粗粒度空間過濾和細粒度空間分析相結合的雙層數據過濾機制，最終通過分布式統計算法模型實現統計分析處理的并行化，擬為大批量、準實時的地理國情統計分析提供優選方案.

對本研究的“格網索引+MapReduce”策略、無索引的MapReduce框架以及傳統ArcGIS平臺的集中統計方式進行性能對比實驗.為此搭建了擁有6個處理節點的分布式集群，軟硬件配置相同，其中1臺為主節點，5臺為子節點，另外選擇一臺與主節點相同配置的單機進行ArcGIS平臺實驗.設備參數如下：

硬件環境： DELL PowerEdge R730 服務器，配有14核2.0 GHz CPU處理器、4×16 G DDR4內存、2×256 G SSD硬盤、3×300 G SAS硬盤和2 G緩存，并集成4 000 Mb網卡.

軟件環境： Suse Linux Enterprise Server 12 SP1(x64)操作系統，JDK版本為1.8.0_11，Hadoop版本為2.7.3.客戶端配置為Intel core i7-6700處理器，配有4核3.4 GHz CPU、8 G內存、1 TB硬盤，ArcGIS版本為10.3.

實驗數據選擇浙江省地理國情普查地表覆蓋分類數據和重要的地理國情要素數據，要素總量約705.6萬和82.2萬.實驗采用25×25規則格網對普查數據進行分塊組織.

圖3 3種策略的性能對比Fig.3 Time comparison of three strategies

圖3為“格網索引+MapReduce”策略、MapReduce框架以及ArcGIS 10.3平臺下，對4種不同體量的地表覆蓋分類數據集進行的基本統計性能對比.從圖3中可以看出，隨著統計范圍的不斷擴大，數據體量不斷增加，基于“格網索引+MapReduce”策略的統計方式較傳統ArcGIS平臺集中處理方式在性能上有較大的提升，較無索引的MapReduce方法也有較明顯的提升.

圖4 節點數與統計性能關系Fig.4 Relationship between number of nodes and performance of statistic

圖4為“格網索引+MapReduce”策略下節點數量對統計性能影響的實驗對比圖，通過測試300萬地表覆蓋分類數據的并行統計效率，得到當節點數量較少時，并行統計處理時間較長，節點數量較多時，耗時較短，并行統計處理性能較高.

5 結 論

針對地理國情普查數據統計分析中集中式存儲與處理方式存在效率低下的問題，提出了“格網索引+MapReduce”策略，利用規則格網對數據進行空間劃分和組織，并進行分布式存儲，設計了結合規則格網索引與精確屬性分析的雙層過濾機制，以保證數據讀取的高效性和有效性，同時設計了地理國情基本指標統計并行處理算法，并與無索引MapReduce分布式處理以及基于ArcGIS 10.3平臺的集中式處理方法進行了對比實驗.結果表明，本文提出的統計算法的效率要高于其他兩種方法.由于本文采用的是冗余存儲方式，一定程度上會增加數據的存儲量和讀取數，對并行處理的性能產生一定程度的影響.格網的大小也會影響數據存儲的冗余量，出現數據傾斜問題，從而影響并行處理效率.后續工作將對格網劃分方式以及冗余存儲策略等的優化進行更深入的研究.

[1] 吳桐，王小華，兀偉. 基于地理國情普查的格網統計分析研究[J].測繪標準化，2016,32(1)： 8-11.

WU T, WANG X H, WU W. Grid statistical research based on national geographical conditions census[J].StandardizationofSurveyingandMapping, 2016, 32(1)： 8-11.

[2] 劉耀林，何力，何青松，等. 地理國情統計分析系統設計與應用[J].地理信息世界， 2015, 22(6)： 56-59.

LIU Y L, HE L, HE Q S,et al. Design and achivement of a statistical analysis system for geographic national conditions surveying and monitoring[J].GeomaticsWorld, 2015, 22(6)： 56-59.

[3] 林富明，李雁楠，劉恒飛. 基于天地圖的地理國情統計分析信息發布服務系統設計[J].測繪與空間地理信息，2014, 37(6)： 23-25.

LIN F M, LI Y N, LIU H F. Design of information publication and service system of national geographical condition statistical and analysis based on Tianditu[J].Geomatics&SpatialInformationTechnology, 2014,37 (6)： 23-25.

[4] 王軍，楊東岳，張梁. 地理國情成果在線發布系統開發與應用研究[J].測繪與空間地理信息，2014, 37(10)： 114-116.

WANG J, YANG D Y, ZHANG L. Geographic conditions the results published online system development and applied research[J].Geomatics&SpatialInformationTechnology, 2014, 37(10)： 114-116.

[5] 肖提榮，吳玉婷，何照攀. 縣域地理國情信息管理及統計分析監測系統的設計與實現——以華寧縣為例[J].測繪通報, 2016(4)： 121-123.

XIAO T R, WU Y T, HE Z P. Design and realization of monitoring system for management and statistical analysis of county geographic condition information： A case study of Huaning county[J].BulletinofSurveyingandMapping, 2016(4)： 121-123.

[6] CAO K.CloudComputingandItsApplicationsinGIS[D]. Worcester: Clark University, 2011.

[7] ASTSATRYAN H, HAYRAPETYAN A, NARISISIAN W, et al. An interoperable web portal for parallel geoprocessing of satellite image vegetation indices[J].EarthScienceInformatics, 2015, 8(2)： 453-460.

[8] LYU Z, HU Y, ZHONG H, et al. Parallel K-means clustering of remote sensing images based on mapreduce[J].LectureNotesinComputerScience, 2010, 6318： 162-170.

[9] ELDAWY A, MOKBEL M. A demonstration of Spatial Hadoop: An efficient mapreduce framework for spatial data[J].ProceedingsoftheVldbEndowment, 2013, 6(12)： 1230-1233.

[10] ELDAWY A, MOKBEL M F. Spatial Hadoop： A MapReduce Framework for spatial data[C]//201531stIEEEInternationalConferenceonDataEngineering(ICDE). Seoul: IEEE Computer Society, 2015： 1352-1363.

[11] AJI A.HighPerformanceSpatialQueryProcessingforLargeScaleSpatialDataWarehousing[D]. Atlanta： Emory University, 2014.

[12] WANG J, LU C, WANG L Z. Concentric layout, a new scientific data layout for matrix data-set in Hadoop file system[J].InternationalJournalofParallelEmergent&DistributedSystems, 2013, 28(5)： 407-433.

[13] DEAN J, GHEMAWAT S. MapReduce： Simplified data processing on large clusters[J].CommunicationsoftheACM, 2008, 51(1)： 107-113.

[14] 余勁松弟，吳升. 面向大數據的地理格網分析操作模型比較[J].地球信息科學學報, 2013, 15(6)： 862-870.

YU J S D, WU S. Research progress of array analytics towards big data[J].JournalofGeo-InformationScience, 2013, 15(6)： 862-870.

[15] PATEL J M, DEWITT D J. Partition based spatial-merge join[J].ACMSigmodRecord, 2001, 25(2)： 259-270.

[16] DITTRICH J P, SEEGER B. Data redundancy and duplicate detection in spatial join processing[J].IEEEComputerSociety, 2000： 535-546.

LIN Yaping1,2，DU Zhenhong1,2，ZHANG Feng1,2，LIU Renyi1,2

(1.ZhejiangProvincialKeyLabofGIS，ZhejiangUniversity，Hangzhou310028，China；2.DepartmentofGeographicInformationScience，ZhejiangUniversity，Hangzhou310027，China)

Researchontheanalysisandstatisticofgeographicalconditionsbasedonthestrategyof“GridIndex+MapReduce”.Journal of Zhejiang University (Science Edition), 2017,44(6): 660-665

The statistic of geographical conditions is the primary premise for the deep excavation and application of geographical data. However, the traditional centralized data storage and processing method based on a single computer are time-consuming, inefficient and even unsupported. This paper creates a strategy called “Grid Index + MapReduce” to solve these problems. Firstly, we design a blocking file organization and distributed storage mode of the census data of geographical situation based on the regular square grid, and then make a double layer filtering method which combines the grid index and the accurate analysis. Lastly, we build a parallel processing algorithm of statistic of the geography conditions based on MapReduce. The test results of performance comparison of the strategy of “Grid Index + MapReduce”, the indexless MapReduce and ArcGIS software show that the method of “Grid Index + MapReduce” is much more efficient than the ArcGIS software, and also has obvious efficiency advantages for the indexless MapReduce method. The study tries to provide an optimal scheme for the high-performance, multi-type and high-volume statistic and analysis method for the data of geographical condition survey.

the statistic and analysis of geographical conditions; the data of geographical condition survey; grid index; MapReduce

2016-12-08.

國家自然科學基金資助項目(41471313,41671391)；國家科技基礎性工作專項(2012FY112300)；國家海洋公益性行業科研專項(201505003)；浙江省科技攻關計劃項目(2015C33021).

林雅萍(1992—)，ORCID: http://orcid.org/0000-0002-9324-7293，女，碩士，主要從事地理國情與云計算相關研究.

*通信作者，ORCID: http://orcid.org/0000-0003-1475-8480，E-mail：zfcarnation@zju.edu.cn.

10.3785/j.issn.1008-9497.2017.06.004

P 208

A

1008-9497(2017)06-660-06