何首武，蔣林利，李曉英，3

（1.桂林理工大學(xué)南寧分校，廣西南寧　530001；2.廣西科技師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，廣西來(lái)賓　546199；3.武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢　430072）

?

基于HBase的位置數(shù)據(jù)區(qū)域查詢研究

何首武1，蔣林利2，李曉英1，3

（1.桂林理工大學(xué)南寧分校，廣西南寧530001；2.廣西科技師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，廣西來(lái)賓546199；3.武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢430072）

摘要：隨著位置服務(wù)的廣泛應(yīng)用，如何對(duì)海量位置數(shù)據(jù)進(jìn)行高效的空間查詢成為研究熱點(diǎn).結(jié)合對(duì)分布式數(shù)據(jù)庫(kù)HBase存儲(chǔ)機(jī)制與Geohash編碼原理的研究，基于GeoHash構(gòu)建空間索引，設(shè)計(jì)位置數(shù)據(jù)存儲(chǔ)模型，并在此基礎(chǔ)上探討一種多邊形區(qū)域查詢算法.通過(guò)與傳統(tǒng)MySQL數(shù)據(jù)庫(kù)的試驗(yàn)對(duì)比，驗(yàn)證了該算法具有較高的查詢效率和良好的可擴(kuò)展性.

關(guān)鍵詞：位置數(shù)據(jù)；HBase；GeoHash；區(qū)域查詢

0　引言

面對(duì)海量的空間數(shù)據(jù)，如何對(duì)其進(jìn)行高效存儲(chǔ)、管理與發(fā)布，已成為一個(gè)迫切需要解決的問(wèn)題［1］.將NoSQL數(shù)據(jù)庫(kù)應(yīng)用于GIS是解決大規(guī)?？臻g數(shù)據(jù)存儲(chǔ)與管理的有效手段［2］.HBase作為Apache Hadoop中的一個(gè)子項(xiàng)目，已在海量空間數(shù)據(jù)的管理中得到廣泛應(yīng)用，如何在HBase數(shù)據(jù)庫(kù)中實(shí)現(xiàn)高效的空間查詢成為了研究熱點(diǎn).

傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)通常使用基于樹的索引（如R樹、四叉樹等）實(shí)現(xiàn)空間查詢［3］，以此類索引處理海量空間數(shù)據(jù)效率較低.基于行健的HBase數(shù)據(jù)庫(kù)難以支持傳統(tǒng)的多維空間索引，因此需要對(duì)空間數(shù)據(jù)進(jìn)行降維處理，以映射到一維空間進(jìn)行索引和查詢.文獻(xiàn)［4，5］采用Hilbert曲線降維法，利用數(shù)學(xué)模型將多維坐標(biāo)降維為字符串，以便HBase存儲(chǔ)和處理，并且能夠最大限度地保證空間對(duì)象之間的邏輯相關(guān)性；其缺點(diǎn)是降維過(guò)程中運(yùn)算量比較大.

Geohash［6］是一種地理編碼，它可以把二維的經(jīng)緯度坐標(biāo)編碼成一維的字符串，已被廣泛應(yīng)用于需要使用一維索引處理空間數(shù)據(jù)的情況［7］，但對(duì)Geohash在區(qū)域查詢的應(yīng)用探討較少.文獻(xiàn)［8］探討了基于Geohash的面數(shù)據(jù)區(qū)域查詢，但其主要是基于關(guān)系數(shù)據(jù)庫(kù)MySQL實(shí)現(xiàn).

本文依據(jù)HBase數(shù)據(jù)模型及位置數(shù)據(jù)的特征，基于GeoHash構(gòu)建空間索引，并在此基礎(chǔ)上探討了一種多邊形區(qū)域查詢算法，為海量位置數(shù)據(jù)的存儲(chǔ)與處理提供一種有效的解決方案和思路.

1　Geohash概述

Geohash編碼是一種經(jīng)緯度地理編碼系統(tǒng)，能夠?qū)⒔?jīng)度信息和緯度信息進(jìn)行轉(zhuǎn)換，得到一個(gè)可以進(jìn)行排序和比較操作的字符串編碼.Geohash算法的主要思想是對(duì)給定的經(jīng)緯度值，利用二分法的思想來(lái)進(jìn)行無(wú)限的區(qū)間逼近.本文以紐約時(shí)代廣場(chǎng)某地的坐標(biāo)值（-73.980844，40.758703）為例，介紹Geohash編碼算法.

（1）地球緯度區(qū)間是［-90，90］，將其進(jìn)行二分為［-90，0］，［0，90］，稱為左右區(qū)間，可以確定40.758703屬于右區(qū)間［0，90］.

