【摘要】：針對傳統(tǒng)的時(shí)空索引構(gòu)建、維護(hù)困難且實(shí)時(shí)查詢效率低等問題,提出基于HBase的時(shí)空索引構(gòu)造方法。該方法采用HBase作為監(jiān)測視頻大數(shù)據(jù)時(shí)空特征索引結(jié)構(gòu),通過Z填充曲線對空間特征進(jìn)行降維存儲,并利用時(shí)間、空間與屬性特征之間的關(guān)聯(lián)及依賴規(guī)則來安排rowkey索引鍵,可有效解決傳統(tǒng)的時(shí)空索引構(gòu)建、維護(hù)困難的缺陷。針對傳統(tǒng)的時(shí)空索引實(shí)時(shí)查詢效率低的問題,提出了基于Z曲線的時(shí)空關(guān)聯(lián)查詢算法。該算法對查詢空間計(jì)算Z值范圍和建立空間劃分子集,利用劃分后的時(shí)空特征進(jìn)行列索引查詢得到候選數(shù)據(jù)集并反查HBase索引表完成關(guān)聯(lián)查詢。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)的R樹索引算法相比,提出的基于HBase的時(shí)空索引構(gòu)造方法索引插入效率更高,提出的基于Z曲線的時(shí)空關(guān)聯(lián)查詢算法能夠快速高效地處理時(shí)空關(guān)聯(lián)查詢。
文內(nèi)圖片：
圖片說明： 入速度均比Ｒ-HBase快2～3倍，并且隨著數(shù)據(jù)量的不斷增大，Ｒ-HBase的插入速度明顯降低，而ZＲMF的插入速度則保持平穩(wěn)。這是因?yàn)椋?HBase為每個(gè)關(guān)鍵字都建立了一棵Ｒ樹，而Ｒ樹在插入數(shù)據(jù)時(shí)由于其負(fù)載平衡機(jī)制需要不斷調(diào)整節(jié)點(diǎn)，并且隨著數(shù)據(jù)量增多其調(diào)整得也越頻繁和復(fù)雜，所以導(dǎo)致Ｒ-HBase插入速度隨著數(shù)據(jù)量增加而下降較快。4.3.2查詢分析1)數(shù)據(jù)量對算法的影響測試實(shí)驗(yàn)在數(shù)據(jù)量分別為50、100、200、400、800萬條進(jìn)行類比，查詢條件為Q．G(1，4)，Q．P(010100～010199)，Q．T(20150307100000)，得到的查詢響應(yīng)時(shí)間如圖3所示。從圖3中分析得知，Ｒ-HBase查詢性能對數(shù)據(jù)量非常敏感，伴隨著數(shù)據(jù)量的增長，性能降低得嚴(yán)重，這是因?yàn)椋?HBase在讀取數(shù)據(jù)時(shí)先將記錄根節(jié)點(diǎn)信息的記錄讀取到內(nèi)存中，，而后按照記錄中的指針指示順序?qū)ふ移渌涗�，直至找到滿足條件的記錄并將其取出為止，其時(shí)間復(fù)雜度直接與Ｒ-tree樹高相關(guān)，數(shù)據(jù)量越大則Ｒ-tree越高，查詢響應(yīng)時(shí)間越長;而ZＲFM、kd_ZＲMF均采用連續(xù)的rowkeyＲange讀取列索引表中連續(xù)的整塊數(shù)據(jù)作為候選集，查找效率更高。2)時(shí)空范圍對算法的影響測試本實(shí)驗(yàn)將時(shí)間特征設(shè)置為連續(xù)的可變范圍，采用連續(xù)屬性特征序列進(jìn)行算法測試，查詢條件為Q．P(010100～010199)，Q．T(20150307100000～20150307110000)，測試空間范圍Q．G在各個(gè)ZＲange段時(shí)算法的查詢響應(yīng)時(shí)間。實(shí)驗(yàn)結(jié)果如表4所示。表4ZＲMF、kd-ZＲMF在不同空間范圍的查詢響應(yīng)時(shí)間算法空間特征范圍0～500～1000～2000～4000～500ZＲMF7420351414392865kd-ZＲMF1022656239801386Ｒ-HBase19134767317422694由表4中三種算法在不同的空間范圍的查詢時(shí)間結(jié)果得知，Ｒ-HBase、ZＲMF和kd-ZＲMF的查詢響應(yīng)時(shí)間隨著查詢范圍的增大都有所增加?
文內(nèi)圖片：
圖片說明： 入速度均比Ｒ-HBase快2～3倍，并且隨著數(shù)據(jù)量的不斷增大，Ｒ-HBase的插入速度明顯降低，而ZＲMF的插入速度則保持平穩(wěn)。這是因?yàn)椋?HBase為每個(gè)關(guān)鍵字都建立了一棵Ｒ樹，而Ｒ樹在插入數(shù)據(jù)時(shí)由于其負(fù)載平衡機(jī)制需要不斷調(diào)整節(jié)點(diǎn)，并且隨著數(shù)據(jù)量增多其調(diào)整得也越頻繁和復(fù)雜，所以導(dǎo)致Ｒ-HBase插入速度隨著數(shù)據(jù)量增加而下降較快。4.3.2查詢分析1)數(shù)據(jù)量對算法的影響測試實(shí)驗(yàn)在數(shù)據(jù)量分別為50、100、200、400、800萬條進(jìn)行類比，查詢條件為Q．G(1，4)，Q．P(010100～010199)，Q．T(20150307100000)，得到的查詢響應(yīng)時(shí)間如圖3所示。從圖3中分析得知，Ｒ-HBase查詢性能對數(shù)據(jù)量非常敏感，伴隨著數(shù)據(jù)量的增長，性能降低得嚴(yán)重，這是因?yàn)椋?HBase在讀取數(shù)據(jù)時(shí)先將記錄根節(jié)點(diǎn)信息的記錄讀取到內(nèi)存中，而后按照記錄中的指針指示順序?qū)ふ移渌涗�，直至找到滿足條件的記錄并將其取出為止，其時(shí)間復(fù)雜度直接與Ｒ-tree樹高相關(guān)，數(shù)據(jù)量越大則Ｒ-tree越高，查詢響應(yīng)時(shí)間越長;而ZＲFM、kd_ZＲMF均采用連續(xù)的rowkeyＲange讀取列索引表中連續(xù)的整塊數(shù)據(jù)作為候選集，查找效率更高。2)時(shí)空范圍對算法的影響測試本實(shí)驗(yàn)將時(shí)間特征設(shè)置為連續(xù)的可變范圍，采用連續(xù)屬性特征序列進(jìn)行算法測試，查詢條件為Q．P(010100～010199)，Q．T(20150307100000～20150307110000)，測試空間范圍Q．G在各個(gè)ZＲange段時(shí)算法的查詢響應(yīng)時(shí)間。實(shí)驗(yàn)結(jié)果如表4所示。表4ZＲMF、kd-ZＲMF在不同空間范圍的查詢響應(yīng)時(shí)間算法空間特征范圍0～500～1000～2000～4000～500ZＲMF7420351414392865kd-ZＲMF1022656239801386Ｒ-HBase19134767317422694由表4中三種算法在不同的空間范圍的查詢時(shí)間結(jié)果得知，Ｒ-HBase、ZＲMF和kd-ZＲMF的查詢響應(yīng)時(shí)間隨著查詢范圍的增大都有所增加?
【作者單位】： 武漢大學(xué)計(jì)算機(jī)學(xué)院;
【基金】：國家水體污染控制與治理科技重大專項(xiàng)資助項(xiàng)目(2013ZX07503-001-06) 湖北省重大科技創(chuàng)新計(jì)劃項(xiàng)目(2013AAA020)
【分類號】：TP311.13


本文編號：2515132