HBase中半結(jié)構(gòu)化時空數(shù)據(jù)存儲與查詢處理*

封孝生，張　翀，陳曉瑩，唐九陽，葛　斌

(國防科技大學 信息系統(tǒng)工程重點實驗室， 湖南 長沙　410073)

?

HBase中半結(jié)構(gòu)化時空數(shù)據(jù)存儲與查詢處理*

封孝生，張翀，陳曉瑩，唐九陽，葛斌

(國防科技大學 信息系統(tǒng)工程重點實驗室， 湖南 長沙410073)

摘要：針對在HBase中如何進行有效的半結(jié)構(gòu)化時空數(shù)據(jù)存儲和查詢問題展開研究，對該問題進行形式化描述，并利用半結(jié)構(gòu)化處理方法TwigStack提出HBase的半結(jié)構(gòu)化時空數(shù)據(jù)存儲模型，在此基礎(chǔ)上開展了半結(jié)構(gòu)化的時空范圍查詢和kNN查詢。在真實數(shù)據(jù)集中進行實驗，與需要硬件配置較高的MongoDB進行了對比，結(jié)果表明在普通配置的機器上，所提出的半結(jié)構(gòu)化時空查詢算法與MongoDB性能相近，在實際中具有優(yōu)勢。

關(guān)鍵詞：時空數(shù)據(jù)；半結(jié)構(gòu)化；HBase；時空范圍查詢；kNN查詢

隨著遙感、通信等技術(shù)不斷深入發(fā)展與應用，遙感數(shù)據(jù)規(guī)模呈幾何級增長，海量遙感數(shù)據(jù)的高效的面向時空屬性的檢索對數(shù)據(jù)庫時空查詢處理技術(shù)提出了挑戰(zhàn)。前序工作中大部分都是考慮如何索引和檢索時空屬性，而包含了檢索關(guān)鍵字的工作又僅僅是考慮結(jié)構(gòu)化的情況，然而對于檢索遙感數(shù)據(jù)，問題背景發(fā)生了變化。通常，遙感數(shù)據(jù)本身并不是文字直接表現(xiàn)的數(shù)據(jù)，如衛(wèi)星遙感圖像、氣象云圖等，因此檢索遙感數(shù)據(jù)實際上是對描述遙感數(shù)據(jù)的元數(shù)據(jù)(也稱編目)進行檢索，而元數(shù)據(jù)是用半結(jié)構(gòu)化樹形結(jié)構(gòu)，如可擴展標記語言(eXtensive Markup Language,XML)文件進行描述，那么問題背景就變成了如何針對海量的半結(jié)構(gòu)化數(shù)據(jù)進行時空+半結(jié)構(gòu)化查詢語言(如XPath)的檢索。

