基于HBASE的時(shí)空大數(shù)據(jù)關(guān)聯(lián)查詢優(yōu)化

徐愛萍 王 波 張 煦

1(武漢大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430072)2(湖北省環(huán)境監(jiān)測中心站 湖北 武漢 430079)

基于HBASE的時(shí)空大數(shù)據(jù)關(guān)聯(lián)查詢優(yōu)化

徐愛萍1王 波1張 煦2*

1(武漢大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430072)2(湖北省環(huán)境監(jiān)測中心站 湖北 武漢 430079)

隨著數(shù)字采集和存儲(chǔ)技術(shù)的快速發(fā)展，視頻監(jiān)測系統(tǒng)得到快速普及，以此帶來了海量的監(jiān)測視頻數(shù)據(jù)。與文本數(shù)據(jù)不同的是，監(jiān)測數(shù)據(jù)具有時(shí)空特征，如何在規(guī)模龐大且動(dòng)態(tài)增長的數(shù)據(jù)量下進(jìn)行高效的查詢成為許多時(shí)空數(shù)據(jù)應(yīng)用所關(guān)心的問題。針對云存儲(chǔ)體系結(jié)構(gòu)中監(jiān)測視頻大數(shù)據(jù)高效的時(shí)空聯(lián)合查詢需求，充分利用時(shí)空特征值和屬性特征值在應(yīng)用中的關(guān)聯(lián)關(guān)系，以及HBase數(shù)據(jù)庫在海量查詢方面的優(yōu)良性能，提出了基于HBase Bloomfilter的時(shí)空大數(shù)據(jù)多重過濾機(jī)制，創(chuàng)新性地利用視頻文件特征值之間的依賴與關(guān)聯(lián)關(guān)系來安排rowkey索引鍵。在此基礎(chǔ)上設(shè)計(jì)出兩種時(shí)空關(guān)聯(lián)查詢算法。最后通過實(shí)驗(yàn)證明了算法在時(shí)空大數(shù)據(jù)查詢方面的可行性、靈活性和高效性，對其他大數(shù)據(jù)關(guān)聯(lián)查詢應(yīng)用有較好的指導(dǎo)意義。

云存儲(chǔ) 大數(shù)據(jù) 關(guān)聯(lián)查詢 時(shí)空特征

0 引 言

海量的時(shí)空大數(shù)據(jù)存儲(chǔ)與檢索的研究尚處于初步階段，主要局限于空間文本的處理研究方面。其數(shù)據(jù)存儲(chǔ)主要利用傳統(tǒng)的空間數(shù)據(jù)存儲(chǔ)系統(tǒng)根據(jù)空間數(shù)據(jù)模型進(jìn)行數(shù)據(jù)存儲(chǔ)，研究點(diǎn)是采用曲線降維和存儲(chǔ)壓縮機(jī)制將多維空間數(shù)據(jù)進(jìn)行降維壓縮成文本信息進(jìn)行存儲(chǔ)，以方便HBase進(jìn)行處理。常用的降維有PCA、Hilbet曲線等降維方法[1]。PCA基于主元分析的特征提取算法，對于樣本差別很大的空間樣本存在明顯的缺陷，匹配精度不夠；在數(shù)據(jù)查詢方面，RDBMS采用對一個(gè)或者若干個(gè)屬性建立索引以及優(yōu)化分頁算法來達(dá)到性能上的提升。經(jīng)典的分頁算法有ADO Recordset算法、基于TOP的快速查詢算法以及Limits算法[2]，這些算法在數(shù)據(jù)集上進(jìn)行分組分頁式加速，對關(guān)系數(shù)據(jù)庫的快速查詢起到很好的效果。文獻(xiàn)[3]提出了一種基于屬性相關(guān)性的SPARQL 查詢優(yōu)化方法，文獻(xiàn)[4-5]通過優(yōu)化索引表以及通過持續(xù)更新維護(hù)元數(shù)據(jù)對海量數(shù)據(jù)存儲(chǔ)進(jìn)行查詢優(yōu)化。這些方法通常要耗費(fèi)大量的資源來維護(hù)查詢所需要的性能開銷，且面對海量的時(shí)空大數(shù)據(jù)查詢性能很低[6]。

