基于Hadoop的空間拓?fù)潢P(guān)系分布式查詢方法研究

褚龍現(xiàn)

摘要：空間對(duì)象的拓?fù)潢P(guān)系查詢是進(jìn)行空間分析的重要基礎(chǔ)，為提高海量規(guī)模的矢量數(shù)據(jù)區(qū)域查詢效率，研究了Hadoop平臺(tái)上的三種分布式查詢方法。以多邊形區(qū)域中的POI查詢?yōu)槟繕?biāo)，分別設(shè)計(jì)了基于MapReduce、HiveQL和Spark的分布式查詢算法。實(shí)驗(yàn)結(jié)果表明，相同條件下基于Spark的并行查詢算法有更高的效率。

關(guān)鍵詞： MapReduce；Hive；Spark；空間關(guān)系；區(qū)域查詢

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）26-0083-03

A Research on Spatial Topotaxy Distributed Query Method Based on Hadoop

CHU Long-xian

（Computer School， Pingdingshan University， Pingdingshan 467000， China）

Abstract： Topotaxy query on spatial objects is essential to spatial analysis. To improve the vector data regional query speed in massive scale， three distributed query methods based on Hadoop platform are studied. To test the POI query speed in polygon region， distributed query algorithms based on Maprduce， HiveQL and Spark are designed respectively. Simulation results show that the parallel query algorithm that based on Spark is more efficient by the same condition.

Key words： MapReduce；Hive；Spark；spatial topotaxy；regional query

1 概述

空間關(guān)系中的空間對(duì)象拓?fù)潢P(guān)系主要表達(dá)了點(diǎn)、線和面等空間對(duì)象的關(guān)聯(lián)、包含和鄰接關(guān)系[1-2]，是空間關(guān)系的重要的組成部分和主要的研究?jī)?nèi)容。在地理信息系統(tǒng)中，拓?fù)潢P(guān)系的判定是最常見(jiàn)和最基礎(chǔ)的操作[3]。從矢量數(shù)據(jù)集中查找與查詢對(duì)象滿足特定拓?fù)潢P(guān)系的要素的過(guò)程，一般就是指空間拓?fù)潢P(guān)系查詢?？臻g數(shù)據(jù)獲取方法和技術(shù)已在不斷地進(jìn)行革新，其中的空間數(shù)據(jù)集也呈現(xiàn)出不斷增大的趨勢(shì)。TB、PB級(jí)大小的矢量數(shù)據(jù)的不斷出現(xiàn)，要求著對(duì)分布式數(shù)據(jù)存儲(chǔ)和查詢的研究，已經(jīng)成為地理信息系統(tǒng)技術(shù)創(chuàng)新中的熱點(diǎn)[4]。

正是因?yàn)锳pache Hadoop[5]的出現(xiàn)，使空間數(shù)據(jù)的并行存儲(chǔ)與分布式拓?fù)潢P(guān)系查詢具有了現(xiàn)實(shí)可能性，分布式文件系統(tǒng)（Hadoop Distributed File System，HDFS）可以方便地存儲(chǔ)海量級(jí)空間數(shù)據(jù)[6]，也支持?jǐn)?shù)據(jù)的并行處理。目前有關(guān)拓?fù)潢P(guān)系查詢研究大都集中在Shapefile矢量數(shù)據(jù)存儲(chǔ)在HBase數(shù)據(jù)庫(kù)中，構(gòu)建索引實(shí)現(xiàn)空間查詢[7，8]，這種查詢方法需要先將數(shù)據(jù)導(dǎo)入HBase，需要設(shè)計(jì)存儲(chǔ)模型和索引結(jié)構(gòu)。

本文主要研究對(duì)直接存儲(chǔ)在HDFS中的空間數(shù)據(jù)并行查詢，在分析拓?fù)潢P(guān)系判定方法和基于Hadoop的分布式查詢技術(shù)的基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了應(yīng)用MapReduce、HiveSQL（借助Arcgis for Hadoop工具）和Spark完成指定區(qū)域POI數(shù)量查詢算法，最后完成實(shí)驗(yàn)對(duì)比三種查詢方法的效率。

