一種支持范圍查詢的云數(shù)據(jù)空間索引研究

李劍鋒,陳世平,段林茂,鈕 亮

1(上海理工大學(xué) 管理學(xué)院,上海 200093)2(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)3(中國計(jì)量大學(xué) 經(jīng)濟(jì)與管理學(xué)院,杭州 310018)

1 引 言

移動互聯(lián)時(shí)代,基于地理位置的移動應(yīng)用程序(APP)產(chǎn)生了大量的多維數(shù)據(jù),此類數(shù)據(jù)至少包括位置信息和時(shí)間戳兩個(gè)屬性.傳統(tǒng)的關(guān)系型數(shù)據(jù)庫在海量數(shù)據(jù)高效讀取方面存在瓶頸,而分布式關(guān)系數(shù)據(jù)庫在服務(wù)器間維護(hù)數(shù)據(jù)一致性等方面所付出的代價(jià)較高[1].

以Google公司提出的BigTable[2]技術(shù)為代表,產(chǎn)生了很多新的分布式云數(shù)據(jù)管理系統(tǒng)(CDM),如HBase和Cassandra[3]等.與分布式關(guān)系數(shù)據(jù)庫相比,基于BigTable的CDM具有適用性廣、可擴(kuò)展、高性能和容錯(cuò)性好等特點(diǎn).上述CDM使用Key-Value的方式來存儲數(shù)據(jù),具有高效的數(shù)據(jù)檢索性能,原因主要有兩點(diǎn):1)每個(gè)Key-Value對被存儲在多個(gè)服務(wù)器上;2)每個(gè)Key又會保留多個(gè)版本的值.其中,第一個(gè)特點(diǎn)有利于提高檢索數(shù)據(jù)的效率,第二個(gè)特點(diǎn)降低了維護(hù)數(shù)據(jù)一致性的延遲時(shí)間.但由于BigTable在數(shù)據(jù)結(jié)構(gòu)上的局限,這些云數(shù)據(jù)管理系統(tǒng)只能支持一些基本的操作,例如HBase的Put、Scan和Get操作并不直接支持多維查詢.

針對上述CDM的原理和特點(diǎn),本文提出了一個(gè)新的可運(yùn)行在CDM上的多維索引HPR-index,該索引通過為每個(gè)桶PR四叉樹的葉節(jié)點(diǎn)分配一個(gè)希爾伯特(Hilbert)鍵值來實(shí)現(xiàn)多維查詢.本文的第一個(gè)難點(diǎn)就是如何避免查詢結(jié)果中出現(xiàn)大量的冗余數(shù)據(jù).如果地圖被分成過多的網(wǎng)格,雖然不同網(wǎng)格包含數(shù)據(jù)量的差距會縮小,但同時(shí)會造成數(shù)據(jù)查詢效率下降.因?yàn)閷τ谝粋€(gè)空間范圍查詢而言,同樣大小的空間內(nèi)網(wǎng)格越多意味著需要查詢的葉節(jié)點(diǎn)就越多,查詢時(shí)間會相應(yīng)增加.理想的情況是網(wǎng)格盡可能小的同時(shí)查詢數(shù)據(jù)的時(shí)間越來越短.因此,對于CDM而言,如何劃分地圖網(wǎng)格的密度來達(dá)到兩者的平衡至關(guān)重要.為解決這一難點(diǎn),HPR-indexs索引采用平衡的桶PR四叉樹來組織多維數(shù)據(jù),每個(gè)四叉樹的葉節(jié)點(diǎn)“管理”一個(gè)網(wǎng)格.采用桶PR四叉樹的原因主要有兩點(diǎn):1)桶PR四叉樹可通過分裂來達(dá)到網(wǎng)格大小和查詢時(shí)間之間的平衡;2)與其他樹結(jié)構(gòu)如R樹相比,桶PR四叉樹的葉節(jié)點(diǎn)不互相重疊,這樣就避免了從不同葉節(jié)點(diǎn)讀取出大量相同數(shù)據(jù)的冗余問題.本文的第二個(gè)難點(diǎn)是如何設(shè)計(jì)網(wǎng)格的鍵值命名規(guī)則,使之在基于BigTable的CDM上實(shí)現(xiàn)高效的多維查詢.本文根據(jù)上述CDM的兩個(gè)特點(diǎn),即系統(tǒng)具有高速的key-value查詢效率,并通過字典順序?qū)︽I值(key)執(zhí)行快速的Scan操作,利用Hilbert曲線的編碼規(guī)則為每個(gè)網(wǎng)格命名唯一的Hilbert鍵值.建立并維護(hù)一張路由表,表中每個(gè)網(wǎng)格區(qū)域的鍵值與桶PR四叉樹的葉節(jié)點(diǎn)一一對應(yīng).根據(jù)HPR-index的數(shù)據(jù)結(jié)構(gòu),定義了實(shí)現(xiàn)空間(二維)數(shù)據(jù)范圍查詢的算法以及插入和刪除算法.