云計(jì)算技術(shù)的出現(xiàn)為解決該問題提供了新的思路，特別是開源社區(qū)的活躍，Hadoop生態(tài)下的HBase、Hive以及MapReduce計(jì)算框架等技術(shù)的出現(xiàn)為PB級別的數(shù)據(jù)存儲(chǔ)提供支持[7]。本研究以監(jiān)測視頻數(shù)據(jù)為信息載體，提出了一種基于各組特征值之間依賴關(guān)系而進(jìn)行rowkey排序拼接的構(gòu)成規(guī)則。首先挖掘監(jiān)測視頻中具有時(shí)空特征依賴性的關(guān)聯(lián)特征值，并在HBase中建立高效、易擴(kuò)展的存儲(chǔ)訪問索引，在此基礎(chǔ)上進(jìn)一步提出了兩種基于HBase的時(shí)空關(guān)聯(lián)查詢算法，最后通過實(shí)驗(yàn)驗(yàn)證了本研究的可行性、高效性和可擴(kuò)展性。

1 基于HBase的監(jiān)測視頻的時(shí)空大數(shù)據(jù)存儲(chǔ)設(shè)計(jì)

1.1 HBase存儲(chǔ)模型

HBase是一個(gè)面向列的、版本化的、可伸縮的、以鍵值對形式來存儲(chǔ)數(shù)據(jù)的分布式存儲(chǔ)系統(tǒng)。與傳統(tǒng)的關(guān)系型數(shù)據(jù)模型不同的是，HBase采用類似于Google的Bigtable存儲(chǔ)模型[8]，并支持“大表”的動(dòng)態(tài)擴(kuò)展，這種Bigtable存儲(chǔ)模型可以按如下定義進(jìn)行形式化描述：

(1)

F→ {Sj，Cj，j=1，2，…，J}

(2)

(3)

其中符號(hào)→表示映射關(guān)系，超列集合S和列集合C可屬于同一層次，F(xiàn)可以同時(shí)映射至S、C。HBase將這種存儲(chǔ)模型實(shí)現(xiàn)為字典式大表，K為大表行健Row Key、F實(shí)現(xiàn)為列簇ColumnFamily、S和C組成列成員Famlily:Qualifier。行健、列成員以及時(shí)間戳來唯一標(biāo)識(shí)一個(gè)cell，時(shí)間戳用來區(qū)分每個(gè)Cell可能出現(xiàn)的多個(gè)版本，每個(gè)cell中存放著一個(gè)無類型的字節(jié)碼。又由于其底層是一個(gè)稀疏的、分布式的、持久化存儲(chǔ)的多維度排序Map結(jié)構(gòu)，通常用來處理分布在數(shù)千臺(tái)普通服務(wù)器上的PB級的大數(shù)據(jù)，又由于其優(yōu)良的并行處理能力和高度可擴(kuò)展性，本文選擇HBase作為時(shí)空大數(shù)據(jù)索引表存儲(chǔ)結(jié)構(gòu)。

1.2 基于HBase時(shí)空大數(shù)據(jù)rowkey設(shè)計(jì)

1.2.1 監(jiān)測視頻時(shí)空大數(shù)據(jù)的關(guān)聯(lián)依賴規(guī)則

其中數(shù)據(jù)記錄Recordi與其特征值存在如下關(guān)系：

時(shí)空特征不依賴業(yè)務(wù)特征而獨(dú)立存在，當(dāng)時(shí)空特征T、G確定時(shí)：

(1) 任意的camera下必定有連續(xù)的case與之對應(yīng)；

(2) 任意的case下必定有連續(xù)的record與之對應(yīng)；

(3) 當(dāng)camera、case、record均一定時(shí)，則Recordi唯一確定。

我們稱視頻監(jiān)測時(shí)空大數(shù)據(jù)的業(yè)務(wù)特征case、camera、record之間存在相關(guān)依賴性，而時(shí)空特征Time、Geo與之形成時(shí)空關(guān)聯(lián)模式。例如，在某個(gè)時(shí)間某個(gè)街區(qū)，監(jiān)測系統(tǒng)的探頭必定監(jiān)測到某些事件的發(fā)生，這個(gè)事件必定分布于不同的記錄，如果我們確定了探頭號(hào)、事件號(hào)、記錄號(hào)，也就唯一了一個(gè)監(jiān)測視頻記錄，反之則不成立。

