面向外包空間數據庫的范圍查詢驗證

胡曉燕,王靜宇,李海榮

1.內蒙古科技大學 工程訓練中心,內蒙古 包頭 014010; 2.內蒙古科技大學 網絡中心,內蒙古 包頭014010)(*通信作者電子郵箱hxy123@imust.cn)

面向外包空間數據庫的范圍查詢驗證

胡曉燕1*,王靜宇2,李海榮1

1.內蒙古科技大學 工程訓練中心,內蒙古 包頭 014010; 2.內蒙古科技大學 網絡中心,內蒙古 包頭014010)(*通信作者電子郵箱hxy123@imust.cn)

針對空間范圍查詢驗證方法(例如VR-tree和MR-tree)普遍存在驗證對象(VO)中包含大量的節點驗證信息,造成服務器到客戶端的傳輸代價較大以及客戶端驗證效率較低等問題,提出一種新的驗證索引結構(ADS)MGR-tree。首先利用拆分思想,通過在Grid-tree的葉子節點中嵌入R-tree,并結合Merkle哈希樹的驗證方法,極大地減小VO的大小,提高查詢和驗證的效率。在此基礎上,利用Hilbert曲線降維的特性,構建了優化的索引結構MHGR-tree,并提出一種過濾策略,進一步提高驗證的效率。實驗結果表明,所提方法具有更好的表現。在最好情況下,MHGR的VO大小和驗證時間僅為MR的63%和19%。

移動互聯網;位置服務;數據庫外包;查詢驗證;驗證對象

0 引言

對于數據庫外包服務或云計算服務,數據所有者(Data Owner, DO)失去對數據的直接操作和控制的能力,隨之產生諸多的數據安全隱患問題[1]。例如,在基于位置服務(Location-Based Service, LBS)查詢應用中,服務提供商(Services Provider, SP)是不可信的,商家為了贏得更多利益,在用戶(Client)不知情的情況下,與服務提供商相互勾結,篡改用戶的查詢結果或返回不完整的結果,損害用戶的權益。因此,如何向用戶提供真實結果以及驗證結果的正確性和可靠性顯得尤為重要。

目前,已經存在的查詢驗證方法主要分為兩類[2-12]:基于數字簽名技術和基于Merkle哈希樹(Merkle Hash Tree, MHT)。Pang等[3-4]提出了簽名鏈的方法,將相鄰數值連接形成一個簽名,通過重新計算結果集里每個數值的簽名并與標記的該數值簽名匹配,實現完整性的驗證。值得注意的是,數字簽名的方法在構建、存儲和更新數據索引時會造成較大的計算開銷。為了解決這個問題,Narasimha等[5]提出數字簽名聚合和鏈接的方法。由于傳統簽名驗證的方法都是驗證一維數據的可靠性,Cheng等[6]提出了基于空間分割的VKD-tree(Verifiable KD-tree) 和基于數據分割的VR-tree(Verifiable R-tree) 用于驗證多維數據庫查詢;MHT最廣泛的應用就是與其他索引結構相結合。對于一維數據查詢驗證,Li等[7]提出了MB-tree,通過在原始B+-tree的基礎上,每個節點上都包含了一個hash值,hash值的計算與MHT相似。為了進一步減小驗證對象(Verification Object, VO)的大小,Li等[7]又提出了MB-tree的變形EMB-tree。而針對多維數據查詢驗證,Yang等[8-9]在MHT和R*-tree的基礎上提出了MR-tree。相對于VR-tree,MR-tree在索引構建時間、存儲空間消耗、查詢處理和查詢驗證等性能方面都有了較大的提升。與此同時,Mouratidis等[10]提出了一種部分實體化摘要的策略(Partially Materialized Digest, PMD),可以與多種索引驗證結構結合,既可以應用于一維的數據查詢驗證,同時也適用于多維空間查詢驗證。謝晴晴等[11]利用PDM策略改進了MHT,實現了數據流范圍查詢驗證。除此之外,Hu等[12]實現了在進行范圍查詢驗證時,對查詢數據的隱私保護。