本文的貢獻(xiàn)包括如下四點(diǎn):1)提出了可運(yùn)行在CMD系統(tǒng)上的空間索引結(jié)構(gòu)HPR-index,該索引利用平衡的桶PR四叉樹來組織空間數(shù)據(jù),利用Hilbert曲線編碼為每個(gè)網(wǎng)格命名唯一的Hilbert鍵值.HPR-index在數(shù)據(jù)均勻分布和數(shù)據(jù)偏斜的情況下均實(shí)現(xiàn)了高效的空間范圍查詢.HPR-index索引經(jīng)過修改還可用于多維數(shù)據(jù)的范圍查詢和KNN查詢;2)HPR-index高效地利用了CMD的特點(diǎn),獲得了較好的查詢效率;3)根據(jù)HPR-index的原理,設(shè)計(jì)了新的空間數(shù)據(jù)的范圍查詢算法;4)與當(dāng)前的多維索引技術(shù)相比,HPR-index具有維護(hù)代價(jià)低,實(shí)現(xiàn)方案簡單,偏斜數(shù)據(jù)查詢效率高等特點(diǎn),且適用于HBase和Cassandra等CMD.

2 相關(guān)工作

2.1 樹結(jié)構(gòu)和線性結(jié)構(gòu)

R樹被廣泛用于多維數(shù)據(jù)索引.R樹兄弟結(jié)點(diǎn)對應(yīng)的空間區(qū)域可以重疊,因此R樹的查詢效率大大降低.為了更高效地索引多維數(shù)據(jù),產(chǎn)生了很多R樹的變種,例如R+樹,R*樹等.其中R+樹子樹上的結(jié)點(diǎn)會頻繁重新劃分,插入和刪除效率低.

四叉樹是另一種索引多維數(shù)據(jù)的常用樹結(jié)構(gòu).PR四叉樹具有結(jié)構(gòu)簡單、等分?jǐn)?shù)據(jù)空間、空間劃分無重疊等優(yōu)點(diǎn).但當(dāng)數(shù)據(jù)不是均勻分布而形成了集簇或聚集時(shí),PR四叉樹含有很多空的節(jié)點(diǎn)而變得不平衡,這種不平衡可通過把這些節(jié)點(diǎn)對應(yīng)的塊聚合成叫做桶(bucket)的更大的塊而解決,即把分解方法變成只有當(dāng)塊內(nèi)包含超過s個(gè)數(shù)據(jù)點(diǎn)時(shí)才分解,這里的s叫做桶容量,這種四叉樹是桶PR四叉樹(bucket PR quadtree)[4].桶PR四叉樹經(jīng)過改進(jìn)可用于構(gòu)建適合云數(shù)據(jù)管理系統(tǒng)的多維索引結(jié)構(gòu).

線性索引技術(shù)通過將多維數(shù)據(jù)降維到一維數(shù)據(jù)來進(jìn)行索引,主要的技術(shù)有空間填充曲線,如Hilbert曲線和Z-order曲線.Hilbert曲線可以將高維空間中沒有良好順序的數(shù)據(jù)映射到一維空間,經(jīng)過這種編碼方式,空間上相鄰的對象會鄰近存儲在一起,因此提高內(nèi)存中數(shù)據(jù)處理效率.相對于其他多維線性化技術(shù),使用Hilbert曲線編碼在處理數(shù)據(jù)聚集的情況下具有優(yōu)勢.

2.2 多維索引相關(guān)研究

