基于MIR樹的空間查詢驗證方法

任德志,陳炬光,王 勇,段曉冉,郝玉潔,吳曉華

(1.電子科技大學 信息與軟件工程學院,成都 610054; 2.電子科技大學 計算機科學與工程學院,成都 611731)

0 概述

隨著智能設備尤其是智能手機的普及,空間查詢成為人們日常生活的一個重要應用,例如查詢最近餐館、影院等的位置信息。與此同時,智能終端設備產生的大量數據被存儲到云端,為用戶提供專業化的查詢服務[1]。在外包服務場景下,原數據擁有者(Data Owner,DO)將數據提供給服務提供商(Service Provider,SP),并假設服務提供商服從HBC(Honest But Curious)模型,即當用戶向服務提供商發起查詢信息請求時,服務提供商將會嚴格遵從應用規范和協議返回用戶所需信息。但有時服務提供商會因為某種利益關系收集額外的數據信息,向用戶提供不真實或被篡改的查詢數據信息。

現有空間查詢方法主要有Top-k[2]、KNN[3]等,均可被抽象為空間多項式函數(Spatial Polynomial Function,SPF)查詢。空間多項式函數查詢是一種基于空間鄰近位置關系的信息查詢方式,其在實際應用中被廣泛應用,具有較強的普適性。

MIR樹是空間查詢結果可靠性、完整性、正確性驗證的主要索引數據結構,然而在數據查詢遍歷過程中,MIR樹的每一層倒排索引文件(Inverted File,IF)和相應的節點都要返回給查詢用戶,這帶來了較高的查詢時間和開銷成本。針對該問題,本文構造一種新的數據索引結構MRH樹,利用位圖來替換MIR樹中的倒排索引文件,從而降低用戶與服務提供商之間的通信開銷和計算時間。

1 相關工作

典型的數據外包服務場景模型如圖1所示。

圖1 數據外包服務場景

目前主流的查詢驗證技術有數字簽名鏈[4]和默克爾哈希(Merkle Hash,MH)樹[5]。數字簽名鏈是利用非對稱加密算法和信息散列算法對信息加密解密的過程,信息發送方利用私鑰對信息進行散列加密,也就是簽名,信息接收方則利用發送方的秘鑰對其進行解密,從而信息得到校驗。MH樹是一種二叉樹,其葉子節點包含數據關鍵字信息,通過自底向上對每一個節點進行哈希運算,得到根節點的哈希值,DO可以利用自己密鑰對根節點哈希值進行簽名,以保證數據信息的可靠性。

文獻[6-7]針對外包服務驗證場景,利用MIR樹作為查詢驗證的數據結構,提出一種基于Top-k查詢驗證方法,但實驗結果表明,利用MIR樹查詢驗證時存在較高的時間和資源開銷。文獻[8-9]在空間查詢驗證的方法中引入空間范圍關鍵詞查詢驗證,構造了一種MR樹。該樹是MB樹和R*樹結合的一種數據結構,能提高查詢驗證的效率。文獻[10]對MH樹中間節點的簽名方法進行優化,提出一種基于MH樹的查詢驗證方法,提高了查詢驗證效率并加快了MH樹的構造速度。文獻[11]提出一種VSS樹空間查詢驗證數據結構,利用邊界球的方法對樹進行區域劃分,減少查詢驗證樹的分支數量和樹的高度。實驗結果表明,該數據結構的查詢驗證及通信開銷優于MR樹。文獻[12-13]基于SAE模型,提出一種基于改進的B+樹和外包XML數據查詢驗證方案,利用B+樹構造的數據結構,有效地提高了查詢驗證速度,同時降低了認證數據結構(Authenticated Data Structure,ADS)的構造成本。文獻[14]提出一種優化MH樹模型方案,對MH樹部分中間節點進行簽名,將樹的葉子節點分為若干個組,每一組組成一顆較小的哈希樹。該方法提高了數據驗證的效率并降低了哈希樹的復雜度。文獻[15]提出一種針對文本關鍵字查詢的查詢驗證方法,通過將倒排索引文件插入MH樹中的每個節點中,基于MH樹構造相應的驗證對象(Verification Object,VO)。文獻[16-18]針對空間多用戶多關鍵字查詢進行了空間驗證研究,提出一種查詢驗證方案。本文提出一種新的ADS MRH樹,以降低空間查詢驗證中的VO開銷。