（2）將右區(qū)間進(jìn)一步二分，遞歸上述過(guò)程.可以預(yù)見(jiàn)，40.758703總是屬于某個(gè)區(qū)間［a，b］.隨著每次迭代區(qū)間［a，b］在不斷縮小，根據(jù)極限可知［a，b］會(huì)收斂到40.758703，用δ來(lái)描述就是，任意給定一個(gè)ε，總存在一個(gè)N使得:為任意給定的緯度.

（3）上述過(guò)程保證了算法收斂性，收斂的過(guò)程如下：如果給定的緯度x0.758703）屬于左區(qū)間，則記錄0，如果屬于右區(qū)間則記錄1，這樣隨著算法的進(jìn)行會(huì)產(chǎn)生一個(gè)序列10111，序列的長(zhǎng)度跟給定的收斂次數(shù)N相關(guān).同理，計(jì)算經(jīng)度-73.980844的位序列為01001.按偶數(shù)位放經(jīng)度，奇數(shù)位放緯度的規(guī)則，以精度遞增的順序?qū)⒔?jīng)度和緯度位序列交叉排列生成一個(gè)新的位序列0110010111.根據(jù)Geohash算法中所使用的Base32編碼表［6］，對(duì)合并后的二進(jìn)制序列進(jìn)行Base32編碼，從而得到地理坐標(biāo)（-73.980844，40.758703）的Geohash編碼為dr.

根據(jù)Geohash算法的編碼規(guī)則，當(dāng)編碼長(zhǎng)度越長(zhǎng)表示的區(qū)域精度就越高，可以根據(jù)具體應(yīng)用需求，來(lái)確定合適的編碼長(zhǎng)度.通過(guò)Geohash編碼，空間上相鄰的位置在編碼上可能具有相同的前綴，使之在解決附近地點(diǎn)搜索的問(wèn)題上具有明顯優(yōu)勢(shì).

2　基于HBase的位置數(shù)據(jù)存儲(chǔ)模型

HBase是一個(gè)基于列模式、稀疏存儲(chǔ)、排序的映射表，表中的數(shù)據(jù)單元通過(guò)行鍵、列族和列限定符和時(shí)間戳進(jìn)行索引和查詢定位，每一個(gè)列屬于特定的列族.HBase表模式的設(shè)計(jì)主要包括行鍵設(shè)計(jì)和列族設(shè)計(jì).本文以紐約出租車數(shù)據(jù)［9］為研究對(duì)象，出租車載客記錄包含出租車編號(hào)、司機(jī)編號(hào)、起始終止的時(shí)間和地點(diǎn)、行駛距離、行駛速度等14個(gè)要素，主要數(shù)據(jù)的詳細(xì)描述見(jiàn)表1.

表1　出租車數(shù)據(jù)說(shuō)明

位置數(shù)據(jù)的處理單元是二維坐標(biāo)（dropoff_longi?tude，dropoff_latitude），而HBase只支持一維數(shù)據(jù)的處理，因而，需要對(duì)空間數(shù)據(jù)進(jìn)行降維處理.本文基于Geohash在出租車下客的經(jīng)度與緯度上建立索引，采用兩者的Geohash字符串編碼作為HBase行健.針對(duì)位置對(duì)象的特征，HBase數(shù)據(jù)表設(shè)計(jì)為單個(gè)列族，每個(gè)行鍵下會(huì)有多個(gè)列限定符，數(shù)據(jù)表結(jié)構(gòu)表2所示. HBase按照行健字典順序進(jìn)行排序，Geohash字符串前綴匹配越多的坐標(biāo)點(diǎn)，其在HBase中就會(huì)被存儲(chǔ)得越接近，因而有利于實(shí)現(xiàn)數(shù)據(jù)的本地化.

表2　HBase數(shù)據(jù)表結(jié)構(gòu)

3　基于Geohash的多邊形區(qū)域查詢

多邊形區(qū)域查詢，指給定一個(gè)空間多邊形區(qū)域，檢索出該多邊形區(qū)域內(nèi)的所有空間對(duì)象信息［10］，比如查詢時(shí)代廣場(chǎng)街區(qū)內(nèi)的所有出租車信息.本文的多邊形區(qū)域查詢過(guò)程：首先，建立多邊形查詢區(qū)域與Geohash編碼的關(guān)聯(lián)，將多邊形查詢區(qū)域轉(zhuǎn)換成一組Geohash編碼.然后，在該Geohash前綴集上執(zhí)行HBase前綴匹配過(guò)濾，返回候選集合.最后，執(zhí)行精確過(guò)濾，過(guò)濾無(wú)效的查詢對(duì)象，最終返回滿足條件的查詢結(jié)果.具體流程見(jiàn)圖1.

圖1　多邊形區(qū)域查詢流程

3.1相關(guān)概念

為了便于多邊形區(qū)域查詢算法的描述與討論，先列出相關(guān)的定義：

1.形心［11］（Centroid）多邊形的形心，指平面多邊形的幾何中心.