近年來,基于上述多維數(shù)據(jù)索引技術(shù),如Quad-kd[5]等,在CMD上構(gòu)建新型索引的研究越來越多.RT-CAN[6]在每個(gè)云節(jié)點(diǎn)的本地?cái)?shù)據(jù)上建立R樹索引,并動態(tài)選擇一部分節(jié)點(diǎn)發(fā)布到全局索引.MD-HBase[7]是基于Hbase的數(shù)據(jù)管理系統(tǒng),利用四叉樹、k-d樹以及Z-Order技術(shù)來索引多維數(shù)據(jù).MD-HBase數(shù)據(jù)一致性問題的解決方案較復(fù)雜[8].KR-index[9]在CMD上實(shí)現(xiàn)海量偏斜數(shù)據(jù)(skewed data)的多屬性查詢.該技術(shù)采用R+樹將數(shù)據(jù)劃分為互不相交的矩形單元,這些矩形存在R+樹的葉節(jié)點(diǎn)上.然后再將整個(gè)空間分成若干個(gè)互不相交的網(wǎng)格,利用Hilbert技術(shù)將這些網(wǎng)格進(jìn)行編碼,并將矩形單元與網(wǎng)格的相交關(guān)系記錄到KeyTable表中.KR-index存在結(jié)點(diǎn)頻繁重新劃分、插入和刪除效率較低等問題.本文提出的HPR-index吸收了KR-index的部分思想,采用桶四叉樹結(jié)構(gòu)來避免R+樹的一些不足.M-Index[10]采用金字塔技術(shù)(pyramid-technique)將數(shù)據(jù)的多維元數(shù)據(jù)描述成一維索引.基于HBase的交通數(shù)據(jù)索引框架[11]利用z-ordering技術(shù)進(jìn)行數(shù)據(jù)分區(qū)以支持高效的多維查詢.M-Quadtree[12]支持多維空間查詢,滿足MapReduce并行化要求.DGFIndex[13]是一種基于分布式網(wǎng)格文件的多維索引技術(shù),用來提升Hive的多維查詢處理能力.數(shù)據(jù)多維去重聚類模型[14]用來降低大數(shù)據(jù)的重復(fù)和冗余,可用于非結(jié)構(gòu)化數(shù)據(jù)的聚類分析.

上述多維索引技術(shù)雖大多能在CDM上完成一定的多維查詢和區(qū)間查詢等功能,但大多存在索引維護(hù)代價(jià)高,解決方案較為復(fù)雜等問題,特別是當(dāng)數(shù)據(jù)分布不均勻時(shí)效率普遍偏低.因此,需要改進(jìn)現(xiàn)有索引技術(shù)或提出新的多維索引技術(shù),使之具有較高效的偏斜數(shù)據(jù)查詢功能,維護(hù)代價(jià)低,實(shí)現(xiàn)方案較簡單等特點(diǎn).

3 多維索引結(jié)構(gòu)

上述CDM執(zhí)行基于鍵值對的數(shù)據(jù)查詢,支持訪問數(shù)據(jù)的基本操作,但是這些數(shù)據(jù)操作不直接支持多維數(shù)據(jù)查詢.為了解決多維查詢的問題,本文提出了適用于CDM的多維索引結(jié)構(gòu),并實(shí)現(xiàn)了空間數(shù)據(jù)的范圍查詢.

3.1 HPR-index概述

數(shù)據(jù)被組織成一顆經(jīng)過改進(jìn)的均衡的桶PR四叉樹,其中數(shù)據(jù)維數(shù)為d,桶容量為s,樹深為m,所有葉節(jié)點(diǎn)都在同一層上.數(shù)據(jù)空間被均分為(2d)m-1個(gè)互相不重疊的多維超矩形.根據(jù)Hilbert曲線的編碼規(guī)則,每個(gè)多維超矩形有一個(gè)唯一的鍵值.HPR-index建立并維護(hù)一張路由表,表中每個(gè)多維超矩形區(qū)域的鍵值與桶PR四叉樹的葉節(jié)點(diǎn)一一對應(yīng).圖1是二維空間數(shù)據(jù)的HPR-index的結(jié)構(gòu)圖,參數(shù)d=2且m=2.圖1(a)中的區(qū)域被均勻分成16個(gè)小矩形,其中每個(gè)最小矩形的中心點(diǎn)(控制點(diǎn))也就是圖1(b)中四叉樹的葉節(jié)點(diǎn).整個(gè)矩形區(qū)域的中心點(diǎn)(控制點(diǎn))是圖1(b)中四叉樹的根節(jié)點(diǎn)u0.這樣,圖1(a)的空間則被分層組織成深度m=3的一顆平衡桶四叉樹,如圖1(b)所示.同樣,根據(jù)Hilbert的編碼規(guī)則,圖1(a)中區(qū)域的每個(gè)最小矩形(葉節(jié)點(diǎn))均有一個(gè)唯一的Hilbert鍵值,如圖1(c)所示.存儲Hilbert鍵值與四叉樹葉節(jié)點(diǎn)的路由表如圖1(d)所示,從路由表中可根據(jù)鍵值檢索到四叉樹的葉節(jié)點(diǎn),從而使多屬性訪問能有效地檢索數(shù)據(jù).