表1顯示了一份遙感元數(shù)據(jù)樣例，用戶可以通過聲明查詢地理范圍與時間范圍以及半結(jié)構(gòu)化查詢條件來查詢遙感數(shù)據(jù)。例：查詢區(qū)域R(以點c為圓心，r為半徑)內(nèi)，時間為2周以內(nèi)，且內(nèi)容滿足“/遙感數(shù)據(jù)編目[類型=‘衛(wèi)星遙感圖像’ and //類型=‘CCD相機’]//路徑”這樣條件的所有遙感數(shù)據(jù)。需要注意的是，此處半結(jié)構(gòu)化查詢是XPath中的twig查詢。

表1　遙感元數(shù)據(jù)樣例

針對這種既有時空查詢，又有樹狀結(jié)構(gòu)+內(nèi)容的混合查詢，目前還沒有在海量大數(shù)據(jù)情況下的相關(guān)查詢處理技術(shù)。盡管很容易想到利用MongoDB[1]進行存儲與時空查詢，然而，第一，MongoDB并不支持時間區(qū)間的存儲與查詢；第二，雖然MongoDB面向JSON(JavaScript object notation)以文檔為中心進行存儲，但對復雜的twig查詢(如表1)效果不佳；第三，雖然MongoDB查詢效率較高，但這是建立在高內(nèi)存占用比例基礎(chǔ)之上的，對硬件投入較大。

相對而言，HBase[2]作為高性能、列存儲、可伸縮、實時讀寫的分布式數(shù)據(jù)庫，可支持集群存儲海量數(shù)據(jù)，極大彌補了傳統(tǒng)數(shù)據(jù)庫和MongoDB的不足。然而HBase僅支持鍵值對(key-value)模式的查詢，對多維復雜查詢能力支持不足，因此現(xiàn)有的工作基本圍繞如何提高HBase多維或空間查詢性能展開，主要集中研究建立空間數(shù)據(jù)的索引結(jié)構(gòu)。一方面，這些工作沒有考慮空間對象的時間維屬性。對于時空對象，時間和空間屬性是密不可分的，簡單將時間維作為另一種空間維處理，會由于數(shù)據(jù)性質(zhì)不同而造成分布不均以致降低性能。另一方面，現(xiàn)有工作基本上受限于HBase平臺的架構(gòu)，無法取得性能上的突破。

針對上述問題，本文從存儲與查詢半結(jié)構(gòu)化時空數(shù)據(jù)的需求出發(fā)，采用HBase技術(shù)，并為切實提高HBase的時空查詢性能，提出了充分利用HBase中唯一的索引機制meta來設計時空索引結(jié)構(gòu)——HBase的半結(jié)構(gòu)化時空(HBase Semi-Structured Spatio-Temporal, HSSST)數(shù)據(jù)存儲與索引模型，并在此結(jié)構(gòu)基礎(chǔ)上，設計了范圍查詢和kNN查詢算法，以及這兩種查詢的并行化算法。

1相關(guān)工作

目前傳統(tǒng)的基于結(jié)構(gòu)化查詢語言(Structured Query Language, SQL)的時空數(shù)據(jù)存儲與查詢處理提供了一個簡單的形式結(jié)構(gòu)將信息存儲和管理在表結(jié)構(gòu)中。數(shù)據(jù)存儲和檢索可以通過簡單的表操作來實現(xiàn)，然而，基于SQL難以滿足高效率的數(shù)據(jù)插入和查詢需求，更難以滿足TB級的數(shù)據(jù)負擔。相對而言，半結(jié)構(gòu)化的NoSQL數(shù)據(jù)庫存儲能夠支持大規(guī)模的時空數(shù)據(jù)操作。

MongoDB是一種可擴展、性能高、開源、模式自由、面向文檔的數(shù)據(jù)庫，歸類為NoSQL的數(shù)據(jù)庫。MongoDB能夠直接支持空間類數(shù)據(jù)存儲以及建立索引滿足相應的功能需求，例如：GeoJSON可采用geospatial (2d) index對存儲在文檔中的空間數(shù)據(jù)坐標對進行索引，隨后計算地理哈希(Geohash)值(Geohash是基于經(jīng)緯度的地理編碼)。其他NoSQL數(shù)據(jù)庫雖然并沒有直接支持空間數(shù)據(jù)編碼的方法，但可以通過Geohash方法進行擴展，而在MongoDB中，將時間維度與空間維度結(jié)合進行查詢是其本身不支持的。

另外一種NoSQL數(shù)據(jù)庫——HBase，能夠適應大數(shù)據(jù)時空數(shù)據(jù)存儲和高效率的數(shù)據(jù)插入，但只支持單一的數(shù)據(jù)檢索模式，而時空數(shù)據(jù)檢索要求返回在特定的空間和時間范圍的數(shù)據(jù)對象，這種檢索要求是傳統(tǒng)的HBase無法實現(xiàn)的。

文獻[3]提出了MD-HBase，一種應用于平臺即服務(PaaS)的多維查詢方法。它使用K-D樹和四叉樹(quad-tree)進行空間的分割，以及采用Z-曲線將多維數(shù)據(jù)轉(zhuǎn)換為一維數(shù)據(jù)，支持多維范圍和最近鄰查詢。文獻[4]提出了一種基于R+樹的鍵值構(gòu)建方案，稱為KR+樹，并在KR+樹的基礎(chǔ)上，設計了空間查詢算法——kNN查詢和范圍查詢，并將其在HBase和Cassandra上進行運用。實驗結(jié)果表明，構(gòu)建的KR+樹優(yōu)于MD-HBase[3]。文獻[5]提出適用于分布式多維數(shù)據(jù)的索引——EDMI(efficient distributed multi-dimensional index)，其中包括兩個層次：上層采用K-D樹把空間分割成許多子空間；底層中，每一個子空間分別對應一個Z-order搭配R樹前綴(ZPR樹)。ZPR樹可以避免由R樹節(jié)點中多維數(shù)據(jù)引起的最小邊界矩形(Minimum Bounding Rectangles, MBRs)重疊。相較于其他的packed-R樹和R*樹，ZPR樹具有更好的查詢性能?；贖Base平臺上的測試結(jié)果表明，EDMI在點查詢、范圍查詢和kNN查詢方面都具有優(yōu)越性。文獻[6]提出一種針對HBase的數(shù)據(jù)模型——HGrid。該數(shù)據(jù)模型基于混合索引結(jié)構(gòu)，融合了四叉樹和常規(guī)的網(wǎng)格(grid)結(jié)構(gòu)，支持范圍查詢和kNN查詢。文獻[7]提出一種基于HBase的可擴展的數(shù)據(jù)存儲機制——HBaseSpatial，通過與MongoDB和MySQL作比較，實驗結(jié)果表明該方法能有效提高大空間數(shù)據(jù)的查詢速度。

上述方法的研究對象為空間數(shù)據(jù)，而在實際應用中，空間數(shù)據(jù)的時間屬性是不容忽視的。文獻[8]從設計HBase的模式(schema)出發(fā)設計行鍵(rowkey)來滿足多維或空間查詢,并結(jié)合Bloom過濾器來快速過濾關(guān)鍵詞從而實現(xiàn)時空數(shù)據(jù)的關(guān)鍵詞查詢。文獻[9]則進一步研究了HBase的內(nèi)部索引機制，提出STEHIX (spatio-temporal HBase index)，適合于HBase的兩級架構(gòu)，其利用了meta鏈表分別索引了空間和時間，在此基礎(chǔ)上設計了時空范圍查詢和kNN查詢，以及對應的并行算法。

在諸多的針對時空數(shù)據(jù)的應用中，移動對象也是常見的研究對象。文獻[10]提出了一種基于HBase、采用R樹構(gòu)建空間索引以及用于遍歷空間的希爾伯特曲線(Hilbert curve)的混合索引結(jié)構(gòu)。它支持多維范圍查詢和kNN查詢，尤其是在不均勻分布的數(shù)據(jù)中應用效果優(yōu)于MD-HBase[3]和KR+[4]。雖然此方法考慮了時空條件，但仍然無法滿足對時空數(shù)據(jù)更加多樣的時空檢索應用。

選擇半結(jié)構(gòu)化時空數(shù)據(jù)的存儲方法還應考慮其轉(zhuǎn)化為其他形式數(shù)據(jù)得以應用的性能，文獻[11]在鏈接開放數(shù)據(jù)(Linked Open Data， LOD)的研究中，對比了HBase、逗號分隔值(Comma-Separated Values, CSV)、XML轉(zhuǎn)化為資源描述框架(Resource Description Framework, RDF)的三種方法的轉(zhuǎn)化性能，結(jié)果表明HBase的映射轉(zhuǎn)化效率最高。

2問題描述與預備知識

2.1問題描述與定義

含有時空信息的半結(jié)構(gòu)化數(shù)據(jù)可以方便靈活地描述遙感信息產(chǎn)品等數(shù)據(jù)。一般半結(jié)構(gòu)化時空數(shù)據(jù)可以描述為，解釋如下：

1)uid是半結(jié)構(gòu)化時空數(shù)據(jù)文檔的唯一標識；