2.凸包［12］（Convex Hull）是一個(gè)計(jì)算幾何中的概念，給定二維平面上的點(diǎn)集，凸包就是將最外層的點(diǎn)連接起來(lái)構(gòu)成的凸多邊型，它能包含點(diǎn)集中所有的點(diǎn).

3.2多邊形區(qū)域處理

一個(gè)Geohash字符串編碼代表的是一個(gè)規(guī)則的矩形，多邊形區(qū)域處理的核心是將被查詢的多邊形區(qū)域轉(zhuǎn)換為多個(gè)鄰接的Geohash矩形區(qū)域，且這些矩形組合區(qū)域的凸包最小包含著該多邊形區(qū)域；即計(jì)算一組最小包含查詢區(qū)域的Geohash前綴集（Mininum Bounding Prefixes-MBP），詳見(jiàn)算法1.

算法1MBP算法

輸入：多邊形區(qū)域

輸出：最小包含查詢區(qū)域的Geohash前綴集

步驟：

1）計(jì)算多邊形查詢區(qū)域的形心.

2）根據(jù)指定精度，計(jì)算該形心對(duì)應(yīng)的Geohash編碼.由于計(jì)算Geohash時(shí)需指定字符精度，本算法根據(jù)查詢區(qū)域的應(yīng)用需求，指定初始精度INIT_PRECESION.

3）基于該Geohash編碼的矩形區(qū)域計(jì)算其凸包，并檢查該凸包對(duì)查詢多邊形的包含情況，若不包含，則執(zhí)行步驟4；否則，返回該Geohash編碼，結(jié)束查詢.

4）將該Geohash編碼加上它的8個(gè)直接鄰居［8］，計(jì)算該組合區(qū)域的凸包，并檢查該凸包對(duì)查詢多邊形的包含情況.若不包含，則降低初始精度INIT_PRECESION，即INIT_PRECESION減一，擴(kuò)大查詢范圍，重復(fù)執(zhí)行步驟2；否則，返回該Geohash編碼加上它的8個(gè)直接鄰居所組成的集合，結(jié)束查詢.

MBP算法的輸入是多邊形查詢區(qū)域，輸出為計(jì)算出的包含查詢區(qū)域的最小包圍Geohash前綴集.最小包圍使得HBase掃描的次數(shù)和掃描覆蓋的空間區(qū)域降到最小，以提高查詢效率.該算法的關(guān)鍵在于確定最佳的Geohash初始精度，以提高查詢效率.

3.3HBase數(shù)據(jù)掃描與精確過(guò)濾

HBase數(shù)據(jù)掃描階段通過(guò)調(diào)用MBP算法獲取Geohash前綴集，執(zhí)行HBase前綴匹配掃描，返回查詢所得的候選集合；在精確過(guò)濾階段，檢查每一個(gè)返回的候選對(duì)象是否落在查詢多邊形區(qū)域內(nèi)，并移除位于前綴集區(qū)域但不位于多邊形查詢區(qū)域內(nèi)的無(wú)效數(shù)據(jù)；最終返回符合條件的結(jié)果集.算法2包含了多邊形區(qū)域查詢流程（圖1）的第②步和第③步.

算法2RegionalQuery算法

輸入：多邊形查詢區(qū)域

輸出：查詢區(qū)域內(nèi)的結(jié)果集

步驟：

1）根據(jù)多邊形查詢區(qū)域，調(diào)用MBP算法獲取最小包圍的Geohash前綴集.

2）對(duì)于Geohash前綴集中的每個(gè)Geohash編碼，逐一執(zhí)行HBase前綴匹配掃描，返回所有候選結(jié)果集.

3）對(duì)于候選結(jié)果集的每個(gè)元素，檢驗(yàn)該元素代表的空間位置是否包含在多邊形查詢區(qū)域內(nèi)，若未包含，則從結(jié)果集移除該元素.

4）返回符合條件的所有results.

4　試驗(yàn)設(shè)計(jì)與結(jié)果分析

圖2　HBase與MySQL的區(qū)域查詢效率對(duì)比

4.1試驗(yàn)環(huán)境及數(shù)據(jù)

試驗(yàn)由4臺(tái)配置相同的服務(wù)器組成HBase集群，每臺(tái)服務(wù)器的軟硬件環(huán)境如表3所示，其中一臺(tái)機(jī)器單機(jī)測(cè)試MySQL.試驗(yàn)數(shù)據(jù)采用2013年全年的紐約出租車數(shù)據(jù)，平均每月的數(shù)據(jù)文件約1.4億條記錄，全年數(shù)據(jù)總量大小約30G.試驗(yàn)的查詢區(qū)域是半徑不超過(guò)2.5km的任意幾何區(qū)域.

表3　試驗(yàn)環(huán)境