3.2 插入和刪除算法

算法2用來插入一個(gè)新的數(shù)據(jù)點(diǎn).首先用算法1計(jì)算出要插入數(shù)據(jù)點(diǎn)的子區(qū)域的Hilbert鍵值,然后用四叉樹數(shù)據(jù)插入算法InsertToPRTree()將該數(shù)據(jù)點(diǎn)插入樹中.數(shù)據(jù)刪除算法3跟算法2相似,首先用算法1計(jì)算出要?jiǎng)h除數(shù)據(jù)點(diǎn)所屬的子區(qū)域的Hilbert鍵值,然后用四叉樹數(shù)據(jù)刪除算法DeleteFromPRTree()從樹中刪除.

圖1 HPR-Index 索引結(jié)構(gòu)Fig.1 Index structure of HPR-Index

算法1.SubspaceLookup(p)

輸入:數(shù)據(jù)點(diǎn) p=(x,y),x和y分別是點(diǎn)p的橫坐標(biāo)和縱坐標(biāo);

輸出:包含點(diǎn)p的最小子空間的Hilbert鍵值.

Begin

1.i←x mod o;//o為Hilbert曲線的階

2.j←y mod o;

3.return Hilbert(i,j);

End

算法2.InsertPoint(p)

輸入:數(shù)據(jù)點(diǎn) p=(x,y),x和y分別是點(diǎn)p的橫坐標(biāo)和縱坐標(biāo);

輸出:插入成功標(biāo)識flag.

Begin

1.key← SubspaceLookup(p);

2.flag←InsertToPRTree(key,p);

3.return flag

End

算法3.DeletePoint(p)

輸入:數(shù)據(jù)點(diǎn) p=(x,y),x和y分別是點(diǎn)p的橫坐標(biāo)和縱坐標(biāo);

輸出:刪除成功標(biāo)識flag.

Begin

1.key← SubspaceLookup(p);

2.flag←DeleteFromPRTree(key,p);

3.return flag

End

3.3 分裂算法

桶PR四叉樹每個(gè)節(jié)點(diǎn)存儲的數(shù)據(jù)是有限的,當(dāng)一個(gè)節(jié)點(diǎn)上存儲的數(shù)據(jù)超過這個(gè)上限,該節(jié)點(diǎn)應(yīng)該分裂.HPR-index要求桶PR四叉樹為平衡四叉樹,即所有葉節(jié)點(diǎn)均處于同一層,而部分葉節(jié)點(diǎn)的分裂會導(dǎo)致四叉樹不平衡,因此HPR-index不允許某個(gè)葉節(jié)點(diǎn)單獨(dú)分裂,只有在樹中所有葉節(jié)點(diǎn)平均存儲的數(shù)據(jù)達(dá)到一定的數(shù)量需要靠分裂來優(yōu)化時(shí),才進(jìn)行所有葉節(jié)點(diǎn)的統(tǒng)一分裂,這樣,分裂后新的葉節(jié)點(diǎn)仍然處于同一層.分裂的同時(shí),Hilbert的階也隨之增加1階.算法4是葉節(jié)點(diǎn)分裂的偽代碼.

算法4.SplitSpace(ns)

輸入:要分裂的四叉樹的葉節(jié)點(diǎn)ns;

輸出:分裂成功標(biāo)識flag.

Begin //na,nb,nc,nd為葉節(jié)點(diǎn)ns分裂的四個(gè)子節(jié)點(diǎn)

1.keyOfNa←Hilbert(center points of na);

2.keyOfNb←Hilbert(center points of nb);

3.keyOfNc←Hilbert(center points of nc);

4.keyOfNd←Hilbert(center points of nd);

5.for each point p in ns do

6.if p in na then