本文在MR-tree的研究基礎上,主要的工作包括以下三個方面:1)提出了一種改進的驗證方案,通過建立一種新的MGR-tree驗證索引結構,提升了MR-tree在驗證時間以及驗證對象大小等方面的性能；2)在此基礎上,提出了一種優化的索引結構MHGR-tree,通過用Hilbert曲線遍歷Grid-tree,降低了搜索空間的維度,從而加快了查詢和驗證的過程；3)基于Hilbert曲線一維線性的特性,提出一種優化的過濾策略,進一步加快了驗證的過程。

1 背景知識

定義1 單向哈希函數。給定哈希函數H(·),其作用于任意長度的字符串消息M,并返回固定長度的輸出H(M)。它滿足兩個性質:1)單向性。給定H(·)和H(M),反向計算M是不可行的。2)無碰撞性。給定M,找到消息M′滿足H(M)=H(M′)是不可行的。

例如,目前最常用的哈希函數是SHA1,其固定輸出160bit字符串消息。

定義2 數字簽名。簽名者產生一對密鑰(私有密鑰和公有密鑰),數據所有者利用私有密鑰對數字消息簽名,并將公有密鑰公開發布,消息接收者利用公有密鑰對接收到的消息進行可靠性驗證。

例如,目前最常用的公鑰加密算法是RSA(Rivest、Shamir和Adleman),其產生128B的消息簽名。

定義3Merkle哈希樹(MHT)。MHT[2]是一棵二叉樹,通過分層的自底向上計算所有節點的哈希值,并對根節點的哈希值進行數字簽名。

MHT的結構如圖1所示,其中涵蓋了四條數據記錄d1～d4,MHT的節點哈希值計算如下:1)如果節點N是葉子節點,其哈希值為H(dN),dN是數據記錄。2) 如果節點N是非葉子節點,其哈希值為H(dL|dR),dL和dR分別為節點N的左、右孩子節點的哈希值,“|”為字符串連接符。對于給定的范圍查詢Q(如圖1中矩形框所示),覆蓋數據記錄d1和d2,且d1和d2分別為范圍的左右邊界。VO(圖1中深色節點)包含了從根節點到左(右)邊界的路徑上節點的所有兄弟節點的摘要(如圖節點N2)。通過VO和查詢結果重新構建根節點的哈希值,如果與數據所有者簽名的哈希值匹配,則查詢結果是正確的,沒有被篡改。

圖1 MHT結構

2 范圍查詢驗證策略

本章主要介紹了MGR-tree和MHGR-tree索引結構的構建算法,并描述了在MHGR-tree上的查詢和驗證的過程。

2.1MGR-tree

在構建R-tree時,不同節點間的最小邊界矩形(MinimumBoundRectangle,MBR)會出現相交的情況；而且隨著數據量增大,節點間的MBR相交數目會增多。因此在執行范圍查詢時,會訪問不必要的節點,影響查詢的效率。若R-tree的結構比較大時,其產生的驗證對象VO也比較大,影響驗證的效率。而VO的大小是系統最重要的評價準則,它衡量了服務提供商到客戶端的傳輸代價,是系統性能的決定因素。通過實驗觀察,把R-tree拆分成多棵結構較小的R-tree時,對產生的驗證對象的大小有明顯的影響,結果如圖2所示(其中,數據基數為2×106,26×26和27×27表示分別將R-tree拆分成26×26和27×27棵小的R-tree)。

圖2 劃分的R-tree對VO大小的影響