2)(xl,yl,xu,yu)是文檔uid描述的數(shù)據(jù)對應的空間范圍；

3)(ts,te)是文檔uid描述的數(shù)據(jù)對應的時間范圍；

4)T是除去時空信息的半結(jié)構(gòu)化數(shù)據(jù)，既含有結(jié)構(gòu)信息也含有內(nèi)容(值)信息。

對于面向半結(jié)構(gòu)化時空查詢定義為：

1)時空范圍查詢。給定時間范圍(tqs,tqe)，空間范圍Rq=(c,r)(c為圓心，r為查詢半徑)，半結(jié)構(gòu)化XPath查詢xq，查詢所有滿足(tqs,tqe)∩(ts,te)≠?，Rq∩(xl,yl,xu,yu)≠?，且滿足xq的文檔；

2)kNN查詢。給定時間范圍(tqs,tqe)，空間位置q=(xq,yq)，以及自然數(shù)k與半結(jié)構(gòu)化XPath查詢xq，查詢所有滿足(tqs,tqe)∩(ts,te)≠?且滿足xq、距離q最近的k個文檔。

2.2TwigStack算法

TwigStack算法是一種有效解決XML結(jié)構(gòu)查詢的方法，尤其是針對小枝連接(twig join)查詢。主要思想是首先將XML結(jié)點進行區(qū)域碼(region code)編碼，形成的編碼格式為：①若該結(jié)點為非值結(jié)點(非葉子結(jié)點)，則為(XML文檔ID, 起始訪問編碼: 結(jié)束訪問編碼, 層次碼)；②若該結(jié)點為葉子結(jié)點，則為(XML文檔ID, 訪問編碼, 層次值)。利用訪問編碼能否覆蓋可以判斷祖先-后代(ancestor-descendant)關(guān)系，再加上層次碼就可以判斷父子(parent-child)關(guān)系。然后將每個標簽綁定一個數(shù)據(jù)流，該數(shù)據(jù)流是以這個標簽為實例化的所有XML結(jié)點的集合。實施查詢時，將查詢結(jié)構(gòu)樹分解為各個路徑，按照每條路徑的查詢條件從根結(jié)點至葉結(jié)點的順序訪問各個結(jié)點，并將數(shù)據(jù)流壓入棧中，然后根據(jù)編碼規(guī)則判斷關(guān)系形成各個路徑的查詢結(jié)果，最后再將所有的路徑進行合并形成最終結(jié)果。