7.pointsOfNa.add(p);

8.else if p in nb then

9.pointsOfNb.add(p);

10. else if p in nc then

11.pointsOfNc.add(p);

12. else if p in nd then

13.pointsOfNd.add(p);

14. end if

15.end for

16.flagNa←Insert(keyOfNa,pointsOfNa);

17.flagNb←Insert(keyOfNb,pointsOfNb);

18.flagNc←Insert(keyOfNc,pointsOfNc);

19.flagNd←Insert(keyOfNd,pointsOfNd);

20.if Na & Nb & Nc &Nd is true then

21.flag←ClearDataPoint(keyOfNs);

22.else flag←false;

23.return flag

End

3.4 范圍查詢算法

算法5是范圍查詢的偽代碼,可用于HBase和Cassandra等云數(shù)據(jù)庫.(pa,pb,pc,pd)是范圍查詢(查詢矩形)的四個(gè)頂點(diǎn).Hilbert將空間等分成網(wǎng)格,每個(gè)網(wǎng)格都有一個(gè)鍵值.算法5首先計(jì)算了所有與查詢矩形相交的網(wǎng)格的坐標(biāo).GridKeys是存儲包含在查詢矩形范圍內(nèi)的網(wǎng)格的鍵值集合.每一個(gè)網(wǎng)格c的坐標(biāo),經(jīng)過ComputeKeys()方法計(jì)算出該網(wǎng)格對應(yīng)的Hilbert鍵值,并把該鍵值加到GridKeys列表中.然后用GetContainPoints()方法從路由表中找到網(wǎng)格鍵值對應(yīng)的葉子節(jié)點(diǎn),并從葉子節(jié)點(diǎn)中找到數(shù)據(jù)點(diǎn).算法5中1-6行代碼將符合矩形查詢條件的鍵值找到;7-10行根據(jù)網(wǎng)格的鍵值,從路由表中獲得葉節(jié)點(diǎn)信息并從葉節(jié)點(diǎn)把符合條件的數(shù)據(jù)取出.

圖2 范圍查詢Fig.2 Range query

具體查詢例子如圖2所示,圖中粉色部分是范圍查詢,黑色圓點(diǎn)是空間數(shù)據(jù)點(diǎn).通過查詢矩形得到與范圍查詢相交的網(wǎng)格的坐標(biāo),即{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)};然后得到每個(gè)坐標(biāo)的Hilbert鍵值,即{(0,1,14,3,2,13};然后根據(jù)路由表得到對應(yīng)的葉節(jié)點(diǎn),并從云數(shù)據(jù)庫中取出數(shù)據(jù),把不符合的數(shù)據(jù)從查詢結(jié)果里刪除.

算法5.RangeQuery(pa,pb,pc,pd)

輸入:查詢范圍(查詢矩形)的四個(gè)頂點(diǎn)pa,pb,pc,pd;

輸出:查詢得到的數(shù)據(jù)點(diǎn)集合Result.

Begin

1.Coordinate← ComputeGrid(pa,pb,pc,pd);

2.Keys← φ;

3.Result← φ;

4.for each Coordinate c ∈Coordinate do

5.GridKeys←GridKeys ∪ComputeKeys(c);

6.end for

7.for each GridKeys k ∈GridKeys do

8.Result←Result ∪GetContainPoints(k);

9.end for

10.return Result;

End

4 實(shí)驗(yàn)和分析

本節(jié)通過仿真實(shí)驗(yàn)比較三種索引技術(shù)的效率高低.這三種索引技術(shù)分別Hilbert曲線、MD-HBase(簡稱MD)和HPR-index(簡稱HPR).仿真實(shí)驗(yàn)的數(shù)據(jù)庫版本為Cassandra1.0.10,每臺物理服務(wù)器的配置為2G內(nèi)存,500G硬盤,操作系統(tǒng)為64位的Ubuntu 8.04.4.每臺物理服務(wù)器建兩個(gè)虛擬節(jié)點(diǎn),Cassandra環(huán)上一共運(yùn)行十個(gè)虛擬節(jié)點(diǎn).本實(shí)驗(yàn)采用的仿真數(shù)據(jù)生成器[15]能產(chǎn)生均勻分布和正態(tài)分布兩種數(shù)據(jù)分布.得到多維均勻分布的方法僅是在每一維度上都產(chǎn)生均勻分布.生成多維正態(tài)分布的方法是先得到多維的均勻分布,然后用Box-Muller 算法[16]轉(zhuǎn)變?yōu)榉恼龖B(tài)分布的數(shù)據(jù),此時(shí)參數(shù)μ=0,σ2=1.查詢范圍在邊長為1×106數(shù)據(jù)單位的正方形內(nèi)生分別生成2×105,5×105,7×105和1×106個(gè)數(shù)據(jù)單位的均勻數(shù)據(jù)集4個(gè),正態(tài)分布數(shù)據(jù)集4個(gè),數(shù)據(jù)集如圖3(a)和圖3(b)所示.為了研究數(shù)據(jù)偏斜情況下的查詢效率,取上述正態(tài)分布數(shù)據(jù)集邊長為1×106個(gè)數(shù)據(jù)單位的正方形坐標(biāo)為A(4×105,4×105)、B(4×105,6×105)、C(6×105,6×105)、D(6×105,4×105)的四個(gè)點(diǎn)所圍成的小正方形內(nèi)的區(qū)域稱為正態(tài)分布密集區(qū),如圖3(b)所示,其余區(qū)域稱為正態(tài)分布稀疏區(qū).每次實(shí)驗(yàn)取100次查詢結(jié)果所耗費(fèi)時(shí)間的平均值作為實(shí)驗(yàn)結(jié)果.文獻(xiàn)[1]證明在同樣的實(shí)驗(yàn)條件下,Hilbert階數(shù)o=7時(shí)查詢效率最高,同樣條件下MD算法的參數(shù)M設(shè)置為2500時(shí)查詢效率最高.因此,所有實(shí)驗(yàn)中將HPR和Hilbert的階數(shù)o均設(shè)置為7,MD算法的參數(shù)M設(shè)置為2500.