從圖2中看出,隨著查詢范圍的增大,驗證對象VO包含的節點數目不斷增加。當查詢范圍大于5%時,基于拆分方法產生VO的大小很大程度上小于MR-tree的方法,并且隨著拆分的分辨率越高,產生的VO越小。基于上述的實驗事實,提出了一種新的驗證索引結構MGR-tree,該索引結構結合了Grid-tree和R-tree的結構特點,實現了對R-tree的有效劃分。MGR-tree的索引結構如圖3所示。

MGR-tree首先利用Grid-tree將搜索空間劃分網格,并將空間數據點映射到相應的網格內,然后用R-tree索引相應網格內的數據點。MGR-tree節點摘要的計算方法同文獻[7]相似,不同的是對Grid-tree節點摘要的處理。對于葉子節點,將節點內嵌套R-tree根節點摘要直接作為葉子節點摘要;而對于非葉子節點,則是將該節點的孩子節點摘要和節點網格區域連接,并利用哈希函數H(·)計算摘要。MGR-tree的構建過程如算法1所示。

算法1MGR-tree的構建算法。

輸入:空間區域R、空間數據點集P。 輸出:MGR-tree索引。

1)

將空間區域進行網格劃分(h為預設最大層數),設置整個空間區域為根節點。

2)

for(Grid-tree的層數≤h)

//在區域網格上建立Grid-tree

3)

依次將每個未劃分的節點區域分層。

4)

將空間數據點依次映射到相應的網格內(Grid-tree的葉子節點內)。

5)

if 節點內的點的數目不為0

6)

在每個網格對應的節點內嵌入R-tree。

7)

從MGR-tree的葉子節點層開始,直至根節點,計算每個節點的摘要。

8)

返回MGR-tree索引。

2.2 MHGR-tree

雖然MGR-tree在VO的大小和驗證效率等方面的性能都有了提高，尤其是減小的VO,不僅縮短了查詢驗證時間,同時也降低了傳輸開銷。但是,客戶端在驗證時,仍然要遍歷VO中所有節點的MBR或節點的網格區域判斷是否與查詢范圍相交。而且,隨著空間維度的增加,查詢判斷和驗證的代價都將增大。于是,在MGR-tree的基礎上,提出了優化的MHGR-tree索引結構。MHGR-tree是結合了MGR-tree和Hilbert曲線的一種索引結構,主要是通過將空間網格用Hilbert曲線遍歷,把Hilbert值映射到Grid-tree的每個節點,并在Grid-tree的每個非空葉子節點中嵌入一棵R-tree。MHGR-tree的索引結構如圖4所示。

圖3 MGR-tree的索引結構

圖4 MHGR-tree的索引結構

MHGR-tree通過Hilbert曲線將Grid-tree的多維空間降低到一維空間,并且通過Hilbert曲線的遍歷,每個節點都與相應的網格區域Hilbert值對應。如圖4所示,MHGR-tree的根節點對應網格區域為整個空間,即映射的Hilbert值區間為[0,15]；Grid-tree的葉子節點對應最小網格劃分(如N33),其Hilbert值區間為[10,10]。

當創建MHGR-tree時,在Grid-tree的基礎上,計算每個節點的Hilbert值范圍(NodeHilbertRange,NHR),與MGR-tree不同的是摘要的計算。對MHGR-tree節點摘要的計算分為兩個部分:Grid-tree和R-tree。其中,R-tree中的節點摘要計算方法與MGR-tree相同。對Grid-tree的葉子節點L,其摘要DigL計算為:

DigL=H(Dig(Root)|Hil(L))

其中:Dig(Root)為葉子節點內嵌入R-tree根節點的摘要,Hil(L)為葉子節點L所覆蓋網格的Hilbert值范圍。對Grid-tree的非葉子節點,其摘要DigI計算為:

DigI=H(Dig1|Dig2|…|Dig4|Hil(I))

其中:Dig1～Dig4表示該非葉子節點的孩子節點的摘要;Hil(I)表示非葉子節點I所覆蓋網格的Hilbert值范圍。在迭代計算到根節點后,利用數據所有者的私有密鑰對根節點的摘要進行簽名。