圖1　TwigStack算法編碼示例Fig.1　Example of TwigStack coding

舉例來說，圖1顯示了對表1中的XML進行編碼后的結(jié)果，因為研究是針對時空條件進行查詢，因此對時空屬性所在的結(jié)果不做編碼。假設該XML的文檔ID為1，根結(jié)點“遙感數(shù)據(jù)編目”的區(qū)域碼為(1, 1 ∶ 24, 1)，其中第1個數(shù)字“1”代表該XML文檔ID，第2個數(shù)字為進行先序遍歷的訪問順序號，第3個數(shù)字表示為訪問完最后一個結(jié)點“路徑”后返回至跟結(jié)點的訪問序號，第4個數(shù)字代表處于第1層。由此編碼之后，給定任意兩個結(jié)點的編碼就可以判斷出這兩個結(jié)點在該XML文檔中的結(jié)構(gòu)關(guān)系。如，“光譜范圍”(1, 12 ∶19, 3)與“上限”(1, 13 ∶15, 4)，由于12<13<15<19，所以“光譜范圍”肯定是“上限”的祖先結(jié)點，再加上層次碼僅差1，則進一步判斷“光譜范圍”肯定是“上限”的父節(jié)點，又如“光譜范圍”(1, 12: 19, 3)與“50”(1, 10, 4)則不存在結(jié)構(gòu)上的關(guān)系，因為10沒有被區(qū)間(12, 19)覆蓋。

對于查詢條件“/遙感數(shù)據(jù)編目[類型=‘衛(wèi)星遙感圖像’ and //類型=‘CCD相機’]//路徑”，其結(jié)構(gòu)如圖2所示，查詢時，將會分解為3條路徑分別進行查詢，其中第1條路徑“遙感數(shù)據(jù)編目”與“類型”是父子結(jié)構(gòu)關(guān)系，其余2條為祖先-后代關(guān)系，查詢后再根據(jù)文檔ID進行合并，最終形成查詢結(jié)果。

圖2　查詢條件結(jié)構(gòu)示例Fig.2　Example of query structure

為了便于表述，現(xiàn)將TwigStack算法的相關(guān)操作表示如下：

1)encodeNode(n)，將樹結(jié)點n進行編碼；

2)decom(q)，將結(jié)構(gòu)化查詢條件q進行按路徑分解；

3)queryPath(p)，對路徑p進行查詢，返回相應的XML文檔ID以及命中的部分具體結(jié)構(gòu)；

4)mergePath(R)，對路徑查詢結(jié)果集合R進行合并并形成最終的XML結(jié)果集。

3HSSST存儲與索引模型

本節(jié)詳細描述HSSST數(shù)據(jù)存儲模型。經(jīng)觀察可知，半結(jié)構(gòu)化時空數(shù)據(jù)含有時空信息與半結(jié)構(gòu)化信息兩個部分，并且時空信息并不是空間點數(shù)據(jù)和時間點數(shù)據(jù)，而是空間范圍數(shù)據(jù)與時間段數(shù)據(jù)，這增加了存儲的復雜性。經(jīng)分析，本次研究對時空信息和半結(jié)構(gòu)化信息分別進行了存儲，索引結(jié)構(gòu)則主要根據(jù)時空信息部分建立。

3.1時空信息存儲與索引

空間部分統(tǒng)一采用Hilbert曲線進行編碼，它采用分形技術(shù)，將多維空間中等分的區(qū)域(cell)中心連接起來，且每個區(qū)域僅進出一次，從而將多維空間區(qū)域映射為1維區(qū)間。對于給定的空間，cell面積的大小取決于Hilbert曲線的階數(shù)λ，λ越大，則等分的cell數(shù)量越多，并且每個cell面積越小。實驗證明[12]，Hilbert是能最好地保持空間局部鄰接性的填充曲線。圖3展示了1階，2階和3階Hilbert曲線。

