一種支持并行處理的矢量數(shù)據(jù)存儲(chǔ)與查詢方法

陳 潔，褚龍現(xiàn)，夏棟梁

（1.銅川職業(yè)技術(shù)學(xué)院 人文科學(xué)系 ，陜西 銅川727031；2.平頂山學(xué)院 軟件學(xué)院，河南 平頂山467000；3.武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢430072）

一種支持并行處理的矢量數(shù)據(jù)存儲(chǔ)與查詢方法

陳 潔1，褚龍現(xiàn)2，3，夏棟梁2

（1.銅川職業(yè)技術(shù)學(xué)院 人文科學(xué)系 ，陜西 銅川727031；2.平頂山學(xué)院 軟件學(xué)院，河南 平頂山467000；3.武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢430072）

為了提高海量空間矢量數(shù)據(jù)的存儲(chǔ)和拓?fù)潢P(guān)系查詢效率，提出一種矢量數(shù)據(jù)的分布式存儲(chǔ)與索引方法。設(shè)計(jì)了基于HBase的空間數(shù)據(jù)存儲(chǔ)模型和索引構(gòu)建方案，采用Spark計(jì)算框架實(shí)現(xiàn)了網(wǎng)格空間索引的并行構(gòu)建算法，利用索引完成了空間拓?fù)潢P(guān)系的分布式查詢。最后在Hadoop集群上統(tǒng)計(jì)了相同數(shù)據(jù)集的拓?fù)浒樵儠r(shí)間，結(jié)果表明提出的并行存儲(chǔ)與查詢方法可行性好，比直接查詢HBase算法快4～5倍。

空間關(guān)系；并行；Spark；HBase；區(qū)域查詢

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

隨著Apache Hadoop[5]的出現(xiàn)，空間數(shù)據(jù)的并行存儲(chǔ)與分布式拓?fù)潢P(guān)系查詢成為可能。目前有關(guān)拓?fù)潢P(guān)系查詢研究大都集中在將海量矢量數(shù)據(jù)存儲(chǔ)在HDFS或HBase數(shù)據(jù)庫中，并構(gòu)建索引實(shí)現(xiàn)空間查詢[6-8]，這些方法重點(diǎn)關(guān)注了數(shù)據(jù)表行鍵的設(shè)計(jì)，且在MapReduce計(jì)算框架下實(shí)現(xiàn)[9]，對(duì)空間索引的并行構(gòu)建優(yōu)化和數(shù)據(jù)過濾查詢研究較少。

文中主要研究矢量數(shù)據(jù)存儲(chǔ)到HBase的數(shù)據(jù)模型和索引結(jié)構(gòu)設(shè)計(jì)，實(shí)現(xiàn)基于Spark的空間網(wǎng)格索引并行構(gòu)建和拓?fù)潢P(guān)系的分布式查詢方法。將矢量數(shù)據(jù)中心點(diǎn)經(jīng)緯度連接作為行鍵，數(shù)據(jù)信息以WKT格式存儲(chǔ)，最后給出拓?fù)浒P(guān)系查詢算法。

1 相關(guān)工作

1.1 HBase

HBase是Hadoop的分布式數(shù)據(jù)庫[10]，采用列式存儲(chǔ)方式來存儲(chǔ)數(shù)據(jù)，這種方式可以排除空元素的保存，節(jié)省存儲(chǔ)空間。從邏輯結(jié)構(gòu)上看，數(shù)據(jù)庫中的數(shù)據(jù)仍然包含行和列，且多個(gè)不同的列構(gòu)成一個(gè)列族，數(shù)據(jù)的唯一性由行鍵來確定，同時(shí)根據(jù)不同時(shí)間一行數(shù)據(jù)可以有多個(gè)不同值。于是，數(shù)據(jù)表中單元格的值由4個(gè)屬性唯一確定：

（行鍵，列族，列名，時(shí)間戳）->單元格值

1.2 Spark

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

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

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

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

2 存儲(chǔ)模型設(shè)計(jì)與索引構(gòu)建

2.1 數(shù)據(jù)模型

1）行鍵設(shè)計(jì)