圖3 數(shù)據(jù)分布Fig.3 Data distribution

4.1 不同查詢范圍的查詢效率比較

當(dāng)數(shù)據(jù)量固定為1×106而查詢范圍不同時(shí),考察三種索引查詢效率情況.圖4給出了數(shù)據(jù)均勻分布情況下三種索引的查詢效率;圖5給出了數(shù)據(jù)正態(tài)分布密集區(qū)情況下三種索引的查詢效率;圖6給出了在數(shù)據(jù)正態(tài)分布稀疏區(qū)三種索引的查詢效率.從圖中可以看出,數(shù)據(jù)正態(tài)分布密集區(qū)條件下三種索引的查詢時(shí)間最長,數(shù)據(jù)稀疏區(qū)三種索引的查詢時(shí)間最短,數(shù)據(jù)正態(tài)分布時(shí)三種索引的查詢時(shí)間介于前兩者之間.查詢范圍越大,三種索引的查詢時(shí)間越長,原因是需要讀取數(shù)據(jù)的節(jié)點(diǎn)的數(shù)量增加.其中Hilbert在查詢范圍較小時(shí)查詢效率與HPR相近,高于MD索引.但當(dāng)查詢范圍較大時(shí),Hilbert查詢時(shí)間增長較快,效率急速下降.MD索引當(dāng)查詢范圍較大時(shí),相比Hilbert而言查詢效率下降較慢,優(yōu)勢較明顯.當(dāng)查詢范圍不斷增大時(shí),HPR索引的查詢效率優(yōu)于Hilbert和MD.

圖4 數(shù)據(jù)均勻分布和不同查詢范圍條件下索引的查詢效率Fig.4 Query efficiency of different query size under uniform distribution

圖5 正態(tài)分布密集區(qū)和不同查詢范圍條件下索引的查詢效率Fig.5 Query efficiency of different query size under Normal-dense distribution

圖6 正態(tài)分布稀疏區(qū)和不同查詢范圍條件下索引的查詢效率Fig.6 Query efficiency of different query size under Normal-sparse distribution

4.2 不同數(shù)據(jù)量的查詢效率比較