2.3 查詢處理

基于MHGR-tree進行多維范圍查詢時,主要考慮兩個部分:Grid-tree和R-tree的查詢過程。分別在兩棵樹上利用棧進行深度優先遍歷,判斷是否與查詢范圍相交,并將查詢結果和驗證時所必需的信息返回。VO的計算是在查詢的過程中進行的。VO中主要包含了在查詢過程與查詢范圍不相交的節點信息(對于Grid-tree,VO包含了節點摘要和Hilbert值范圍;對于R-tree,則包含了節點摘要和MBR)。具體過程如算法2所示。

算法2 MHGR-tree的查詢和創建VO算法。

輸入:空間查詢范圍R,MHGR-tree索引結構。 輸出:查詢結果集Result Set和VO。 1)將空間查詢范圍R映射為Hilbert值范圍(HilbertRange,HR) 2)將MHGR-tree根節點入棧S3)WhileS非空 4)S.pop();

//出棧 5)if Grid-tree節點是非葉子節點 6)if Grid-tree節點的NHR與HR相交 7)S.push(節點的孩子節點);

//入棧 8)else 將節點的摘要和NHR加入VO中 9)if Grid-tree節點是葉子節點 10)S.push(R-tree根節點)

//入棧 11)if R-tree節點是非葉子節點 12)if 節點MBR與范圍R相交 13)S.push(節點的孩子節點);

//入棧 14)else將節點的摘要和MBR加入VO中 15)if R-tree節點是葉子節點 16)if節點MBR與范圍R相交 17)將包含于范圍R內的點P加入Result Set 18)else 將范圍外的點P的摘要和MBR加入VO中 19)Return Result Set and VO

算法2描述了范圍查詢的完整過程,首先將查詢范圍R映射為Hilbert范圍(第1)行),從MHGR-tree的根節點開始判斷是否與查詢范圍相交(第2)～4行))。在Grid-tree上,通過判斷節點的Hilbert值范圍NHR與查詢范圍HR是否相交(第6)行),相對于多維屬性的相交判斷,一維Hilbert值的比較可以在一定程度上加快查詢。若相交,則將該節點的孩子節點入棧(第7)行);否則,將該節點的摘要和NHR加入VO(第8)行)。在R-tree上,則通過判斷節點的MBR是否與查詢范圍R相交。若與非葉子節點相交,則將該節點的孩子節點入棧(第11)～13)行);否則,將該節點的摘要和MBR加入VO(第14)行)。若與葉子節點相交,則將包含于范圍R內的所有點加入結果集Result Set(第15)～17)行);否則,將位于范圍R外的所有點的摘要和MBR加入VO中。以圖4為例,查詢Q從MHGR-tree的根節點開始迭代的訪問與深色矩形范圍框相交的節點{N,N3,N33,N34,R1,R2,R5,R6}(注:圖中只標記了與Q相交的一棵R-tree,未標記的R-tree的訪問節點未列舉)。訪問結束后,驗證對象VO包括{(N1.H,N1.NHR),(N2.H,N2.NHR),(N4.H,N4.NHR),(N31.H,N31.NHR),(N32.H,N32.NHR),(R3.H,R3.MBR),(R4.H,R4.MBR)}和結果集{P5,P6,P7,P8}。服務提供商將VO、Result Set和根節點摘要簽名傳輸給客戶端。

2.4 查詢驗證

在驗證查詢結果時,客戶端需要對結果進行可靠性驗證,主要包括以下兩個方面:1)完整性。所有被查詢范圍覆蓋的點P都包含在結果集Result Set中,沒有被遺漏。2)健壯性。返回的結果集中所包含的結果都是真實的結果,且沒有被篡改。客戶端借助驗證對象VO對查詢結果進行上述兩方面的驗證。

算法3 VO驗證算法。

輸入:Result Set和VO。 輸出:Verification Result。

1)