HBase數(shù)據(jù)表中每一行數(shù)據(jù)根據(jù)時(shí)間戳不同可以有多個(gè)值，但是不同行的確定是通過行鍵標(biāo)識(shí)的。在HBase中只支持行鍵查詢，且數(shù)據(jù)根據(jù)行鍵按字典升序存儲(chǔ)[13]。為了確保行鍵的唯一性，在存儲(chǔ)矢量空間數(shù)據(jù)時(shí)首先計(jì)算矢量數(shù)據(jù)空間中心點(diǎn)經(jīng)緯度，然后使用“@”將經(jīng)緯度坐標(biāo)按字符串連接在一起組成行鍵。其中，經(jīng)度取12位（符號(hào)位1位，整數(shù)3位，小數(shù)8位），緯度取11位（符號(hào)位1位，整數(shù)2位，小數(shù)8位），負(fù)值符號(hào)位為1，正值符號(hào)位為0，整數(shù)不足部分前面補(bǔ)0，小數(shù)不足的后面補(bǔ)0。如中心點(diǎn)坐標(biāo) 為 （98.23125441，-80.54824512）， 則 行 鍵 ，009823125441@180548245120。

2）列族設(shè)計(jì)

矢量數(shù)據(jù)一般包括幾何屬性和非幾何屬性，在HBase數(shù)據(jù)表設(shè)計(jì)時(shí)包含兩個(gè)列族Geo和Attribute分別保存幾何數(shù)據(jù)和非幾何數(shù)據(jù)。其中，Geo包含wkt列，Attribute根據(jù)實(shí)際非幾何屬性個(gè)數(shù)包含不同列。為方便拓?fù)潢P(guān)系判定，幾何數(shù)據(jù)以WKT格式存儲(chǔ)點(diǎn)、線和面，最終設(shè)計(jì)的數(shù)據(jù)表存儲(chǔ)模型如表1所示。

表1 矢量數(shù)據(jù)存儲(chǔ)模型

2.2 索引并行構(gòu)建

為了提高數(shù)據(jù)查詢效率，針對(duì)矢量數(shù)據(jù)構(gòu)建網(wǎng)格索引。構(gòu)建的索引表結(jié)構(gòu)如表2所示。

表2 索引表存儲(chǔ)模型

按照經(jīng)緯度 （1，0.5） 劃分網(wǎng)格， 全球共有360*360個(gè)網(wǎng)格，使用二維數(shù)組Cell[360][360]表示。每個(gè)網(wǎng)格編碼使用i@j表示，其中i和j分別為數(shù)組Cell的下標(biāo)。按照公式（1）可以計(jì)算出空間坐標(biāo)點(diǎn)p（longitude，latitude）所屬的網(wǎng)格的下標(biāo)。

其中，h=1，w=0.5。

索引表使用網(wǎng)格編碼作為行鍵，列rowkeys:ids的值為包含在對(duì)應(yīng)網(wǎng)格中空間對(duì)象行鍵的組合，不同行鍵之間使用逗號(hào)分隔。應(yīng)用Spark并行構(gòu)建方法，構(gòu)建算法的過程如圖2所示。

圖2 Spark并行構(gòu)建索引流程

并行構(gòu)建索引具體步驟：

1）newAPIHadoopRDD讀取HBase中數(shù)據(jù)表，得到RDD[K，V]，其中K為自主編號(hào)，V為行數(shù)據(jù)；

2）map變換，獲取數(shù)據(jù)的行鍵并截取字符串得到矢量數(shù)據(jù)中心點(diǎn)的經(jīng)緯度，計(jì)算得出中心點(diǎn)所屬網(wǎng)格編碼，以網(wǎng)格編碼為Key，以數(shù)據(jù)行鍵為Value，形成mapRDD；

3）reduceByKey變換，以網(wǎng)格索引為Key，以"，"拼接原Value構(gòu)成新的Value，形成reduceRDD；

4）map（convert）變換，convert是向HBase表的變換函數(shù)，形成resultRDD；

5）saveAsHadoopDataset將 resultRDD寫到索引表。

3 拓?fù)潢P(guān)系并行查詢算法

拓?fù)浒P(guān)系并行查詢的基本思想是：首先將輸入的區(qū)域構(gòu)造為空間對(duì)象，接著獲取空間對(duì)象的最小外接矩形MBR，按照公式（2）得到MBR相關(guān)的網(wǎng)格索引編碼集合，然后掃描索引表獲取矢量數(shù)據(jù)的行鍵并進(jìn)一步取出數(shù)據(jù)，最后依次判斷取出wkt數(shù)據(jù)是否包含在輸入?yún)^(qū)域中，若是則為結(jié)果。

其中，CodeMBR是多邊形區(qū)域最小外接矩形相關(guān)的網(wǎng)格編碼集合，MBR兩個(gè)頂點(diǎn)為Min（minx，miny），Max（maxx，maxy），N表示自然數(shù)。

實(shí)現(xiàn)流程如圖3所示。

圖3 拓?fù)浒⑿胁樵兞鞒?/p>