圖3　Hilbert曲線Fig.3　Hilbert curves

時間部分采用周期+粒度方式進行索引，即首先設定一個時間周期T(如24 h)，然后在T內(nèi)按照粒度tG(如1 h)進行劃分，那么任何時間段值對T取模后都可以對應至周期T內(nèi)，即計算與該時間段相交疊的粒度區(qū)間(注意，由于遙感信息的采集時間段是任意的，因此一個時間段可以對應到多個粒度區(qū)間)。舉例來說，如圖4所示，周期T被劃分為5段，時間段t1對應于粒度區(qū)間[0,tG]，而時間段t2對應于粒度區(qū)間[tG,2tG]和[2tG,3tG]，類似地，時間段t3對應于粒度區(qū)間[2tG,3tG]，[3tG,4tG]以及[4tG,T]。

圖4　時間索引示例Fig.4　Example of time index

圖5　時空信息索引Fig.5　Spatio-temporal data index

3.2半結(jié)構(gòu)化信息存儲

半結(jié)構(gòu)化信息的存儲依靠區(qū)域碼對其進行編碼。首先調(diào)用encodeNode()函數(shù)將每個樹結(jié)點進行編碼，例如，tn1編碼為ec1，然后將tn1作為HBase中列的列鍵(column qualifier)，ec1作為時空信息部分與tn1形成cell的值。

表2示例了時空半結(jié)構(gòu)化信息在HBase邏輯表中的存儲方式。其中行鍵即為meta索引，存儲Hilbert值，列中的列族(column family)用hssst代表，space和time這兩個列鍵對應的cell中存儲文檔中標注的空間范圍和時間區(qū)間，接下來的列鍵就是該文檔中的樹結(jié)點，所對應的cell中存儲該樹結(jié)點的區(qū)域碼編碼。注意，邏輯表中反映不出時間索引。

表2　時空半結(jié)構(gòu)數(shù)據(jù)在HBase的邏輯表示

4查詢處理算法

4.1時空范圍查詢

對于給定范圍查詢——時間范圍(tqs,tqe)、空間范圍Rq=(c,r)(c為圓心，r為查詢半徑)、半結(jié)構(gòu)化XPath查詢xq，基本處理流程如算法1所示：首先計算空間范圍Rq與Hilbert曲線的交集，即所相交的Hilbert cell值集合Hq，然后將Hq作為條件查詢meta索引，獲得對應的區(qū)域服務器列表，然后在區(qū)域服務器中利用時間索引查詢條件(tqs,tqe)獲得存儲文件上對應的item，每個item就是邏輯表中的行健+列族+列鍵+cell值，形式化為(rowkey, column family, column qualifier, cell)，然后利用TwigStack算法判斷item中半結(jié)構(gòu)化信息是否符合xq查詢條件，若符合且時空屬性均符合則輸出該文檔作為結(jié)果。

算法1　時空范圍查詢算法

對上述算法解釋如下：第2行函數(shù)intersectHilbert()為計算空間范圍Rq與Hilbert cell的交集；第3行為利用meta索引，根據(jù)Hilbert值集合Hq查找對應的區(qū)域服務器；第4行至第6行為每個服務器通過時間索引查找存儲文件中對應的item，形成item集合；第7行將XPath查詢條件分解為多個路徑的集合P；第8行至第13行為依次根據(jù)P中每個路徑利用TwigStack算法查找符合條件的文檔，并判斷該文檔的時空屬性是否符合查詢條件；最后，第14行將符合條件的文檔進行過濾合并形成結(jié)果返回。

4.2kNN查詢

采用串行的方法實現(xiàn)kNN查詢算法，原因如下：并行的方法對k值的大小有一定要求，必須超過一定值后，并行的方法才有性能提高的優(yōu)勢，然而通常情況下，kNN查詢時，k值并不大；另外，并行的方法對數(shù)據(jù)分布不均勻的情況處理不好，因為這種方法只能均勻地擴大查詢邊框，造成大量的與結(jié)果無關(guān)的數(shù)據(jù)進入候選集，導致查詢性能下降。串行的方法由于采用優(yōu)先隊列技術(shù)，因此可以很好地解決數(shù)據(jù)分布不均勻的情況。