for(從R-tree 的葉子層開始至R-tree根節點所在層)

2)

計算R-tree每一層的節點的摘要至根節點

3)

for(從Grid-tree 的葉子層開始至Grid-tree根節點所在層)

4)

計算Grid-tree每一層的節點的摘要至根節點

5)

利用DO的公鑰密匙解密MHGR-tree根節點摘要的簽名

6)

if(計算的根節點摘要與DO簽名的摘要匹配)

7)

return true

8)

else return false

算法3描述了查詢結果健壯性驗證的過程。以圖3和圖4為例,客戶端首先掃描VO和Result Set,從R-tree的葉子層開始,通過{P5,P6}和{P7,P8}可以得到R5和R6的摘要和MBR。依次向上,通過VO中的{R3,R4}和計算的R5和R6可以得到R1和R2的摘要和MBR。最后計算得出R-tree根節點的摘要。在Grid-tree上,計算方法與R-tree類似,將R-tree節點的MBR用Grid-tree節點的Hilbert值范圍NHR替代,然后迭代計算MHGR-tree根節點的摘要,并與數據所有者簽名的摘要進行匹配。而在完整性驗證時,需要判斷：1)Result Set中的每個點都在查詢范圍R內；2)VO中的節點的NHR或MBR都不與查詢范圍R相交。

在驗證查詢結果的完整性和健壯性時,如果對于Result Set中的一點P被篡改,而P是計算根節點摘要時的組成部分,如果P的值是錯誤的,根據哈希函數的無碰撞性,計算得到的MHGR-tree根節點摘要與DO簽名的摘要必然不匹配,故不滿足健壯性。如果對于一點P,P包含于查詢范圍R內,但Result Set不包含P,在滿足健壯性前提下,P包含于VO中,故不滿足完整性驗證的條件。若P不包含于查詢范圍R內,但Result Set包含P,故也不滿足完整性驗證的條件。

3 優化策略

在驗證查詢結果的可靠性時,需要判斷VO中的Grid-tree的節點NHR不與查詢范圍的HR相交。如圖5所示,查詢Q所覆蓋網格對應的Hilbert值范圍為[27, 28],查詢產生的Grid-tree上的驗證對象VO為集合{N4,N34,N33,N324,N323,N322,N313,N314,N311,N2,N1}中每個節點的摘要和NHR,客戶端需要依次判斷節點NHR是否與查詢Q的HR相交。實際中,查詢范圍只覆蓋了少數的幾個網格,因此VO中包含了較多的冗余節點,而造成驗證時間變長和驗證效率下降。

圖5 基于Hilbert曲線的線性變化

于是,本文提出了一種優化的過濾策略,通過該策略可以減少客戶端的比較次數,縮短驗證時間。從圖5可看出,每個空間網格都被Hilbert曲線遍歷并被賦予一個Hilbert值,從而將具有空間位置關系的網格轉換為一維線性位置關系的網格。在判斷節點與查詢Q是否相交時,將空間坐標的判斷轉換為一維Hilbert值的比較,從而也加快了比較的速度,縮短了驗證時間。值得注意的是,通過Hilbert曲線的映射,每個空間網格間都具有一種線性關系,例如N4、N3和N2的Hilbert值范圍分別為[0, 15]、[16, 31]和[32, 47],它們之間的線性關系為N4

4 實驗與分析

為了評價提出的MGR-tree和MHGR-tree的表現,本文在一個真實的數據集CAR[7]上進行測試,其中CAR為California的道路分割,包含了2 096 702個不同位置的坐標點。在實驗中,將這些坐標點當作不同物體的位置。實驗在配置為IntelCore2DuoCPUE7500 2.93GHz和8GB內存的WindowsXP系統上運行。系統代碼用Java編寫,哈希函數采用160bit的SHA1算法,數字簽名采用128B的RSA算法。在構建MGR-tree和MHGR-tree時,Grid-tree的默認的樹的高度為7,查詢范圍默認為10%的空間覆蓋率,R-tree的節點大小設置為4 096B。

