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

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

1 引 言

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

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

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

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

2 相關(guān)工作

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

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

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

線性索引技術(shù)通過將多維數(shù)據(jù)降維到一維數(shù)據(jù)來進行索引,主要的技術(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]在每個云節(jié)點的本地數(shù)據(jù)上建立R樹索引,并動態(tài)選擇一部分節(jié)點發(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上實現(xiàn)海量偏斜數(shù)據(jù)(skewed data)的多屬性查詢.該技術(shù)采用R+樹將數(shù)據(jù)劃分為互不相交的矩形單元,這些矩形存在R+樹的葉節(jié)點上.然后再將整個空間分成若干個互不相交的網(wǎng)格,利用Hilbert技術(shù)將這些網(wǎng)格進行編碼,并將矩形單元與網(wǎng)格的相交關(guān)系記錄到KeyTable表中.KR-index存在結(jié)點頻繁重新劃分、插入和刪除效率較低等問題.本文提出的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ù)進行數(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ū)間查詢等功能,但大多存在索引維護代價高,解決方案較為復(fù)雜等問題,特別是當數(shù)據(jù)分布不均勻時效率普遍偏低.因此,需要改進現(xiàn)有索引技術(shù)或提出新的多維索引技術(shù),使之具有較高效的偏斜數(shù)據(jù)查詢功能,維護代價低,實現(xiàn)方案較簡單等特點.

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

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

3.1 HPR-index概述

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

3.2 插入和刪除算法

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

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

算法1.SubspaceLookup(p)

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

輸出:包含點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ù)點 p=(x,y),x和y分別是點p的橫坐標和縱坐標;

輸出:插入成功標識flag.

Begin

1.key← SubspaceLookup(p);

2.flag←InsertToPRTree(key,p);

3.return flag

End

算法3.DeletePoint(p)

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

輸出:刪除成功標識flag.

Begin

1.key← SubspaceLookup(p);

2.flag←DeleteFromPRTree(key,p);

3.return flag

End

3.3 分裂算法

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

算法4.SplitSpace(ns)

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

輸出:分裂成功標識flag.

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

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

圖2 范圍查詢Fig.2 Range query

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

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

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

輸出:查詢得到的數(shù)據(jù)點集合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 實驗和分析

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

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

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

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

當數(shù)據(jù)查詢范圍固定為1×105時,數(shù)據(jù)量不同條件下考察三種索引查詢效率情況.當數(shù)據(jù)量分為2×105、5×105、7×105和1×106時,圖7給出了在數(shù)據(jù)均勻分布情況下三種索引的查詢效率;圖8給出了在數(shù)據(jù)正態(tài)分布密集區(qū)情況下三種索引的查詢效率;圖9給出了在數(shù)據(jù)正態(tài)分布稀疏區(qū)三種索引的查詢效率.從圖中可以看出,數(shù)據(jù)量越大,三種索引的查詢時間越長,原因是需要讀取數(shù)據(jù)的節(jié)點的數(shù)量增加.其中Hilbert在數(shù)據(jù)均勻分布條件下查詢效率與MD相近,低于HPR索引.但當數(shù)據(jù)偏斜時,Hilbert查詢時間增長較快,效率急速下降,此時MD的查詢效率明顯優(yōu)于Hilbert,但兩者均低于HPR.綜上所述,當數(shù)據(jù)量不斷增大時,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)重要.實驗通過Cassandra環(huán)上的十個虛擬節(jié)點上評估了數(shù)據(jù)插入性能.圖10所示,插入吞吐量是系統(tǒng)負載的函數(shù).實驗將負載生成器的數(shù)量由200個增加到500個,500個增加到700個,最后增加到1000個,其中每個負載器產(chǎn)生每秒1000次的插入負載.實驗使用參數(shù)為μ=0、σ2=1的正態(tài)分布的仿真數(shù)據(jù)集.使用仿真數(shù)據(jù)集便于調(diào)整數(shù)據(jù)的偏斜度.實驗表明,三種方法均顯示了良好的擴展性,插入數(shù)據(jù)吞吐量至少達到了每秒150k個空間數(shù)據(jù)點.MD索引插入吞吐量偏低的原因是因為四叉樹節(jié)點分裂的開銷較大,分裂一個節(jié)點MD平均需要40秒的時間.Hilbert不需要分裂節(jié)點,而HPR-index只有在特殊情況下才統(tǒng)一分裂所有節(jié)點,所以兩者的插入吞吐量相對較高.三種索引的刪除數(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è)計新的空間范圍查詢算法、插入和刪除算法.實驗結(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.

附中文參考文獻：

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

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

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

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

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

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

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