設計了增量式返回最近鄰居的方法，利用優(yōu)先隊列依據(jù)與查詢點距離的升序保存cell或半結(jié)構(gòu)化文檔，通過不斷的enqueue()和dequeue()操作，返回k個最近的文檔。下面給出距離定義。

定義1(兩點距離)給定空間中兩點p=(xp,yp)和q=(xq,yq)，距離d(p,q)為歐式距離，即

(1)

定義2(點與矩形之間的距離)給定空間中點p=(xp,yp)以及矩形R=(xl,yl,xu,yu)，若p在R內(nèi)(包括R的邊沿)，距離為0；否則，距離d(p,R)定義為：

(2)

式中，d1=d[p,(xl,yl)],d2=d[p,(xl,yu)],d3=d[p,(xu,yl)],d4=d[p,(xu,yu)]。

對于給定時間范圍(tqs,tqe)，空間位置q=(xq,yq)，k以及半結(jié)構(gòu)化XPath查詢xq，kNN查詢的基本思路如算法2所示：首先將q所在的Hilbert cell插入優(yōu)先隊列，該優(yōu)先隊列按照文檔中空間范圍(即矩形)或cell(也是矩形)到q的距離升序排列元素，不斷取出第一個元素并判斷，若元素為cell則將cell中符合時間要求的文檔從HBase中取出并插入隊列，然后再將該cell的鄰居cell插入隊列；若元素為文檔，則利用TwigStack算法判斷該文檔是否符合xq查詢要求，符合的插入返回結(jié)果列表，并判斷結(jié)果數(shù)量如果達到k個，則停止循環(huán)返回結(jié)果列表。

算法說明如下：第2行初始化優(yōu)先隊列PQ，第3行定位查詢點q所在的cell，第4行將該cell壓入隊列PQ，度量值為點q與該cell之間的距離，從第5行開始，不斷將PQ中的元素取出(第6行)，然后判斷，若是cell類型(第7行)，則利用時間索引獲取該cell內(nèi)的全部符合時間條件的文檔(第8行)，形成集合xFileSet，然后將xFileSet中的每個文檔壓入PQ(第10行)，然后將當前cell的鄰居cell全部壓入PQ(第12至第15行)；若出隊列的元素類型是文檔，那么首先利用函數(shù)isSatisfied判斷該文檔是否滿足XPath查詢xq(第17行)，將滿足條件的加入結(jié)果集Qlist，若Qlist大小為k，則結(jié)束循環(huán)。

算法2kNN查詢算法

Alg.2Algorithm forkNN queries

Input:(tqs,tqe)//時間條件q=(xq,yq)//空間點k//返回的結(jié)果數(shù)量xq//XPath查詢條件Output:Qlist//查詢結(jié)果列表1. Begin2. PQ=?//初始化升序優(yōu)先隊列3. cellinitial=coorToCell(xq,yq)4. PQ.enqueue(cellinitial,d(q,cellinitial))5. whilePQ≠?6. element=PQ.dequeue();7. ifelementistypeofcellthen8. xFileSet=getXFilesbyTimeIndex(element,(tqs,tqe));9. foreachxFileinxFileSet10. PQ.enqueue(xFile,d(q,xFile.R))11. endfor12. CellSet=getNeighborCells(element.center);13. foreachcellinCellSet14. PQ.enqueue(cell,d(q,cell))15. endfor16. else//elementistypeofxFileobject17. ifelement.isSatisfied(element,xq)then18. Qlist.add(element);19. ifQlist.size()==kthen20. returnQlist21. endif22. endif23. endif24.endwhile

5實驗分析

實驗采用HBase-0.98.6搭建了一個由11個節(jié)點構(gòu)成的HBase集群。每個節(jié)點為Intel Core i3 2.40 GHz×2 CPU，2 G內(nèi)存，240 G硬盤，操作系統(tǒng)為CentOS release 6.5 64 bit，網(wǎng)絡帶寬為100 Mbps。

MongoDB是面向文檔的數(shù)據(jù)庫，它的查詢優(yōu)勢在于將索引大部分裝載于內(nèi)存，從而提高檢索的速度，然而這樣的性能需要配置較高的硬件來支撐，在實際運行中增加了投入成本。將HSSST算法與MongoDB進行對比，目的是證明在配置一般的計算機集群上，HSSST查詢性能與對配置要求較高的MongoDB相近。MongoDB的硬件環(huán)境為1臺Intel Xeon 3.60 GHz×4 CPU，32G內(nèi)存的機器。按照MongoDB的設計理念，每個半結(jié)構(gòu)化文檔存儲為MongoDB中的一個文件(document)，利用自帶的查詢方法進行時空半結(jié)構(gòu)化查詢。