當(dāng)數(shù)據(jù)查詢范圍固定為1×105時(shí),數(shù)據(jù)量不同條件下考察三種索引查詢效率情況.當(dāng)數(shù)據(jù)量分為2×105、5×105、7×105和1×106時(shí),圖7給出了在數(shù)據(jù)均勻分布情況下三種索引的查詢效率;圖8給出了在數(shù)據(jù)正態(tài)分布密集區(qū)情況下三種索引的查詢效率;圖9給出了在數(shù)據(jù)正態(tài)分布稀疏區(qū)三種索引的查詢效率.從圖中可以看出,數(shù)據(jù)量越大,三種索引的查詢時(shí)間越長,原因是需要讀取數(shù)據(jù)的節(jié)點(diǎn)的數(shù)量增加.其中Hilbert在數(shù)據(jù)均勻分布條件下查詢效率與MD相近,低于HPR索引.但當(dāng)數(shù)據(jù)偏斜時(shí),Hilbert查詢時(shí)間增長較快,效率急速下降,此時(shí)MD的查詢效率明顯優(yōu)于Hilbert,但兩者均低于HPR.綜上所述,當(dāng)數(shù)據(jù)量不斷增大時(shí),HPR索引的查詢效率優(yōu)于Hilbert和MD.

4.3 插入與刪除操作效率比較

圖7 數(shù)據(jù)均勻分布和不同數(shù)據(jù)量條件下的索引查詢效率Fig.7 Query efficiency of different data size under uniform distribution

圖8 正態(tài)分布密集區(qū)和不同數(shù)據(jù)量條件下索引的查詢效率Fig.8 Query efficiency of different data size under Normal-dense distribution

圖9 正態(tài)分布稀疏區(qū)和不同數(shù)據(jù)量條件下索引的查詢效率Fig.9 Query efficiency of different data size under Normal-sparse distribution

圖10 插入操作吞吐量比較Fig.10 Insertion throughput comparison

支持大吞吐量的數(shù)據(jù)插入操作對支撐大量基于位置的服務(wù)而言至關(guān)重要.實(shí)驗(yàn)通過Cassandra環(huán)上的十個(gè)虛擬節(jié)點(diǎn)上評估了數(shù)據(jù)插入性能.圖10所示,插入吞吐量是系統(tǒng)負(fù)載的函數(shù).實(shí)驗(yàn)將負(fù)載生成器的數(shù)量由200個(gè)增加到500個(gè),500個(gè)增加到700個(gè),最后增加到1000個(gè),其中每個(gè)負(fù)載器產(chǎn)生每秒1000次的插入負(fù)載.實(shí)驗(yàn)使用參數(shù)為μ=0、σ2=1的正態(tài)分布的仿真數(shù)據(jù)集.使用仿真數(shù)據(jù)集便于調(diào)整數(shù)據(jù)的偏斜度.實(shí)驗(yàn)表明,三種方法均顯示了良好的擴(kuò)展性,插入數(shù)據(jù)吞吐量至少達(dá)到了每秒150k個(gè)空間數(shù)據(jù)點(diǎn).MD索引插入吞吐量偏低的原因是因?yàn)樗牟鏄涔?jié)點(diǎn)分裂的開銷較大,分裂一個(gè)節(jié)點(diǎn)MD平均需要40秒的時(shí)間.Hilbert不需要分裂節(jié)點(diǎn),而HPR-index只有在特殊情況下才統(tǒng)一分裂所有節(jié)點(diǎn),所以兩者的插入吞吐量相對較高.三種索引的刪除數(shù)據(jù)吞吐量均比各自的插入數(shù)據(jù)吞吐量高,如圖11所示,它們的性能對比與插入數(shù)據(jù)吞吐量與圖10相似.MD索引刪除數(shù)據(jù)吞吐量低的原因是四叉樹的合并開銷較大.

5 結(jié) 論

本文提出的多維索引HPR用于在云數(shù)據(jù)管理系統(tǒng)Cassandra上執(zhí)行范圍查詢.多維索引HPR用桶PR四叉樹來構(gòu)建基本索引結(jié)構(gòu),通過Hilbert鍵值來快速定位數(shù)據(jù).此外,還設(shè)計(jì)新的空間范圍查詢算法、插入和刪除算法.實(shí)驗(yàn)結(jié)果表明,多維索引HPR查詢效率優(yōu)于Hilbert和MD索引,尤其是在數(shù)據(jù)偏斜的情況下.

圖11 刪除操作吞吐量比較Fig.11 Deletion throughput comparison

：

[1] Wei Ling-yin,Hsu Ya-ting,Peng Wen-chih,et al.Indexing spatial data in cloud data managements[J].Pervasive and Mobile Computing,2014,15:48-61.