實驗中,主要針對如下兩個方面進行測試:1)查詢范圍對系統性能的影響;2)數據集大小對系統系能的影響；并且系統性能主要包含了VO的大小和驗證時間等方面。

實驗主要與文獻[7]方法(簡稱MR)進行對比,將本文提出的方法稱為MGR和MHGR。

隨著用戶查詢范圍的改變,系統性能會發生變化。實驗中測試了當查詢范圍在整個空間的1%至20%之間變化時,VO大小和驗證時間的變化,其中Grid-tree樹高h=7,數據量大小為2×106。從圖6可以看出,當查詢范圍很小時,MGR和MHGR較MR表現出了一定的優勢,隨著查詢范圍的增大,這種優勢更加明顯。尤其是,當查詢范圍發生變化時,MR的VO大小和驗證時間發生明顯改變,而MGR和MHGR與之相反。例如,當查詢范圍分別為1%和20%時,MR的VO大小和驗證時間的差值分別為756 KB和114 ms,而MHGR僅為474 KB和16 ms。值得注意的是,在最好情況下,MHGR的VO大小和驗證時間僅為MR的63%和19%。

如圖7所示,當數據量比較小時,MGR和MHGR在查詢時間、VO大小和驗證時間等方面已經明顯比MR要好。當數據量很大時,MGR和MHGR的優勢更加明顯,都保持了較低的水平。尤其是當數據量為400 000時,MHGR的VO大小和驗證時間僅為MR的33%和26%。

圖6 查詢范圍對不同算法在系統性能方面的影響(h=7,|D|=2×106)

圖7 數據量對不同算法在系統性能方面的影響(h=7,r=10%)

5 結語

隨著移動互聯網絡的普及和高速發展,例如4G網絡等,極大地推動了基于位置服務(LBS)的進展。而面對客戶日益復雜的查詢服務需求,數據所有者已無法滿足要求。為了更好地解決這個矛盾,將數據庫外包給LBS提供商成為了必然的選擇。但是,在LBS提供商給客戶提供更高級的查詢服務的同時,由于LBS提供商是不受信任的,為了提供可靠的查詢服務,LBS服務商應以一種可驗證的方式提供查詢服務,即客戶可以對查詢結果進行可靠性驗證。在大數據的背景下,如何快速響應查詢服務請求,以較小的數據傳輸代價給客戶提供更可靠的查詢結果變得至關重要。針對上述問題,提出新的索引結構MGR-tree,結合了Grid-tree和R-tree的特點,極大地改善了VO過于龐大的問題,降低了服務提供商和客戶之間的傳輸消耗,并且有效地縮短了驗證時間；在此基礎上,通過Hilbert的降維特性,還提出了優化的MHGR-tree,并提出了一種過濾策略,有效地改善了系統性能。實驗結果表明,在數據量和查詢范圍都比較大時,MGR-tree和MHGR-tree在VO大小和驗證時間等方面都表現出了明顯的優勢。

References)

[1] DEVANBU P, GERTZ M, MARTEL C, et al. Authentic third-party data publication[M]// THURAISINGHAM B, VAN DE RIET R, DITTRICH K R, et al. Data and Application Security. Berlin: Springer, 2000: 101-112.

[2] MERKLE R C. A certified digital signature [C]// CRYPTO 1989: Proceedings on Advances in Cryptology. Berlin: Springer, 1989: 218-238.

[3] PANG H H, TAN K L. Authenticating query results in edge computing [C]// Proceedings of the 20th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2004: 560-571.

[4] PANG H H, JAIN A, RAMAMRITHAM K, et al. Verifying completeness of relational query results in data publishing[C]// SIGMOD 2005: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2005: 407-418.