實驗數(shù)據(jù)集選用真實遙感元數(shù)據(jù)集，數(shù)量為100萬，類別分為氣象、海洋、可見光成像等，數(shù)據(jù)中的空間范圍描述呈偏斜分布，時間范圍呈均勻分布。

5.1時空范圍查詢實驗

時空范圍查詢實驗中分為變化選擇率和變化HBase的節(jié)點數(shù)量。變化查詢條件的時間范圍、空間范圍和XPath的選擇率形成綜合選擇率作為測試變化點，選擇率的默認值為15%，節(jié)點數(shù)量默認為3，首先測試變化選擇率，實驗結(jié)果如圖6所示。

圖6　時空范圍查詢實驗結(jié)果(變化選擇率)Fig.6　Results of spatio-temporal rangequeries (change selectivity)

變化選擇率從3%至50%，兩種方法的查詢響應時間都在增長，這是因為隨著查詢的時空窗口與XPath選擇率的增大，所涉及的文檔數(shù)量不斷增長，HBase和MongoDB中所查詢的行數(shù)不斷增加引起查詢延時增加。從趨勢上分析，由圖中發(fā)現(xiàn)，HSSST與MongoDB的性能曲線趨勢相似。這是因為，HSSST利用HBase的meta結(jié)構(gòu)，該結(jié)構(gòu)是一種樹狀索引，通過Hilbert曲線值查找對應的區(qū)域服務器；MongoDB是一種面向文檔的NoSQL數(shù)據(jù)庫，并且針對地理信息維度建立Geospatial索引，該索引也是一種樹狀索引，但并沒有使用Hilbert映射方法，而是通過類似B-樹查找的方法深入到葉結(jié)點。雖然MongoDB充分利用內(nèi)存將查詢大部分都在內(nèi)存中完成，但其索引結(jié)構(gòu)與Hilbert曲線映射相比較并沒有優(yōu)勢，而HSSST通過Hilbert曲線映射并且將第二階段過濾查詢分散到各個區(qū)域服務器上，降低了時間開銷。因此，二者在性能上比較相近。對比兩種方法可見，在配置一般的計算機上，HSSST僅使用了3臺機器就接近了MongoDB的查詢性能(基本上相差500 ms)，這主要是因為HSSST不但使用了空間信息作索引，而且還使用了時間信息作索引結(jié)構(gòu)，并且時間索引占用內(nèi)存較小，空間索引利用meta結(jié)構(gòu)分布到各個機器上。

然后測試節(jié)點數(shù)量變化對查詢性能的影響，變化HSSST所用的節(jié)點數(shù)量從3至11，MongoDB機器1臺不變。圖7顯示了實驗結(jié)果。可見節(jié)點數(shù)量增加時，HSSST查詢時間在不斷降低，這是由于機器數(shù)量增多，查詢被分散，吞吐量增加，提高了性能。進一步，由圖可見，HSSST機器數(shù)量為5時，性能就超過了MongoDB，可見HSSST中時空索引和半結(jié)構(gòu)化查詢算法十分有效。

圖7　時空范圍查詢實驗結(jié)果(變化節(jié)點數(shù)量)Fig.7　Results of spatio-temporal rangequeries (change node numbers)

5.2kNN查詢實驗

對kNN查詢算法進行測試，類似地，也分為k值變化測試和節(jié)點數(shù)量變化測試，k值默認為10，節(jié)點數(shù)量默認值為3。圖8展示了k值變化的實驗結(jié)果。

圖8　kNN查詢算法實驗結(jié)果(變化k值)Fig.8　Results of kNN queries (change k)

由圖8可見，k值不斷增加引起訪問的空間范圍也不斷增多，兩種方法的查詢性能都在降低。趨勢上，二者的性能接近，原因同上一小節(jié)講述的。

圖9顯示了kNN查詢中節(jié)點數(shù)量變化的實驗結(jié)果。性能和原因與時空范圍查詢類似，當節(jié)點數(shù)量增大時，HSSST的查詢能力超過了MongoDB的。

圖9　kNN查詢算法實驗結(jié)果(變化節(jié)點數(shù)量)Fig.9　Results of kNN queries (change node numbers)

6結(jié)論