表1給出了監(jiān)測視頻時(shí)空大數(shù)據(jù)集Records中的信息描述，監(jiān)控視頻的大數(shù)據(jù)對象相關(guān)依賴性特征值由一組關(guān)鍵字成：{Time，Geo ，camera，case，record，filepath}，這組關(guān)鍵字即是滿足上述依賴規(guī)則的特征值序列，filepath指向上述序列所確定的文件記錄在存儲(chǔ)服務(wù)器中的路徑。

表1 監(jiān)測視頻時(shí)空大數(shù)據(jù)Records的表結(jié)構(gòu)

1.2.2 監(jiān)測視頻時(shí)空大數(shù)據(jù)rowkey設(shè)計(jì)

rowkey=T+Properties+Z-order值

(4)

這樣設(shè)計(jì)rowkey的好處在于：一方面，由于屬性特征具有相關(guān)依賴性，這樣安排rowkey很方便基于rowkey地去批量查詢某一時(shí)空特征下的連續(xù)記錄；另一方面，在HBase中，基于rowkey的查詢方式比過濾器的查詢方式簡單，并且指定起始位置的行掃描的IO操作效率比過濾器刪選要高效。同時(shí)Z-oder降維算法的高效壓縮機(jī)制使得其索引表能夠在保證其查詢性能的前提下大大降低數(shù)據(jù)所需的實(shí)際存儲(chǔ)空間。

1.3 基于HBase時(shí)空大數(shù)據(jù)列簇設(shè)計(jì)

在監(jiān)測視頻Record的元信息基礎(chǔ)上進(jìn)行整合，時(shí)間、空間特征整合為時(shí)空關(guān)聯(lián)特征。為時(shí)空關(guān)聯(lián)特征和屬性特征建立HBase列簇。為了進(jìn)一步篩選特征值缺省下滿足查詢條件的rowkey，方便從時(shí)空關(guān)聯(lián)特征和屬性特征兩個(gè)維度數(shù)據(jù)處理，結(jié)合 HBase的過濾器機(jī)制，將屬性特征和時(shí)空關(guān)聯(lián)特征存儲(chǔ)到HBase表中并分別建立過濾列簇，用以解決在某特征值缺省情況下限定rowkey篩選的范圍。利用這種多重過濾機(jī)制加快時(shí)空數(shù)據(jù)的處理、增強(qiáng)查詢的靈活性。

1.3.1 時(shí)空關(guān)聯(lián)特征列簇設(shè)計(jì)

時(shí)空關(guān)聯(lián)數(shù)據(jù)模型將數(shù)據(jù)劃分為：矢量數(shù)據(jù)、時(shí)間數(shù)據(jù)、屬性數(shù)據(jù)以及拓?fù)鋽?shù)據(jù)，結(jié)合監(jiān)測視頻數(shù)據(jù)應(yīng)用場景涉及到的空間坐標(biāo)數(shù)據(jù)、時(shí)間數(shù)據(jù)、業(yè)務(wù)數(shù)據(jù)(屬性數(shù)據(jù))。我們利用HBase存儲(chǔ)模型將三類數(shù)據(jù)依次設(shè)計(jì)成時(shí)間數(shù)據(jù)列簇、空間矢量列簇。矢量空間點(diǎn)在GeoTool采用二維坐標(biāo)存儲(chǔ)，在HBase中需將矢量空間點(diǎn)橫縱坐標(biāo)解析成字符串類型進(jìn)行存儲(chǔ)；時(shí)間數(shù)據(jù)采用14位時(shí)間占位符Time: yyyy-MM-dd hh:mm:進(jìn)行存儲(chǔ)?？臻g數(shù)據(jù)和時(shí)間數(shù)據(jù)共同構(gòu)成時(shí)空關(guān)聯(lián)列簇TGeo，TGeo列簇設(shè)計(jì)如表2所示。各列簇中的屬性名稱作為HBase的列限定符動(dòng)態(tài)增加，使列簇模式可復(fù)用和擴(kuò)展。

表2 TGeo列簇設(shè)計(jì)