2 MIR樹與SPF查詢

2.1 MIR樹

MIR[19]樹是一種結合MH樹和IR[20]樹并且可驗證的數據索引結構,適用于空間關鍵字查詢,但在數據查詢遍歷過程中,MIR樹的每一層倒排索引文件和相應的節點都要返回給查詢用戶,導致巨大的通信成本和時間開銷。MIR樹的構造原理如圖2所示。在圖2(a)中零散分布著許多興趣點,各個相鄰的興趣點組成一個小區域的興趣點集合,圖2(b)是根據圖2(a)中的興趣點集合構成的MIR樹。

圖2 MIR樹構造示意圖

2.2 空間多項式函數查詢定義

隨著科技的快速發展,定位技術應用越來越廣泛,多數地點都能利用精確的定位技術獲得自己位置的詳細信息。在空間查詢驗證中,當某個地點攜帶查詢關鍵字信息時,該地點通常被稱為興趣點(Point of Interest,POI)。現實中POI可能是飯店、娛樂場所、醫療機構等。

3 MRH樹索引構造

3.1 位圖的構造

i=「((h/n)-1)?,j=h-i×n-1

(1)

3.2 MRH樹的構造

在MIR樹和位圖的基礎上,本文構造MRH樹來索引數據集D中的POI。在外包給SP之前,DO為數據集D中的每個POI構造自己的位圖RM。本文采用MRH樹的葉子節點代表興趣點Ii,每個葉子節點的哈希值都涵蓋了對應POI的id信息、空間位置λ和位圖RMIi,其計算方式為:

H(Ii)=h(Ii.id|Ii.λ|RMIi)

(2)

其中,“|”為級聯操作運算符,h(·)為單向哈希運算。

在構造MRH的過程中,MRH樹中的每一個葉子節點ei是一個最小外接矩形區域,會根據其所處的空間位置覆蓋一組POI,并與一個位圖RMei相關聯。位圖RMei是葉子節點ei相對應的位圖,其計算方式為:

RMei=RMI1⊕RMI2⊕…⊕RMIm

(3)

其中,I1,I2,…,Im是該最小外接矩形區域所覆蓋的POI,“⊕”表示位圖的“按位或”操作運算。葉子節點ei的哈希值為:

H(ei)=h(>RMei|H(I1)|H(I2)|…|H(Im))

(4)

MRH樹的中間節點ej根據其所處位置關系將附近POI組成的一個最小矩形區域作為其孩子節點,并與位圖RMej相關聯。位圖RMej是MRH樹中間節點ej所對應的位圖,其計算方式為:

RMei=RMe1⊕RMe2⊕…⊕RMel

(5)

其中,e1,e2,…,el為中間節點ej的所有子節點。中間節點ej的哈希值為:

H(ej)=h(RMej|H(e1)|H(e2)|…|H(el))

(6)

通過從葉子節點到根節點逐層構建MRH樹,能夠得到MRH樹根節點值eroot的位圖RMeroot及其哈希值H(eroot)。DO用自己的私鑰對哈希值H(eroot)簽名,并將數據提供給SP。

本文提出的MRH樹與MIR樹相比,可以大幅降低MIR樹中倒排索引文件通信代價。根據圖2(a)構造的MRH樹如圖3所示。

圖3 根據圖2(a)構造的MRH樹

4 VO生成算法與真實性驗證

4.1 VO生成算法設計