2 空間拓?fù)潢P(guān)系

空間拓?fù)潢P(guān)系使用關(guān)聯(lián)、鄰接和包含體現(xiàn)地理空間要素之間的關(guān)系，要素類(lèi)型包括點(diǎn)、線和面。拓?fù)潢P(guān)聯(lián)表達(dá)不同要素之間關(guān)系，拓?fù)溧徑颖磉_(dá)相同要素之間的關(guān)系，拓?fù)浒瑒t表達(dá)不同級(jí)別或不同層次的多邊形實(shí)體之間的關(guān)系[9]。本文主要研究拓?fù)浒P(guān)系查詢的不同算法，其中包含關(guān)系如圖1所示。

圖1 拓?fù)浒P(guān)系

3 分布式查詢技術(shù)

3.1 MapReduce

MapReduce是Hadoop上的用于并行處理大數(shù)據(jù)集的軟件框架[10]，其核心是函數(shù)性編程中的map和reduce函數(shù)。map函數(shù)接收數(shù)據(jù)并將其轉(zhuǎn)換為鍵值對(duì)，輸入數(shù)據(jù)的每一行對(duì)應(yīng)一個(gè)鍵值對(duì)；reduce函數(shù)接收map函數(shù)的結(jié)果，然后根據(jù)鍵進(jìn)行分組、排序等二次處理，得到縮小的鍵值對(duì)[11]。

3.2 HiveQL

Hive是基于Hadoop的一個(gè)數(shù)據(jù)倉(cāng)庫(kù)基礎(chǔ)工具，能夠創(chuàng)建數(shù)據(jù)庫(kù)表的同時(shí)映射到HDFS文件，并能提供類(lèi)似于SQL的簡(jiǎn)單查詢和分析語(yǔ)言HiveQL。HiveQL是查詢的和數(shù)據(jù)處理Hive數(shù)據(jù)集的語(yǔ)言，內(nèi)部會(huì)解析成對(duì)應(yīng)的操作或者M(jìn)apReduce程序進(jìn)行分布式處理。

為了處理GIS數(shù)據(jù)，Esri美國(guó)開(kāi)發(fā)了一套Geometry API[12]，通過(guò)這些API對(duì)存儲(chǔ)在HDFS中的數(shù)據(jù)可以進(jìn)行處理。在Hive中加載相關(guān)工具后，可以使用HiveQL處理簡(jiǎn)單的空間數(shù)據(jù)查詢操作。

3.3 Spark

Spark是一個(gè)可以運(yùn)行在Hadoop上的并行軟件框架，能夠?qū)崿F(xiàn)MapReduce功能的同時(shí)確保中間輸出結(jié)果保存在內(nèi)存中，并行處理過(guò)程不需要重復(fù)I/O操作[13]。Spark進(jìn)行并行處理的根本是彈性分布式數(shù)據(jù)集（Resilient Distributed Dataset，RDD），RDD是分布式內(nèi)存中只讀的分區(qū)集合，有三種方式創(chuàng)建：現(xiàn)有RDD轉(zhuǎn)換而來(lái)、集合轉(zhuǎn)換和讀取文件，且RDD可以相互依賴。

4 拓?fù)潢P(guān)系分布式查詢算法

本文研究的算法主要分布式查詢指定區(qū)域內(nèi)點(diǎn)的數(shù)量，指定區(qū)域以JSON格式存儲(chǔ)多邊形區(qū)域，點(diǎn)要素以CSV格式存儲(chǔ)坐標(biāo)和相關(guān)屬性。

4.1使用MapReduce并行查詢

使用MapReduce實(shí)現(xiàn)并行查詢的思想是：map函數(shù)讀取數(shù)據(jù)判斷是否與指定區(qū)域有拓?fù)浒P(guān)系，若有則以鍵值對(duì)輸出，形如（多邊形區(qū)域名，1）；reduce函數(shù)對(duì)map處理結(jié)果進(jìn)行分組和排序，最終輸出結(jié)果形如（多邊形區(qū)域名，N）。算法步驟如下：