屬性數(shù)據(jù)是建立在時(shí)空數(shù)據(jù)之上的一組監(jiān)測視頻Record屬性特征集，存儲(chǔ)在Properties列簇中，存儲(chǔ)格式采用普通字符串，列屬性名稱為事件號(hào)、探頭號(hào)、記錄號(hào)，各占4位。例如，假設(shè)t1時(shí)刻在(x1,y1)處的監(jiān)測站點(diǎn)記錄下一段監(jiān)測視頻Record1，則視頻處理程序會(huì)通過監(jiān)測視頻本體庫為Record1進(jìn)行屬性標(biāo)記，這些標(biāo)記屬性有case1(事件號(hào))、camera1(探頭號(hào))、record1(記錄號(hào))，并且在記錄進(jìn)行插入時(shí)，將文件所在的路徑filepath寫入到HBase表中。Properties列簇設(shè)計(jì)如表3所示。

表3 Properties列簇設(shè)計(jì)

1.3.2 多重過濾鍵列簇設(shè)計(jì)

多重過濾機(jī)制的過濾列簇用來解決時(shí)空關(guān)鍵字查詢的，縮小候選鍵查找范圍， HBase單一的行健查詢規(guī)則無法過濾掉不滿足條件的結(jié)果集，例如，在片區(qū)A(我們這里假設(shè)片區(qū)A中包含的監(jiān)測坐標(biāo)點(diǎn)群為(1,1),(1,2),(1,3))中查找t時(shí)刻，(1,1)～(2,2)范圍內(nèi)的所有記錄,如果采用HBase提供的基于行健的查詢接口scan，查詢過程分為兩步。首先，根據(jù)rowkey構(gòu)成規(guī)則在rowkey中挑選出含縱坐標(biāo)的行鍵，得到的(1,1),(1,2),(1,3)中,(1,3)縱坐標(biāo)不在(1,1)～(2,2)范圍內(nèi)，這個(gè)點(diǎn)不應(yīng)出現(xiàn)在結(jié)果中，因此必須設(shè)計(jì)過濾鍵在HBase服務(wù)器段進(jìn)行再次過濾。過濾列簇采用HBase的布隆過濾器[10](bloom filter)對查詢進(jìn)行優(yōu)化，列簇設(shè)計(jì)如表4所示。過濾列簇的Qualifiler(列限定符)包含：時(shí)空點(diǎn)橫縱坐標(biāo)x+y構(gòu)成的空間過濾鍵(記作G)，和時(shí)間t構(gòu)成的時(shí)空過濾鍵(記作T)；事件號(hào)、探頭號(hào)、記錄號(hào)構(gòu)成的屬性過濾鍵(記作P)；Value存儲(chǔ)他們的值。

表4 MutiFilter過濾列簇設(shè)計(jì)

2 基于HBase的時(shí)空大數(shù)據(jù)聯(lián)合查詢優(yōu)化策略

在建立上述基于HBase的監(jiān)測視頻時(shí)空大數(shù)據(jù)的存儲(chǔ)基礎(chǔ)上，利用Rowkey值對海量的大數(shù)據(jù)進(jìn)行時(shí)空關(guān)聯(lián)的查詢。查詢要求可分為單記錄查詢和多記錄查，由于HBase提供的行鍵查詢接口即可解決單記錄。這里我們主要對連續(xù)多記錄查詢接口進(jìn)行算法設(shè)計(jì)，最終問題聚焦在：時(shí)空關(guān)聯(lián)的關(guān)鍵字查詢(標(biāo)記為Q(Q.T,Q.G,Q.B)，其中Q.T表示時(shí)間范圍關(guān)鍵字，Q.G表示空間范圍關(guān)鍵字，Q.B表示屬性關(guān)鍵字)，找出時(shí)空范圍(Q.T,Q.S)上所有包含業(yè)務(wù)關(guān)鍵字Q.B的記錄。

為了解決這類查詢要求，本文提出了基于多重過濾鍵的Z曲線時(shí)空關(guān)聯(lián)查詢算法 ZRMF( Z-order Range with Multi Filter based Algorithm) ，對于給定的一個(gè)時(shí)空關(guān)聯(lián)查詢請求Q(Q.T，Q.G，Q.B)，ZRMF算法主要分為三個(gè)步驟:

步驟一 計(jì)算出查詢空間范圍對應(yīng)的 Z-order 值范圍 ZRange;