4 實(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，HBase版本為 0.98.6.1，Zookeeper版本為 3.4.6，Spark版本為1.4.1。實(shí)驗(yàn)數(shù)據(jù)為：紐約2013年的出租車運(yùn)營記錄和紐約市行政區(qū)劃[14]。

表3 實(shí)驗(yàn)數(shù)據(jù)集

應(yīng)用Spark計(jì)算框架完成索引的并行構(gòu)建，各個(gè)數(shù)據(jù)集花費(fèi)時(shí)間分別為：D1花費(fèi)180.25s，D2花費(fèi)339.12s，D3花費(fèi)525.54s。

拓?fù)浒瑢?shí)驗(yàn)查詢出租車計(jì)時(shí)開始的坐標(biāo)點(diǎn)在每個(gè)行政區(qū)出現(xiàn)的次數(shù)，使用文獻(xiàn)[7]和本文兩種算法對(duì)如表3所示的3個(gè)數(shù)據(jù)集進(jìn)行拓?fù)浒樵儯ㄙM(fèi)時(shí)間如圖4所示。

圖4 不同區(qū)域查詢運(yùn)行時(shí)間

實(shí)驗(yàn)結(jié)果表明，在HBase中借助空間網(wǎng)格索引和Spark并行處理框架能有效提高空間拓?fù)潢P(guān)系查詢效率。根據(jù)Spark運(yùn)行特點(diǎn)，隨著集群中節(jié)點(diǎn)數(shù)的增加和數(shù)據(jù)量的增大，本文查詢執(zhí)行效率將提高更多。

5 結(jié)束語

文中分析了空間拓?fù)潢P(guān)系查詢特點(diǎn)，提出一種基于HBase的矢量數(shù)據(jù)存儲(chǔ)模型，設(shè)計(jì)了支持并行處理的空間網(wǎng)格索引構(gòu)建算法，應(yīng)用Spark計(jì)算框架實(shí)現(xiàn)了空間拓?fù)潢P(guān)系查詢。實(shí)驗(yàn)驗(yàn)證了本文提出的數(shù)據(jù)存儲(chǔ)索引和分布式拓?fù)洳樵兎椒ǖ挠行裕乱徊綄⒀芯咳绾蝺?yōu)化線、面拓?fù)潢P(guān)系的分布式判定方法。

[1]陳軍，趙仁亮.GIS空間關(guā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 AnalysisofBinaryTopological 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 InternationalSymposium on IntelligenceInformation Processing and Trusted Computing.Piscataway:IEEE，2011:154-156.

[6]WANG L，CHEN B，LIU Y.Distributed storage and index of vector spatial data based on HBase[C]// Proceedings of the 2013 21st International Conference on Geoinformatics.Piscataway:IEEE，2013: 1-5.

[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]辛大欣，屈偉.基于Hadoop的云計(jì)算算法研究[J].電子設(shè)計(jì)工程，2013，21（3）:33-35.

[10]Tom White.Hadoop:The Definitive Guide[M].2nd ed.O’ReillyMedia，Inc，2011.

[11]M.Zaharia，M.Chowdhury，M.J.Franklin，S. Shenker，and I.Stoica.Spark:Cluster Computing with Working Sets[C]//In 2nd USENIX Conference on Hot Topics in Cloud Computing（HotCloud），2010.

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

[13]Zheng kun，Yanli Fu.Research on Vector Spatial Data Storage Schema Based on Hadoop Platform[J]. InternationalJournalofDatabase Theory and Application，2013，6（5）:85-94.

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

A vector data storage and query method supporting parallel compute

CHEN Jie1，CHU Long-xian2，3，XIA Dong-liang2
（1.Department of Humanities，Tongchuan Vocational and Technical College，Tongchuan 727031，China；2.Software School，Pingdingshan University，Pingdingshan 467000，China；3.Computer School，Wuhan University，Wuhan 430072，China）

To improve the storage efficiency of massive spatial vector data and query efficiency of topotaxy relation，a distributed storage and index method of vector data is proposed.A spatial data storage modal and index build method is designed based on HBase.The parallel build algorithm of grid spatial index is realized by using Spark compute framework，and the distributed query of spatial topotaxy relation is then achieved by using the index.The query time consumption of topologically containing based on same data sets on Hadoop cluster is counted，statistic data shows that the proposed method on parallel storage and query is feasible and 4～5 times faster than directly query method of HBase.

spatial relation；parallel；spark；HBase；regional query

TN91

A

1674－6236（2017）10-0031-03

2016-04-13稿件編號(hào)：201604131

河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目（12B520040）；平頂山學(xué)院青年基金項(xiàng)目（PXYQNJJ2016013）

陳 潔（1979—），女，江蘇溧水人，碩士，講師。研究方向：大數(shù)據(jù)，旅游與城市發(fā)展。