1）在Driver類(lèi)中將包含指定區(qū)域的JSON文件路徑通過(guò)配置參數(shù)傳給Mapper，CSV文件路徑通過(guò)框架傳遞到Mapper；

2）在Mapper端初始化方法中讀取配置參數(shù)傳遞的文件內(nèi)容，生成包含不同區(qū)域的Map集合polygonMap；

3）在map方法中讀取CSV文件內(nèi)容，每讀取一行即判斷是否拓?fù)浒趐olygonMap集合所屬的元素中，若是則執(zhí)行write操作；

4）在Reducer端對(duì)收到鍵值對(duì)數(shù)據(jù)分組排序并輸出結(jié)果。

4.2使用HiveQL并行查詢

圖2 HiveQL實(shí)現(xiàn)并行查詢流程圖

使用HiveQL實(shí)現(xiàn)并行查詢的基本思想是：首先加載Arcgis for Hadoop提供的工具包，接著在hive中創(chuàng)建拓?fù)潢P(guān)系的臨時(shí)函數(shù)，然后創(chuàng)建外部表并分別映射JSON文件和CSV文件，最后通過(guò)SQL語(yǔ)句查詢出結(jié)果。查詢過(guò)程的流程如圖2所示。

其中，HiveQL查詢語(yǔ)句格式為：

SELECT 區(qū)域名稱， count（*） 結(jié)果要素?cái)?shù)量

FROM 區(qū)域表JOIN 要素表

WHERE ST_Contains（區(qū)域表數(shù)據(jù)對(duì)象， ST_Point（要素經(jīng)度，要素緯度））

GROUP BY 區(qū)域名稱

ORDER BY 結(jié)果要素?cái)?shù)量 desc；

4.3使用Spark并行查詢

使用Spark實(shí)行并行查詢的基本思想是：首先讀取多邊形區(qū)域創(chuàng)建數(shù)組polygon，接著讀取要素文件創(chuàng)建RDD；然后map轉(zhuǎn)換并在RDD中判斷每一個(gè)要素是否拓?fù)浒趐olygon中元素中，若是保留鍵值對(duì)，形如（polygon元素名，1）；最后reduceByKey得出結(jié)果。算法步驟如下：

1）讀取JSON文件創(chuàng)建RDD[K]，執(zhí)行map轉(zhuǎn)換得到mapRDD[K，V]，K為區(qū)域名稱，V為WKT格式的多邊形對(duì)象，將RDD轉(zhuǎn)換為數(shù)組polygonArray；

2）讀取CVS文件創(chuàng)建RDD[K]，執(zhí)行map轉(zhuǎn)換得到mapRDD[K，V]，K為要素名稱，V為WKT格式的要素對(duì)象；

3）執(zhí)行map轉(zhuǎn)換，在轉(zhuǎn)換函數(shù)中判斷polygonArray中元素是否拓?fù)浒琺apRDD中V表示的要素，若包含則map結(jié)果為（區(qū)域名稱，1）；

4）執(zhí)行reduceByKey（_+_），得到結(jié)果形如（區(qū)域名稱，N）；

5）執(zhí)行saveAsTextFile保存結(jié)果。

其中關(guān)鍵RDD轉(zhuǎn)換過(guò)程如表1所示。

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

實(shí)驗(yàn)環(huán)境的平臺(tái)搭建為：云平臺(tái)4個(gè)節(jié)點(diǎn)構(gòu)成的Hadoop集群，每臺(tái)機(jī)器2.6GHZ CPU和4GB內(nèi)存，安裝CentOS6.4操作系統(tǒng)，Hadoop版本為2.6.0，MySQL版本為5.6.24，Hive版本為0.13.1。

實(shí)驗(yàn)數(shù)據(jù)為：紐約2013年的出租車(chē)運(yùn)營(yíng)記錄（CSV文件）和紐約市行政區(qū)劃（JSON文件）[14]。