步驟二 根據(jù)Zrange以及計(jì)算出rowkey Range;

步驟三 調(diào)用 HBase的scan 接口掃描索引表 indexTable多重過濾列簇MutiFilter在 HBase 服務(wù)器端過濾掉所有不在Q.T范圍內(nèi)的數(shù)據(jù)。

具體見算法1。

算法1 ZRMF時(shí)空關(guān)聯(lián)查詢算法

輸入: 時(shí)空關(guān)聯(lián)關(guān)鍵字查詢Q(Q.T,Q.G,Q.B)，其中，Q.T由給出的時(shí)間范圍確定，Q.G由左下角頂點(diǎn)坐標(biāo) left Low和右上角頂點(diǎn)坐標(biāo)right High確定，Q.B是業(yè)務(wù)特征進(jìn)行字符串拼接組成的集合

輸出: 結(jié)果集列表RecordList

1. min Z←calculate Min Zorder(left Low )

2. max Z←calculate Max Zorder(right High)

3. Zrange←calculate Zorder Range(min Z,max Z)

4. for Ziin Zrange do

5. for Biin Q.B do

6. rowkeyRange←(Zi+Bi)右移14位

7. Scan scan←rowkeyRange,MutiFilter(T),

Properties:filepath

8. RecodSeti←indexTable.getScanner( scan)

教學(xué)過程最優(yōu)化是把教學(xué)過程作為一個(gè)系統(tǒng)進(jìn)行研究，將構(gòu)成該系統(tǒng)的有機(jī)組成部分，即：教學(xué)過程中的人(教師和學(xué)生)、條件(教學(xué)物質(zhì)條件、衛(wèi)生條件、道德心理?xiàng)l件)、教學(xué)過程結(jié)構(gòu)(教學(xué)目的和任務(wù)、教學(xué)內(nèi)容、教學(xué)方法、教學(xué)組織形式、教學(xué)結(jié)果)及教學(xué)實(shí)施的基本環(huán)節(jié)當(dāng)作整體進(jìn)行研究[7]。

9. RecordList.add( RecordSeti)

10. end for

11. end for

ZRMF算法對于空間連續(xù)性好的情況(Q.G為連續(xù)可變范圍)有非常好的效果，這是因?yàn)?，一方面相關(guān)依賴值固定的情況下采用行健(rowkey)掃描的方式進(jìn)行數(shù)據(jù)查詢，復(fù)雜度為O(l)，(其中l(wèi)為region分組大小)；另一方面，對于相關(guān)依賴特征值為取值范圍的情況，盡可能地利用正則表達(dá)式對查詢請求進(jìn)行正則化，得到的正則查詢行間依然是以掃描rowkey的方式進(jìn)行檢索，IO效率更高。但是當(dāng)Q.G空間連續(xù)性不好，Zrang中無用的候選行健會(huì)更多，特別是當(dāng)查詢空間范圍Q.G增大時(shí)，無效的Z-order對HBase通信量的占用越大，ZRMF算法效率降低。因此 我們在ZRMF算法基礎(chǔ)上提出了基于空間塊劃分的時(shí)空關(guān)聯(lián)查詢算法。該算法利用kd樹整個(gè)查詢空間范圍劃分為更小的空間塊，并在該劃分塊上建立索引范圍kdi，查詢的時(shí)候則將Zrange與kdi求交集，過濾掉無效的Z-order值，以此處理完每個(gè)劃分塊之后形成一個(gè)更精準(zhǔn)的Zrange,后面的算法過程同ZRMF一樣。

具體見算法2。

算法2 kd-ZRMF時(shí)空關(guān)聯(lián)查詢算法

輸入: 時(shí)空關(guān)聯(lián)關(guān)鍵字查詢Q(Q.T,Q.G,Q.B)，其中 Q.T由給出的時(shí)間范圍確定 ，Q.G由左下角頂點(diǎn)坐標(biāo)left Low和右上角頂點(diǎn)坐標(biāo)right High確定，Q.B是業(yè)務(wù)特征進(jìn)行字符串拼接組成的集合

輸出: 結(jié)果集列表RecordList

2. max Z←calculateMaxZorder(right High)

3. Zrange←calculateZorder Range( minZ,max Z)