[5] NARASIMHA M, TSUDIK G. DSAC: integrity of outsourced databases with signature aggregation and chaining [C]// CIKM 2005: Proceedings of the 14th ACM International Conference on Information and Knowledge Management. New York: ACM, 2005: 235-236.

[6] CHENG W, PANG H H, TAN K. Authenticating multi-dimensional query results in data publishing [C]// DBSEC 2006: Proceedings of the 20th IFIP WG 11.3 Working Conference on Data and Applications Security. Berlin: Springer, 2006: 60-73.

[7] LI F, HADJIELEFTHERIOU M, KOLLIOS G, et al. Dynamic authenticated index structures for outsourced databases [C]// SIGMOD 2006: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2006: 121-132.

[8] YANG Y, PAPADOPOULOS S, PAPADIAS D, et al. Authenticated indexing for outsourced spatial databases [J]. The VLDB Journal, 2009, 18(3): 631-648.

[9] YANG Y, PAPADOPOULOS S, PAPADIAS D, et al. Spatial outsourcing for location-based services [C]// ICDE 2008: Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2008: 1082-1091.

[10] MOURATIDIS K, SACHARIDIS D, PANG H H. Partially materialized digest scheme: an efficient verification method for outsourced databases [J]. The VLDB Journal, 2009, 18(1): 363-381.

[11] 謝晴晴, 王良民.基于PMD的外包數據流范圍查詢驗證方案[J]. 計算機科學與探索, 2015, 9(10): 1209-1218.(XIE Q Q, WANG L M. Data stream range query authentication scheme based on PMD in outsourced database[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(10): 1209-1218.)

[12] HU H, XU J, CHEN G, et al. Authenticating location-based services without compromising location privacy [C]// SIGMOD 2012: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2012: 301-312.

This work is partially supported by the National Natural Science Foundation of China (61462056,71363040), the Natural Science Foundation of Inner Mongolia (2016MS0609).

HU Xiaoyan, born in 1980, M. S., lecturer. Her research interests include cloud computing, database management.

WANG Jingyu, born in 1976, Ph. D., associate professor. His research interests include cloud computing, information security.

LI Hairong, born in 1976, M. S., associate professor. Her research interests include cloud storage.

Range query authentication for outsourced spatial databases

HU Xiaoyan1*, WANG Jingyu2, LI Hairong1

(1. Engineering Training Center, Inner Mongolia University of Science and Technology, Baotou Nei Mongol 014010, China;2. Information and Network Center, Inner Mongolia University of Science and Technology, Baotou Nei Mongol 014010, China)

In existing spatial range query authenticating methods such as VR-tree and MR-tree, the transmission cost of the server to the client is high and the verification efficiency of the client is low because the Verification Object (VO) contains too much authentication information. To resolve these problems, a new index structure MGR-tree was proposed. First of all, by means of embedding a R-tree in each leaf node of Grid-tree, the size of VO decreased, and the efficiency of query and authentication was improved. In addition, an optimal index MHGR-tree which takes advantage of the property of Hilbert curve and a filter policy were proposed to accelerate the verification. Experimental results show that the proposed method has a better performance compared with MR-tree. In the best case, the verification object size and authentication time of MHGR are 63% and 19% of MR respectively.

mobile Internet; location-based service; database outsourcing; query authentication; Verification Object (VO)

2016- 10- 31;

2016- 12- 20。

國家自然科學基金資助項目(61462056,71363040);內蒙古自然科學基金資助項目(2016MS0609)。

胡曉燕(1980—),女,內蒙古涼城人,講師,碩士,主要研究方向:云計算、數據庫管理; 王靜宇(1976—),男,河南開封人,副教授,博士,CCF會員,主要研究方向:云計算、信息安全; 李海榮(1976—),女,內蒙古巴彥淖爾人,副教授,碩士,主要研究方向:云存儲。

1001- 9081(2017)04- 1021- 05

10.11772/j.issn.1001- 9081.2017.04.1021

TP311

A