實(shí)驗(yàn)查詢出租車(chē)計(jì)時(shí)開(kāi)始的坐標(biāo)點(diǎn)在每個(gè)行政區(qū)出現(xiàn)的次數(shù)，使用本文三種算法對(duì)如表2所示的四個(gè)數(shù)據(jù)集進(jìn)行拓?fù)浒樵儭?/p>

實(shí)驗(yàn)結(jié)果表明，Spark查詢效率最高，直接MapReduce最低。這是因?yàn)橥ㄟ^(guò)HiveQL進(jìn)行拓?fù)潢P(guān)系查詢時(shí)對(duì)，調(diào)用了Arcgis for Hadoop對(duì)MapReduce進(jìn)行了優(yōu)化，查詢效率高于直接使用MapReduce；而Spark并行處理大大節(jié)省I/O操作時(shí)間，隨著數(shù)據(jù)量的增加查詢效率將越來(lái)越高。

6 結(jié)束語(yǔ)

本文分析了基于Hadoop的并行計(jì)算框架在空間拓?fù)潢P(guān)系查詢中的應(yīng)用方法，分別實(shí)現(xiàn)了MapReduce、HiveQL和Spark算法完成區(qū)域拓?fù)浒鴺?biāo)點(diǎn)查詢，最后實(shí)驗(yàn)驗(yàn)證了本文三種方法的有效性，并提出Spark并行處理效率最高。下一步將如何優(yōu)化空間數(shù)據(jù)存儲(chǔ)模型和構(gòu)建空間索引作為研究方向。

參考文獻(xiàn)：

[1] 陳軍，趙仁亮.GIS空間關(guān)系的基本問(wèn)題與研究進(jìn)展[J].測(cè)繪學(xué)報(bào)，1999，28（2）：95-102.

[2] Eliseo C， Paolino D F. Approximate topological relations[J].International Journal of Approximate reasoning.1997，16（2）：173-204.

[3] Zhan F B. Approximate Analysis of Binary Topological Relations Between Geographic Regions with Indeterminate Boundaries[J].Soft Computing，1998，2（2）：28-34.

[4] 吳華意，劉波，李大軍，等.空間對(duì)象拓?fù)潢P(guān)系研究綜述[J].武漢大學(xué)學(xué)報(bào)信息科學(xué)版，2014，39（11）：1269-1276.

[5] YANG G.The application of MapReduce in the cloud computing[C] // Proceedings of the 2011 2nd International Symposium on Intelligence Information Processing and Trusted Computing. Piscataway：IEEE， 2011：154-156.

[6] WANG Y， WANG S. Research and implementation on spatial data storage and operation based on Hadoop platform. proceedings of the Geoscience and Remote Sensing （IITA-GRS） [C]， 2010 Second IITA International Conference on， F， 2010IEEE.

[7]鄭坤，付艷麗.基于HBase和GeoTools的矢量空間數(shù)據(jù)存儲(chǔ)模型研究[J].計(jì)算機(jī)應(yīng)用與軟件，2015，32（3）：23-26.

[8]丁琛.基于HBase的空間數(shù)據(jù)分布式存儲(chǔ)和并行化查詢算法的研究[D].南京：南京師范大學(xué)，2012.

[9] Maribeth Price. Mastering ArcGIS[M]. McGraw-Hill Education，2015.

[10]Dean J，Ghemawat S. MapReduce：simplified data processing on large clusters[J]. Communications of the ACM，2008，51（1）：107-113.

[11]辛大欣， 屈偉.基于Hadoop的云計(jì)算算法研究[J].電子設(shè)計(jì)工程，2013， 21（3）：33-35.

[12]Arcgis for Hadoop[EB/OL].http：//esri.githup.com.

[13] Zaharia M， Chowdhury M， Franklin M J，et al. Spark： Cluster Computing with Working Sets[C]. In 2nd USENIX Conference on Hot Topics in Cloud Computing （HotCloud）， 2010.

[14] NYC Taxi Trips [EB/OL].http：//www.andresmh.com/.