4. for kdiin kd-tree do

newZrangei←Zrange ∩kdi

newZrange.add (newZrangei)

5. end for

6. for Zi in newZRange do

7. for Biin Q.B do

8. rowkeyRange←(Zi + Bi)右移14位

9. Scan scan←rowkeyRange,MutiFilter(T),

Properties:filepath

10. RecodSeti←index Table.getScanner( scan)

11. RecordList.add( RecordSeti)

12. end for

13. end for

3 實(shí)驗(yàn)分析與評估

3.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)采用真實(shí)云存儲(chǔ)系統(tǒng)，系統(tǒng)架構(gòu)由兩部分組成，第一部分是搭建了12臺(tái)服務(wù)器作為Hadoop集群及其上的HBase集群，其中1個(gè)節(jié)點(diǎn)作為HMaster，其他11個(gè)節(jié)點(diǎn)作為RegionServer和ZooKeeper服務(wù)器。另一部分是安裝了thrift和自主研發(fā)的Geao-GIS系統(tǒng)。

3.2 數(shù)據(jù)導(dǎo)入

本文數(shù)據(jù)來源于Geao-GIS系統(tǒng)下武漢市視頻監(jiān)測站點(diǎn)空間數(shù)據(jù)庫，它采用shapefile格式的空間數(shù)據(jù)模型將視頻監(jiān)測點(diǎn)站標(biāo)記成Symbol點(diǎn)值，橫縱坐標(biāo)采用整型數(shù)據(jù)存儲(chǔ)。我們挑選其中Z值在0～500的symbol點(diǎn)，并將Symbol點(diǎn)的矢量空間數(shù)據(jù)以及各個(gè)Symbol的視頻數(shù)據(jù)元信息加載到HBase中，為方便實(shí)驗(yàn)，分時(shí)段對數(shù)據(jù)進(jìn)行加載，在加載過程中按照rowkey生成規(guī)則采用for循環(huán)方式對事件號(hào)，探頭號(hào)，記錄號(hào)進(jìn)行連續(xù)生成。分別生成五張不同數(shù)據(jù)級別的HBase表，導(dǎo)入的數(shù)據(jù)量如表5所示。

表5 數(shù)據(jù)導(dǎo)入情況

3.3 算法實(shí)驗(yàn)與分析

在上述數(shù)據(jù)導(dǎo)入的基礎(chǔ)上，我們主要研究大規(guī)模數(shù)據(jù)量下基于HBase的時(shí)空大數(shù)據(jù)聯(lián)合查詢優(yōu)化算法ZRMF的性能情況。本文將全表掃描的查詢標(biāo)記為QBFT(Query Based On Full Table)；將在Q.T和Q.G上構(gòu)造索引的查詢標(biāo)記為QBIT(Query Based On Index Table)。分別不同的數(shù)據(jù)量時(shí)對算法進(jìn)行性能測試，并從屬性特征集、時(shí)空特征范圍兩個(gè)方面對算法的影響進(jìn)行了實(shí)驗(yàn)分析。

1) 數(shù)據(jù)量對算法的影響測試

實(shí)驗(yàn)在50萬條、100萬條、200萬條、400萬條、800萬條進(jìn)行類比，查詢條件Q.T：20150307100000，Q.G(1,4)，Q.P(010100～010199)，Q.T缺省，得到的查詢響應(yīng)時(shí)間如圖1所示。

圖1 不同的數(shù)據(jù)量下的查詢響應(yīng)時(shí)間

從圖1中我們分析得知，四類算法在數(shù)據(jù)量不大的時(shí)候都能表現(xiàn)較好的查詢效率，而伴隨著數(shù)據(jù)量的增長，全表掃描的查詢性能對數(shù)據(jù)量非常敏感，性能降低得嚴(yán)重；適當(dāng)?shù)乃饕沟肣BIT充分利用HBase級聯(lián)索引表不斷收窄檢索空間，由于本實(shí)驗(yàn)查詢的屬性特征值具有連續(xù)性，QBIT、ZRFM、kd_ZRMF均采用連續(xù)的rowkeyRange讀取空間連續(xù)的整塊數(shù)據(jù)作為cache，提高了查找效率。所不同的是 QBIT只需一次讀取，而ZRMF、kd_ZRMF讀取的次數(shù)直接取決于屬性特征集的大小，時(shí)間開銷稍大，但是數(shù)據(jù)量對性能的影響不大。