4.2多邊形區(qū)域查詢性能分析

試驗(yàn)對(duì)比不同數(shù)據(jù)量下，HBase與MySQL數(shù)據(jù)庫(kù)下區(qū)域查詢算法的響應(yīng)時(shí)間.從圖2a可以看出，隨著數(shù)據(jù)量的增大，HBase耗時(shí)很少且查詢響應(yīng)時(shí)間基本不受影響，但MySQL查詢耗時(shí)上升較快.將查詢區(qū)域擴(kuò)大并基于更大規(guī)模數(shù)據(jù)的實(shí)驗(yàn)（圖2b），MySQL查詢耗時(shí)隨數(shù)據(jù)量的增長(zhǎng)而急劇上升；而在HBase集群下，該算法的響應(yīng)時(shí)間雖有所增加，但幅度變化較小.試驗(yàn)表明，在HBase集群下該算法具有較好的時(shí)效性.

5　結(jié)語(yǔ)

云計(jì)算技術(shù)為海量數(shù)據(jù)的存儲(chǔ)提供了一種新的解決方案.Geohash編碼把二維經(jīng)緯度坐標(biāo)降維成一維字符串，且空間位置相鄰的Geohash編碼具有相同的前綴，據(jù)此，本文基于Geohash構(gòu)建空間索引，并基于該索引探討一種多邊形區(qū)域查詢算法.與傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)MySQL相比，HBase集群環(huán)境下查詢效率有較大的提升，可以滿足區(qū)域查詢中的時(shí)效性要求，為更高層次的應(yīng)用提供了參考.

［參考文獻(xiàn)］

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

［2］劉經(jīng)南，方媛，郭遲，等.位置大數(shù)據(jù)的分析處理研究進(jìn)展［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2014，39（4）：379-385.

［3］過(guò)志峰，王宇翔，楊崇俊.空間數(shù)據(jù)索引與查詢技術(shù)研究及其應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2002，38（23）：176-178.

［4］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.

［5］陸鋒，周成虎.一種基于Hilbert排列碼的GIS空間索引方法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2001，13（5）：424-429.

［6］Niemeyer G.Geohash［EB/OL］.2013-06-20，http：//en.wikipedia.org/wiki/Geohash.

［7］DIMIDUK N，KHURANA A.HBase in Action［M］.New York：Manning Publicatons Co，2012：203-215.

［8］金安，程承旗，宋樹華，等.基于Geohash的面數(shù)據(jù)區(qū)域查詢［J］.地理與地理信息科學(xué)，2013，29（5）：31-35.

［9］NYC Taxi Trips by andresmh［EB/OL］.2014-11-11.http：// www.andresmh.com/nyctaxitrips/.

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

［11］Centroid［EB/OL］.［2015-05-13］.https：//en.wikipedia.org/ wiki/Centroid.

［12］Convex hull［EB/OL］.［2003-11-03］.https：//en.wikipedia. org/wiki/Convex_hull.

（責(zé)任編輯：李潔坤）

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：2096-2126（2016）03-0140-04

［收稿日期］2016-03-02

［基金項(xiàng)目］2015年度廣西職業(yè)教育教學(xué)改革立項(xiàng)項(xiàng)目“計(jì)算機(jī)應(yīng)用技術(shù)（Web方向）“產(chǎn)品驅(qū)動(dòng)”實(shí)踐教學(xué)體系的改革研究與實(shí)踐”（桂教職成（2015）22號(hào)）。

［作者簡(jiǎn)介］何首武（1979—），男，山西河曲人，碩士，講師，研究方向：云計(jì)算、數(shù)據(jù)管理。

［通訊作者］李曉英（1981—），女，山西汾陽(yáng)人，碩士，講師，武漢大學(xué)計(jì)算機(jī)學(xué)院訪問(wèn)學(xué)者，研究方向：數(shù)據(jù)管理。

The Research of Location Data Regional Query Based on HBase

HE Shouwu1，JIANG Linli2，LI Xiaoying1，3

（1.Campus of Nanning，Guilin University of Technology，Nanning，Guangxi，530001China；2.College of Mathematics and Computer Science，Guangxi Science&Technology Normal University，Laibin，Guangxi，546199 China；3.Computer School，Wuhan University，Wuhan，Hubei，430072 China）

Abstract:With the growing popularity of location-based services，how to make the efficient spatial query in the massive location da?ta has become an important research topic.With the research of storage mode of distributed database HBase and Geohash code，the data?base model of the location data was proposed，in which the row key was designed by the method of the spatial index based on GeoHash.A polygon region query algorithm is discussed on the basis of the above work..The HBase cluster environment is used to verify high efficien?cy of the proposed method.Compared with the traditional MySQL database，the proposed algorithm achieves better query efficiency and scalability.

Key words:location big data；HBase；GeoHash；regional query