在構建VO生成算法之前,本文首先闡述用戶查詢算法執行過程。該算法是基于貪心策略來構建的,其IR樹中節點ei的權值ωei計算公式為:

(7)

其中,dist(ei,Q)表示節點ei與查詢點Q之間的距離,|ei.ψ∩CurK|表示節點ei中含有的關鍵詞ei.ψ和當前查詢關鍵詞集合CurK中具有相同關鍵詞的個數。

當用戶查詢所需信息時,查詢算法利用最小優先隊列H存放即將遍歷的節點權值,并按照節點權值大小進行排序。將IR樹的根節點放進最小優先隊列H中,每次從隊列中取出最小的值進行測驗:

1)如果從隊列中取出的元素cur是一個節點,則查詢算法用式(7) 計算該節點的孩子節點的權重值并放入隊列H中。

2)如果取出的元素是一個POI,查詢算法將其加入結果集中,重新更替查詢關鍵詞Q.ψ(Q.ψ=Q.ψcur.ψ)。該算法用式(8)更替隊列H中全部關鍵詞和cur.ψ有交集元素的權重值。

(8)

其中,er是某個節點(含有關鍵字信息),關鍵詞集合PreK是上一次將POI放入結果集后的查詢關鍵詞集合,即PreK=Q.ψ,關鍵詞集合CurK是本次將POI放入結果集后的查詢關鍵詞集合,即CurK=Q.ψcur.ψ,ω′er是上一次將POI放入結果集時er的權重值。僅當結果集CurK中或最小優先隊列H中沒有元素時,該算法程序才會停止執行,并將產生的查詢結果返回給用戶。

根據上述查詢算法構造VO生成算法,通過VO和結果集R,即可驗證查詢結果的真實性,VO生成算法偽代碼如算法1所示。

算法1VO生成算法

輸入查詢點Q

輸出開銷值Cost,結果集R,驗證結構VO

Root←MRH樹的根節點

PreK←Q.ψ,CurK←Q.ψ,R←?,Cost←?,VO←?

while(CurK非空且Root非空) do

cur←Root.pop

If (cur是POI) do

Cost←ωcur

R←cur

PreK←CurK,CurK←CurKcur.ψ

If (CurK為空) do

break

endif

For (遍歷Root每個元素e) do

If (e.ψ與cur.ψ的交集非空) do

根據式(8)更新e的權重值We

endif

重新調整Root中權值排序

endfor

endif

else

For (遍歷cur中每個孩子e) do

VO←e

If (e.ψ與CurK的交集非空) do

根據式(7)計算e的權重值We

Root←e

endif

endfor

endelse

endwhile

在VO構造算法過程中,首先將待遍歷的MRH樹節點按順序全部放入隊列Root中,然后依次取出節點的值,當彈出的是非葉子節點時,需要將該節點的子節點放入VO中,方便記錄查詢,因為該節點的子節點肯定包含需要的查詢信息。當彈出的是POI時,將其放入結果集R中,并重新對Root中剩余節點值進行排序。當查詢的關鍵字集合CurK為空時,表明關鍵字查詢完畢,即算法結束,VO構建完畢。

4.2 查詢真實性驗證算法

本文設計驗證算法對算法1的結果進行可靠性、正確性和完整性驗證。

1)可靠性驗證:用戶根據算法1得到的VO和結果集R,重新構造一顆完整的MRH樹,并從下到上計算每一層節點的哈希值,直到計算出根節點哈希值。然后,用戶通過DO提供的公鑰與計算出的根節點哈希值進行對比,判斷查詢結果是否可靠。

2)完整性驗證:在結果集R中的POI,其攜帶的關鍵詞并集必須包含查詢點關鍵字的總和,否則驗證算法會立刻停止執行,并返回用戶“驗證結果錯誤”。