2) 屬性特征集合對算法的影響測試

本實(shí)驗(yàn)為避免屬性特征連續(xù)的影響，采用離散屬性特征序列進(jìn)行算法測試，查詢條件Q.T：20150307100000，Q.G：(1.1)～(4.4)，Q.P：{100110，011001，101001，001100，001001})，查找實(shí)驗(yàn)結(jié)果如圖2所示。

從圖2中可以看出，對于離散型屬性特征值的查找，QBIT基于連續(xù)rowkey查詢的優(yōu)勢減弱，ZRFM則由于采用基于布隆過濾器的多重過濾機(jī)制，RowKey+ColFamily+Qualify的Scan去掉了不存在此Qualify的storefile，而且指明Qualify也能減少流量，因此即便屬性特征集增大，其性能仍然比較穩(wěn)定。同時(shí)我們發(fā)現(xiàn)kd_ZRMF隨著屬性特征值集的增加查詢響應(yīng)時(shí)間增加較快，且高于ZRMF。這是由于kd_ZRMF基于塊劃分的機(jī)制在保證候選間正確的情況下，其每個(gè)屬性特征值所包含的候選rowkey較多，增加了HBase的通信開銷。

圖2 不同的屬性集下算法的查詢響應(yīng)時(shí)間

3) 時(shí)空范圍對算法的影響測試

由于QBIT是建立在時(shí)空屬性上的索引查找，在時(shí)空值不確定情況下，無法采用前綴方式進(jìn)行查詢，其查詢過程轉(zhuǎn)換為全表掃描，因此本部分實(shí)驗(yàn)僅選取ZRMF、kd_ZRMF進(jìn)行算法實(shí)驗(yàn)。查詢條件Q.T：20150307100000～20150307110000，Q.P(010100～010199)，空間范圍Q.G在各個(gè)ZRange段時(shí)算法的查詢響應(yīng)時(shí)間。實(shí)驗(yàn)結(jié)果如表6所示。

表6 ZRMF、kd_ZRMF在不同空間范圍的查詢響應(yīng)時(shí)間

從表6中可以看出，ZRMF 和 kd-ZRMF 的查詢響應(yīng)時(shí)間隨著查詢范圍的增大而有所增加，但仍處于可接受范圍內(nèi)。當(dāng)查詢空間范圍小于等于 200 時(shí)，ZRMF 具有較好的查詢性能； 而當(dāng)查詢空間范圍超過 200 時(shí)，kd-ZRMF 表現(xiàn)出了比 ZRMF 更好的查詢性能，并且這種優(yōu)勢隨著查詢空間范圍的增大表現(xiàn)得愈加明顯。

從以上三組實(shí)驗(yàn)可以看出，通過合理設(shè)計(jì)表行鍵、過濾列簇以及查詢算法，將HBase 應(yīng)用于時(shí)空大數(shù)據(jù)數(shù)據(jù)管理可以提高時(shí)空大數(shù)據(jù)的存儲(chǔ)效率。并且通過算法類比，相對于索引查詢方式，ZRMF和kd_ZRMF算法在靈活解決時(shí)空數(shù)據(jù)聯(lián)合聯(lián)合查詢請求的同時(shí)，算法性能更為穩(wěn)定，且能夠很好地平衡存儲(chǔ)效率和查詢性能；而對于非時(shí)空特征的查詢，ZRMF和kd_ZRMF算法性能仍然不錯(cuò)，但是受離散型屬性特征值的數(shù)目影響較大。

4 結(jié) 語