[2] Fay C,Jeffrey D,Sanjay G,et al.Bigtable:a distributed storage system for structured data[C].Proceedings of the 7th Symposium on Operating Systems Design and Implementation,CA,2006:205-218.

[3] Lakshman A,Malik P.Cassandra:a decentralized structured storage system[J].ACM SIGOPS Operating Systems Review,2010,44(2):35-40.

[4] Hanan S.Foundations of multidimensional and metric data structures[M].Beijing:Tsinghua University Press,2011:28-48.

[5] Nikolett B,Amalia D,Krisztián N,et al.Quad-kd trees:a general framework for kd trees and quad trees[J].Theoretical Computer Science,2016,616(2):126-140.

[6] Wang Jin-bao,Wu Sai,Gao Hong,et al.Indexing multi-dimensional data in a cloud system[C].Proceedings of the ACM SIGMOD/PODS Conference,2010:591-602.

[7] Shoji N,Sudipto D,Divyakant A,et al.MD-HBase:design and implementation of an elastic data infrastructure for cloud-scale location services[J].Distributed and Parallel Databases,2013,31 (2):289-319.

[8] Ma You-zhong,Meng Xiao-feng.Research on indexing for cloud

data management[J].Journal of Software,2015,26(1):145-166.

[9] Hsu Ya-ting,Pan Yi-chin,Wei Ling-yin,et al.Key formulation schemes for spatial index in cloud data managements[C].Proceedings of the 13th IEEE Conference on Mobile Data Management,2012:21-26.

[10] Zhu Xia,Luo Jun-zhou,Song Ai-bo,et al.A multi-dimensional indexing for complex query in cloud computing[J].Journal of Computer Research and Development,2013,50(8):1592-1603.

[11] Liu Xing-ping,Luo Xiang-yun,Yang Hai.Querying research on efficient traffic data cloud-indexing technology based on HBase[J].Control Engineering of China,2016,23(4):560-564.

[12] Fu Zhong-liang,Hu Yu-long,Weng Bao-feng,et,al.M-quadtree index:a spatial index method forcloud storage environment based on modified quadtree coding approach[J].Acta Geodaetica et Cartographica Sinica,2016,45(11):1342-1351.

[13] Liu Yue,Li Jin-tao,Hu Song-lin.A cost-based splitting policy search algorithm for Hive multi-dimensional index[J].Journal of Computer Research and Development,2016,53(4):798-810.

[14] Luo En-tao,Wang Guo-jun,Li Chao-liang.Research on clustering analysis of multi-dimensional remove-duplicate removal in big data[J].Journal of Chinese Computer Systems,2016,37(3):438-442.

[15] Pei Y,Za?ane O.A synthetic data generator for clustering and outlier analysis[R].Technical Report,TR06-15,Department of Computing Science,University of Alberta,2006.

[16] Box G E P,Muller M E.A note on the generation of random normal deviates[J].Annals of Mathematical Statistics,1958,29(2):610-611.

附中文參考文獻(xiàn)：

[4] 薩姆特.多維與度量數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)[M].北京:清華大學(xué)出版社,2011:28-48.

[8] 馬友忠,孟小峰.云數(shù)據(jù)管理索引技術(shù)研究[J].軟件學(xué)報(bào),2015,26(1):145-166.

[10] 朱 夏,羅軍舟,宋愛波,等.云計(jì)算環(huán)境下支持復(fù)雜查詢的多維數(shù)據(jù)索引機(jī)制[J].計(jì)算機(jī)研究與發(fā)展,2013,50(8):1592-1603.

[11] 劉星平,羅湘運(yùn),楊 海.基于HBase的高效交通數(shù)據(jù)云索引技術(shù)[J].控制工程,2016,23(4):560-564.

[12] 付仲良,胡玉龍,翁寶鳳,等.M-Quadtree索引:一種基于改進(jìn)四叉樹編碼方法的云存儲環(huán)境下空間索引方法[J].測繪學(xué)報(bào),2016,45(11):1342-1351.

[13] 劉 越,李錦濤,虎嵩林.基于代價(jià)估計(jì)的Hive多維索引分割策略選擇算法[J].計(jì)算機(jī)研究與發(fā)展,2016,53(4):798-810.

[14] 羅恩韜,王國軍,李超良.大數(shù)據(jù)環(huán)境中多維數(shù)據(jù)去重的聚類算法研究[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(3):438-442.