3)正確性驗證:該驗證算法是根據貪心算法的思想每次選出最符合的POI,并且會把該POI的兄弟節點也加入VO中,依據算法1構造出的結果集R和VO,重新執行算法1進行驗證,其偽代碼如算法2所示。

算法2VO驗證算法

輸入查詢點Q,原始根節點哈希值ort,結果集R,驗證結構VO

輸出驗證結果Auth

1.根據VO和R計算MRH樹的根節點哈希值mrt

2.If (ort不等于mrt) do

3.Return Auth←False

4.if(R中POI的關鍵字沒有包含查詢關鍵字的集合)do

5.Return Auth←False

6.PreK←Q.ψ,CurK←Q.ψ

7.For (R中的每個POI Pi) do

8.HR←根據式(7)計算Pi的權值

9.for(VO中每個節點ei)do

10.HV←根據式(7)計算ei的權值

11.while(CurK非空) do

12.cur←HR.pop

13.cur′←HV.pop

14.If(ωcur大于ωcur')do

15.return Auth←False

16.else

17.PreK←CurK,CurK←CurKcur.ψ

18.for(HR中的每個POI p)do

19.If(p.ψ與cur.ψ交集非空)do

20.根據式(8)計算新的POI p的權值Wp

21.endif

22.重新調整HR中每個POI排序

23.endfor

24.for(HV中每個節點e)do

25.If(e.ψ與cur.ψ交集非空)do

26.根據式(8)計算節點e 的權值We

27.endif

28.重新調整HV權值排序

29.endfor

30.endif

31.endwhile

32.if(HR非空)do

33.return Auth←False

34.endif

35.return Auth←True

VO驗證算法在執行過程中:

1)驗證查詢結果的可靠性(第1行～第3行)。如果原始根節點哈希值與MRH樹的根節點值一致,驗證完成;否則,驗證失敗。

2)驗證結果的完整性(第4行～第5行)。如果結果集R包含查詢的關鍵字集合,驗證完成;否則,驗證失敗。

3)驗證結果的正確性(第7行～第34行)。

(1)利用查詢算法的性質,HR和HV分別存放結果集R的權值和VO的權值,在驗證算法循環中檢驗當前查詢關鍵字是否為空,來保證算法的正確性(第7行～第30行)。

(2)當驗證算法結束時,判斷結果集隊列是否為空,以便檢驗不會有多余的POI被放入結果集R中(第32行～第34行)。

當VO驗證算法的每一步都通過執行時,就可以驗證算法1的可靠性、完整性和正確性,同時也驗證了查詢結果的真實性。

5 實驗與結果分析

5.1 實驗配置

本文采用數據集合D來驗證算法1和算法2的真實性和有效性。數據集合D來源于2個數據集:

1)公開地圖OpenStreetMap(www.openstreetmap.org)的大西洋城區域。數據集采集方式是利用一個矩形區域覆蓋一塊興趣點,矩形區域的左頂點和右下角坐標分別為(-74.978 9,38.920 0)和(-74.330 0,39.430 0),其中大部分興趣點是矩形區域中的建筑物,少部分是空間區域,其包含地理位置的經緯度信息等。

2)合成數據集,其數據來源同上,矩形區域的左頂點和右下角坐標分別(-84.435 0,33.729 6)和(-84.344 4,33.794 6),其中與每個POI相關聯的關鍵字來自于美國地名委員會(geonames.usgs.gov),包含180多萬個POI和攜帶20多萬個不同的關鍵詞,這些關鍵字包含地理名稱等信息,與POI隨機相關聯。

本文實驗的PC機采用Windows7系統,開發環境為Eclipse,編程語言為Java。利用POI所攜帶的平均關鍵詞量|I.ψ|和關鍵字數量|Q.ψ|對本文構造的MRH樹進行性能評估,在變量POI個數和查詢關鍵字數量不同的情況下,分析VO大小的增長情況。VO大小表示SP與用戶之間的通信開銷,VO越大表示通信所需帶寬越大,即表明消耗的資源和時間也就越多。