本文以時(shí)空大數(shù)據(jù)在視頻監(jiān)測的應(yīng)用作為研究背景，利用具有時(shí)空大數(shù)據(jù)特征的大數(shù)據(jù)的監(jiān)測視頻作為數(shù)據(jù)源，巧妙地挖掘出其特征關(guān)聯(lián)關(guān)系并設(shè)計(jì)rowkey來構(gòu)建候選查詢鍵。同時(shí)為提高查詢的準(zhǔn)確性，利用HBase bloomfiter構(gòu)造多重過濾鍵，并根據(jù)多種可能的查詢需求提出了兩種基于HBase的時(shí)空大數(shù)據(jù)查詢算法。最后通過實(shí)驗(yàn)證明了ZRMF、kd_ZRNF算法在時(shí)空聯(lián)合查詢方面算法性能非常好，并且能滿足各類查詢請求。然而算法在處理屬性特征的查詢請求時(shí)性能尚有提升的空間，今后的工作中我們會(huì)對用戶的查詢請求進(jìn)行分類，對不同的查詢分類動(dòng)態(tài)地調(diào)整行健的位置，靈活運(yùn)用索引表進(jìn)行輔助查詢，用以提高時(shí)空關(guān)聯(lián)查詢的效率。

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

[2] 樊新華. 關(guān)系數(shù)據(jù)庫的查詢優(yōu)化技術(shù)[J]. 計(jì)算機(jī)與數(shù)字工程, 2009, 37(12):188-192.

[3] 林子雨, 賴永炫, 林琛,等. 云數(shù)據(jù)庫研究[J]. 軟件學(xué)報(bào), 2012, 34(5):1148-1166.

[4] 汪璐,程耀東,陳剛等.海量存儲(chǔ)系統(tǒng)元數(shù)據(jù)服務(wù)器的設(shè)計(jì)及性能優(yōu)化[J].計(jì)算機(jī)工程,2012,38(2):1-3.

[5] Sun Z, Shen J, Yong J. DeDu: Building a Deduplication Storage System over Cloud Computing[C]// Proc. of the 2011 15th International Conference on Computer Supported Cooperative Work in Design: IEEE 2011,348-355．

[6] Vashishtha H, Stroulia E. Enhancing query support in HBase Via An Extended Coprocessors Framework[C]// European Conference on Towards A Service-Based Internet. Springer-Verlag, 2011:75-87.

[7] Qin X P, Wang H J, Du X Y, et al. Big Data Analysis—Competition and Symbiosis of RDBMS and MapReduce[J]. Journal of Software, 2012, 23(1):32-45.

[8] Xu J W, Liang J L.Research on a Distributed Storage Application with HBase[J].Advanced Materials Research,2013,631:1265-1269.

[9] 張榆, 馬友忠, 孟小峰. 一種基于HBase的高效空間關(guān)鍵字查詢策略[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2012, 33(10):2141-2146.

[10] Dimiduk N, Khurana A. HBase 實(shí)戰(zhàn)[M]. 北京：人民郵電出版社,2013.

OPTIMIZATION OF SPATIAL AND TEMPORAL BIG DATA ASSOCIATION QUERY BASED ON HBASE

Xu Aiping1Wang Bo1Zhang Xu2*

1(SchoolofComputer,WuhanUniversity,Wuhan430072,Hubei,China)2(EnvironmentalMonitoringCenteofHubeiProvince,Wuhan430079,Hubei,China)

With the rapid development of digital acquisition and storage technology, video surveillance system has been rapidly popularized, which brings a lot of monitoring video data. Different from the text data, the monitoring data has the characteristics of time and space, and how to carry out efficient query under the large-scale and dynamic growth of data becomes a concern of many spatial and temporal data applications. To meet the requirement of space-time joint query for efficient monitoring of large video data in cloud storage architecture, in this paper, we make full use of the relationship between the temporal and spatial eigenvalues and the attribute eigenvalues in the application and the excellent performance of the HBase database in the massive query, propose HBase Bloomfilter’s multi-filtering mechanism of large data in space and time, and make use of the dependency and association between the eigenvalues of video files to arrange rowkey index keys in an innovative manner. On this basis, two kinds of spatiotemporal correlation query algorithms are designed. Finally, the feasibility, flexibility and efficiency of the algorithm are proved by experiments. It is useful for other large data association queries.

Cloud storage Big data Associated query Spatial and temporal characteristics

2016-04-16。國家水體污染控制與治理科技重大專項(xiàng)(2013ZX07503-001);湖北省重大科技創(chuàng)新計(jì)劃項(xiàng)目(2013AAA020)。徐愛萍，教授，主研領(lǐng)域：云存儲(chǔ)，空間分析，自然語言理解。王波，碩士生。張煦，工程師。

TP311

A

10.3969/j.issn.1000-386x.2017.06.008