隨著各種探測技術(shù)的不斷發(fā)展與各類時空數(shù)據(jù)的深入應用，對時空數(shù)據(jù)的有效管理與利用將會越來越受到關(guān)注。針對半結(jié)構(gòu)化的時空數(shù)據(jù)存儲與查詢這一目前尚處起步階段的問題進行研究，面向時空范圍和kNN查詢，提出了問題的形式化描述，設計了存儲與索引結(jié)構(gòu)模型HSSST，并給出了范圍和kNN查詢的算法。實驗在真實數(shù)據(jù)集上進行，與需要配置較高硬件設備的MongoDB進行比較，結(jié)果表明所設計方法的查詢性能在配置一般的集群上就能接近MongoDB的，當節(jié)點數(shù)量增加時，其性能還會超過MongoDB。

進一步的工作將專注于將結(jié)構(gòu)化與半結(jié)構(gòu)化的時空數(shù)據(jù)統(tǒng)一建模管理，并進一步提升查詢性能。

參考文獻(References)[1]MongoDB. The MongoDB 3.2 manual[EB/OL].[2016-05-10]. https://docs.mongodb.com/manual/.

[2]Apache Software Foundation. HBase[EB/OL]. [2016-03-12]. http://hbase.apache.org.

[3]Nishimura S, Das S, Agrawal D, et al. MD-HBase: a scalable multi-dimensional data infrastructure for location aware services[C]//Proceedings of the 12th IEEE International Conference on Mobile Data Management (MDM), 2011, 1: 7-16.

[4]Hsu Y T, Pan Y C, Wei L Y, et al. Key formulation schemes for spatial index in cloud data managements[C]//Proceedings of the 13th International Conference on Mobile Data Management (MDM), 2012: 21-26.

[5]Zhou X, Zhang X, Wang Y H, et al. Efficient distributed multi-dimensional index for big data management[C]//Proceedings of 14th International Conference, WAIM , 2013: 130-141.

[6]Han D, Stroulia E. HGrid: a data model for large geospatial data sets in HBase[C]//Proceedings of the Sixth International Conference on Cloud Computing (CLOUD), 2013: 910-917.

[7]Zhang N Y, Zheng G Z, Chen H J, et al. HBaseSpatial: a scalable spatial data storage based on HBase[C]//Proceedings of the 13th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), 2014: 644-651.

[8]Chen X Y, Zhang C, Shi Z L, et al. Spatio-temporal keywords queries in HBase[J]. Big Data and Information Analytics (BDIA), 2015, 1(1): 81-91.

[9]Chen X Y, Zhang C, Ge B, et al. Spatio-temporal queries in HBase[C]//Proceedings of the IEEE International Conference on Big Data (Big Data), 2015: 1929-1937.

[10]Du N B, Zhan J F, Zhao M, et al. Spatio-temporal data index model of moving objects on fixed networks using HBase[C]//Proceedings of the International Conference on Computational Intelligence & Communication Technology (CICT), 2015: 247-251.

[11]Vahdati S, Karim F, Huang J Y, et al. Mapping large scale research metadata to linked data: a performance comparison of HBase, CSV and XML[M]. USA: Metadata and Semantics Research (MSR), Springer International Publishing, 2015: 261-273.

[12]Moon B, Jagadish H V, Faloutsos C, et al. Analysis of the clustering properties of the Hilbert space-filling curve[J]. Knowledge and Data Engineering (KDE), 2001, 13(01): 124-141.

Storage and query processing for semi-structured spatio-temporal data in HBase

FENG Xiaosheng, ZHANG Chong, CHEN Xiaoying, TANG Jiuyang, GE Bin

(The Key Laboratory of Information System Engineering, National University of Defense Technology, Changsha 410073, China)

Abstract：A study about how to effectively achieve semi-structured spatio-temporal data storage and query in HBase was carried out. The formal description of the problem was issued; the HBase semi-structured spatio-temporal storage model was proposed by using a semi-structured approach TwigStack. On this basis, semi-structured spatio-temporal range query andkNN queries were carried out. An experiment was made in terms of real data and a comparison was made with MongoDB which needs higher hardware configuration, the results show that the performance of semi-structured spatio-temporal query algorithm is similar to MongoDB in the machine with general configuration, so that it has the advantage in the practical application.

Key words：spatio-temporal data; semi-structured; HBase; spatio-temporal range query;kNN query

doi:10.11887/j.cn.201603029

收稿日期：2016-03-07

基金項目：國家自然科學基金資助項目(61303062，71331008)

作者簡介：封孝生(1971—)，男，湖北蘄春人，副教授，碩士，碩士生導師，E-mail：xsfeng@nudt.edu.cn

中圖分類號：TP391

文獻標志碼：A

文章編號：1001-2486(2016)03-174-08

http://journal.nudt.edu.cn