5.2 實驗結果

5.2.1 VO空間開銷與興趣點規模的關系

本實驗通過興趣點數量的增大,觀察VO開銷的變化,結果如圖4所示。其中,每個POI平均包含10個關鍵字,查詢點的關鍵字設為4個。

圖4 VO隨興趣點數量變化曲線

從圖4可以看出,隨著興趣點數量的增大,其包含的關鍵字數量也增多,MIR樹和MRH樹的VO也呈增長的趨勢,并且不僅MIR樹的初始VO開銷比MRH樹高,而且其VO增長率明顯比MRH樹的增長率大,即MIR樹的帶寬和時間開銷均比MRH樹高。這是因為MIR樹中的每個節點都含有開銷代價較大的倒排索引文件,而本文構造的MRH樹的每個節點則使用開銷代價較小的位圖。

5.2.2 VO空間開銷與POI平均關鍵字數量關系

本實驗選取100萬個POI作為變量測驗數據,查詢關鍵字設為4個。通過增加POI攜帶的平均關鍵字數量,觀察VO開銷的變化趨勢,結果如圖5所示。

圖5 VO隨POI攜帶平均關鍵詞數量變化曲線

Fig.5 Curve of VO changing with the average number of keywords carried by POI

從圖5可以看出,隨著POI攜帶的平均關鍵詞數量逐漸增大,MIR樹和MRH樹的VO開銷都呈增長的趨勢。同樣的,MIR樹的初始VO比MRH樹高,其增長率也比MRH樹高。這說明隨POI攜帶的平均關鍵詞數量的增長,MIR樹在空間查詢中帶寬和時間的開銷代價都比MRH樹大。

5.2.3 VO空間開銷與查詢關鍵字數量關系

本實驗選取100萬個POI作為測驗數據,每個POI攜帶關鍵字個數為10個,通過增加查詢關鍵字數量,觀察VO開銷值的變化,結果如圖6所示。

圖6 VO隨查詢關鍵字數量變化曲線

Fig.6Curve of VO changing with the number ofquery keywords

從圖6可以看出,隨著查詢關鍵字的逐漸增多,MIR樹和MRH樹的VO開銷也增大,同樣的,MIR樹的初始VO開銷比MRH樹高,且其VO增長率比MRH樹要高。這表明隨查詢關鍵字數量的逐漸增大,MIR樹的開銷比MRH樹更高。

5.2.4 VO算法正確性驗證

本文對VO算法的正確性進行了相應的實驗驗證。本實驗分2組,第1組實驗包括5個正確實驗數據集,第2組實驗包括5個隨機攜帶10%～20%虛假POI的數據集。實驗以通過的實驗數據占總的實驗數據的百分比來評估算法的正確性,對每一組實驗結果求均值。本文進行了3次實驗,結果如圖7所示。在3次實驗中,第2組實驗數據分別攜帶10%、15%、20%的虛假POI。從圖7可以看出,在3次實驗中第1組正確率均達100%,因為第2組實驗數據攜帶虛假的POI,其正確率為90%、85%、80%。實驗結果證明了VO查詢算法的可靠性和完整性。

圖7 查詢算法正確率

6 結束語

在MIR樹的基礎上,本文構造一種數據結構MRH樹,利用位圖來替代MIR樹中高代價的倒排索引文件數據結構,并設計VO生成算法和VO驗證算法,驗證MRH樹在空間查詢中的可靠性、正確性和完整性。在POI規模、查詢關鍵字數量與POI攜帶關鍵字個數不同的情況下分別進行實驗,結果表明,MRH樹的通信開銷和計算時間均低于MIR樹。然而MRH樹仍將查詢關鍵字信息嵌入在樹的每個節點中,導致空間查詢驗證的開銷較大,后續將采用其他驗證數據結構進一步降低空間查詢驗證的開銷。