基于MIR樹的空間查詢驗(yàn)證方法

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

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

0 概述

隨著智能設(shè)備尤其是智能手機(jī)的普及,空間查詢成為人們?nèi)粘Ｉ畹囊粋€(gè)重要應(yīng)用,例如查詢最近餐館、影院等的位置信息。與此同時(shí),智能終端設(shè)備產(chǎn)生的大量數(shù)據(jù)被存儲(chǔ)到云端,為用戶提供專業(yè)化的查詢服務(wù)[1]。在外包服務(wù)場(chǎng)景下,原數(shù)據(jù)擁有者(Data Owner,DO)將數(shù)據(jù)提供給服務(wù)提供商(Service Provider,SP),并假設(shè)服務(wù)提供商服從HBC(Honest But Curious)模型,即當(dāng)用戶向服務(wù)提供商發(fā)起查詢信息請(qǐng)求時(shí),服務(wù)提供商將會(huì)嚴(yán)格遵從應(yīng)用規(guī)范和協(xié)議返回用戶所需信息。但有時(shí)服務(wù)提供商會(huì)因?yàn)槟撤N利益關(guān)系收集額外的數(shù)據(jù)信息,向用戶提供不真實(shí)或被篡改的查詢數(shù)據(jù)信息。

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

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

1 相關(guān)工作

典型的數(shù)據(jù)外包服務(wù)場(chǎng)景模型如圖1所示。

圖1 數(shù)據(jù)外包服務(wù)場(chǎng)景

目前主流的查詢驗(yàn)證技術(shù)有數(shù)字簽名鏈[4]和默克爾哈希(Merkle Hash,MH)樹[5]。數(shù)字簽名鏈?zhǔn)抢梅菍?duì)稱加密算法和信息散列算法對(duì)信息加密解密的過(guò)程,信息發(fā)送方利用私鑰對(duì)信息進(jìn)行散列加密,也就是簽名,信息接收方則利用發(fā)送方的秘鑰對(duì)其進(jìn)行解密,從而信息得到校驗(yàn)。MH樹是一種二叉樹,其葉子節(jié)點(diǎn)包含數(shù)據(jù)關(guān)鍵字信息,通過(guò)自底向上對(duì)每一個(gè)節(jié)點(diǎn)進(jìn)行哈希運(yùn)算,得到根節(jié)點(diǎn)的哈希值,DO可以利用自己密鑰對(duì)根節(jié)點(diǎn)哈希值進(jìn)行簽名,以保證數(shù)據(jù)信息的可靠性。

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

2 MIR樹與SPF查詢

2.1 MIR樹

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

圖2 MIR樹構(gòu)造示意圖

2.2 空間多項(xiàng)式函數(shù)查詢定義

隨著科技的快速發(fā)展,定位技術(shù)應(yīng)用越來(lái)越廣泛,多數(shù)地點(diǎn)都能利用精確的定位技術(shù)獲得自己位置的詳細(xì)信息。在空間查詢驗(yàn)證中,當(dāng)某個(gè)地點(diǎn)攜帶查詢關(guān)鍵字信息時(shí),該地點(diǎn)通常被稱為興趣點(diǎn)(Point of Interest,POI)?，F(xiàn)實(shí)中POI可能是飯店、娛樂(lè)場(chǎng)所、醫(yī)療機(jī)構(gòu)等。

3 MRH樹索引構(gòu)造

3.1 位圖的構(gòu)造

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

(1)

3.2 MRH樹的構(gòu)造

在MIR樹和位圖的基礎(chǔ)上,本文構(gòu)造MRH樹來(lái)索引數(shù)據(jù)集D中的POI。在外包給SP之前,DO為數(shù)據(jù)集D中的每個(gè)POI構(gòu)造自己的位圖RM。本文采用MRH樹的葉子節(jié)點(diǎn)代表興趣點(diǎn)Ii,每個(gè)葉子節(jié)點(diǎn)的哈希值都涵蓋了對(duì)應(yīng)POI的id信息、空間位置λ和位圖RMIi,其計(jì)算方式為:

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

(2)

其中,“|”為級(jí)聯(lián)操作運(yùn)算符,h(·)為單向哈希運(yùn)算。

在構(gòu)造MRH的過(guò)程中,MRH樹中的每一個(gè)葉子節(jié)點(diǎn)ei是一個(gè)最小外接矩形區(qū)域,會(huì)根據(jù)其所處的空間位置覆蓋一組POI,并與一個(gè)位圖RMei相關(guān)聯(lián)。位圖RMei是葉子節(jié)點(diǎn)ei相對(duì)應(yīng)的位圖,其計(jì)算方式為:

RMei=RMI1⊕RMI2⊕…⊕RMIm

(3)

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

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

(4)

MRH樹的中間節(jié)點(diǎn)ej根據(jù)其所處位置關(guān)系將附近POI組成的一個(gè)最小矩形區(qū)域作為其孩子節(jié)點(diǎn),并與位圖RMej相關(guān)聯(lián)。位圖RMej是MRH樹中間節(jié)點(diǎn)ej所對(duì)應(yīng)的位圖,其計(jì)算方式為:

RMei=RMe1⊕RMe2⊕…⊕RMel

(5)

其中,e1,e2,…,el為中間節(jié)點(diǎn)ej的所有子節(jié)點(diǎn)。中間節(jié)點(diǎn)ej的哈希值為:

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

(6)

通過(guò)從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)逐層構(gòu)建MRH樹,能夠得到MRH樹根節(jié)點(diǎn)值eroot的位圖RMeroot及其哈希值H(eroot)。DO用自己的私鑰對(duì)哈希值H(eroot)簽名,并將數(shù)據(jù)提供給SP。

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

圖3 根據(jù)圖2(a)構(gòu)造的MRH樹

4 VO生成算法與真實(shí)性驗(yàn)證

4.1 VO生成算法設(shè)計(jì)

在構(gòu)建VO生成算法之前,本文首先闡述用戶查詢算法執(zhí)行過(guò)程。該算法是基于貪心策略來(lái)構(gòu)建的,其IR樹中節(jié)點(diǎn)ei的權(quán)值ωei計(jì)算公式為:

(7)

其中,dist(ei,Q)表示節(jié)點(diǎn)ei與查詢點(diǎn)Q之間的距離,|ei.ψ∩CurK|表示節(jié)點(diǎn)ei中含有的關(guān)鍵詞ei.ψ和當(dāng)前查詢關(guān)鍵詞集合CurK中具有相同關(guān)鍵詞的個(gè)數(shù)。

當(dāng)用戶查詢所需信息時(shí),查詢算法利用最小優(yōu)先隊(duì)列H存放即將遍歷的節(jié)點(diǎn)權(quán)值,并按照節(jié)點(diǎn)權(quán)值大小進(jìn)行排序。將IR樹的根節(jié)點(diǎn)放進(jìn)最小優(yōu)先隊(duì)列H中,每次從隊(duì)列中取出最小的值進(jìn)行測(cè)驗(yàn):

1)如果從隊(duì)列中取出的元素cur是一個(gè)節(jié)點(diǎn),則查詢算法用式(7) 計(jì)算該節(jié)點(diǎn)的孩子節(jié)點(diǎn)的權(quán)重值并放入隊(duì)列H中。

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

(8)

其中,er是某個(gè)節(jié)點(diǎn)(含有關(guān)鍵字信息),關(guān)鍵詞集合PreK是上一次將POI放入結(jié)果集后的查詢關(guān)鍵詞集合,即PreK=Q.ψ,關(guān)鍵詞集合CurK是本次將POI放入結(jié)果集后的查詢關(guān)鍵詞集合,即CurK=Q.ψcur.ψ,ω′er是上一次將POI放入結(jié)果集時(shí)er的權(quán)重值。僅當(dāng)結(jié)果集CurK中或最小優(yōu)先隊(duì)列H中沒(méi)有元素時(shí),該算法程序才會(huì)停止執(zhí)行,并將產(chǎn)生的查詢結(jié)果返回給用戶。

根據(jù)上述查詢算法構(gòu)造VO生成算法,通過(guò)VO和結(jié)果集R,即可驗(yàn)證查詢結(jié)果的真實(shí)性,VO生成算法偽代碼如算法1所示。

算法1VO生成算法

輸入查詢點(diǎn)Q

輸出開銷值Cost,結(jié)果集R,驗(yàn)證結(jié)構(gòu)VO

Root←MRH樹的根節(jié)點(diǎn)

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每個(gè)元素e) do

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

根據(jù)式(8)更新e的權(quán)重值We

endif

重新調(diào)整Root中權(quán)值排序

endfor

endif

else

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

VO←e

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

根據(jù)式(7)計(jì)算e的權(quán)重值We

Root←e

endif

endfor

endelse

endwhile

在VO構(gòu)造算法過(guò)程中,首先將待遍歷的MRH樹節(jié)點(diǎn)按順序全部放入隊(duì)列Root中,然后依次取出節(jié)點(diǎn)的值,當(dāng)彈出的是非葉子節(jié)點(diǎn)時(shí),需要將該節(jié)點(diǎn)的子節(jié)點(diǎn)放入VO中,方便記錄查詢,因?yàn)樵摴?jié)點(diǎn)的子節(jié)點(diǎn)肯定包含需要的查詢信息。當(dāng)彈出的是POI時(shí),將其放入結(jié)果集R中,并重新對(duì)Root中剩余節(jié)點(diǎn)值進(jìn)行排序。當(dāng)查詢的關(guān)鍵字集合CurK為空時(shí),表明關(guān)鍵字查詢完畢,即算法結(jié)束,VO構(gòu)建完畢。

4.2 查詢真實(shí)性驗(yàn)證算法

本文設(shè)計(jì)驗(yàn)證算法對(duì)算法1的結(jié)果進(jìn)行可靠性、正確性和完整性驗(yàn)證。

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

2)完整性驗(yàn)證:在結(jié)果集R中的POI,其攜帶的關(guān)鍵詞并集必須包含查詢點(diǎn)關(guān)鍵字的總和,否則驗(yàn)證算法會(huì)立刻停止執(zhí)行,并返回用戶“驗(yàn)證結(jié)果錯(cuò)誤”。

3)正確性驗(yàn)證:該驗(yàn)證算法是根據(jù)貪心算法的思想每次選出最符合的POI,并且會(huì)把該P(yáng)OI的兄弟節(jié)點(diǎn)也加入VO中,依據(jù)算法1構(gòu)造出的結(jié)果集R和VO,重新執(zhí)行算法1進(jìn)行驗(yàn)證,其偽代碼如算法2所示。

算法2VO驗(yàn)證算法

輸入查詢點(diǎn)Q,原始根節(jié)點(diǎn)哈希值ort,結(jié)果集R,驗(yàn)證結(jié)構(gòu)VO

輸出驗(yàn)證結(jié)果Auth

1.根據(jù)VO和R計(jì)算MRH樹的根節(jié)點(diǎn)哈希值mrt

2.If (ort不等于mrt) do

3.Return Auth←False

4.if(R中POI的關(guān)鍵字沒(méi)有包含查詢關(guān)鍵字的集合)do

5.Return Auth←False

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

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

8.HR←根據(jù)式(7)計(jì)算Pi的權(quán)值

9.for(VO中每個(gè)節(jié)點(diǎn)ei)do

10.HV←根據(jù)式(7)計(jì)算ei的權(quán)值

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中的每個(gè)POI p)do

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

20.根據(jù)式(8)計(jì)算新的POI p的權(quán)值Wp

21.endif

22.重新調(diào)整HR中每個(gè)POI排序

23.endfor

24.for(HV中每個(gè)節(jié)點(diǎn)e)do

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

26.根據(jù)式(8)計(jì)算節(jié)點(diǎn)e 的權(quán)值We

27.endif

28.重新調(diào)整HV權(quán)值排序

29.endfor

30.endif

31.endwhile

32.if(HR非空)do

33.return Auth←False

34.endif

35.return Auth←True

VO驗(yàn)證算法在執(zhí)行過(guò)程中:

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

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

3)驗(yàn)證結(jié)果的正確性(第7行～第34行)。

(1)利用查詢算法的性質(zhì),HR和HV分別存放結(jié)果集R的權(quán)值和VO的權(quán)值,在驗(yàn)證算法循環(huán)中檢驗(yàn)當(dāng)前查詢關(guān)鍵字是否為空,來(lái)保證算法的正確性(第7行～第30行)。

(2)當(dāng)驗(yàn)證算法結(jié)束時(shí),判斷結(jié)果集隊(duì)列是否為空,以便檢驗(yàn)不會(huì)有多余的POI被放入結(jié)果集R中(第32行～第34行)。

當(dāng)VO驗(yàn)證算法的每一步都通過(guò)執(zhí)行時(shí),就可以驗(yàn)證算法1的可靠性、完整性和正確性,同時(shí)也驗(yàn)證了查詢結(jié)果的真實(shí)性。

5 實(shí)驗(yàn)與結(jié)果分析

5.1 實(shí)驗(yàn)配置

本文采用數(shù)據(jù)集合D來(lái)驗(yàn)證算法1和算法2的真實(shí)性和有效性。數(shù)據(jù)集合D來(lái)源于2個(gè)數(shù)據(jù)集:

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

2)合成數(shù)據(jù)集,其數(shù)據(jù)來(lái)源同上,矩形區(qū)域的左頂點(diǎn)和右下角坐標(biāo)分別(-84.435 0,33.729 6)和(-84.344 4,33.794 6),其中與每個(gè)POI相關(guān)聯(lián)的關(guān)鍵字來(lái)自于美國(guó)地名委員會(huì)(geonames.usgs.gov),包含180多萬(wàn)個(gè)POI和攜帶20多萬(wàn)個(gè)不同的關(guān)鍵詞,這些關(guān)鍵字包含地理名稱等信息,與POI隨機(jī)相關(guān)聯(lián)。

本文實(shí)驗(yàn)的PC機(jī)采用Windows7系統(tǒng),開發(fā)環(huán)境為Eclipse,編程語(yǔ)言為Java。利用POI所攜帶的平均關(guān)鍵詞量|I.ψ|和關(guān)鍵字?jǐn)?shù)量|Q.ψ|對(duì)本文構(gòu)造的MRH樹進(jìn)行性能評(píng)估,在變量POI個(gè)數(shù)和查詢關(guān)鍵字?jǐn)?shù)量不同的情況下,分析VO大小的增長(zhǎng)情況。VO大小表示SP與用戶之間的通信開銷,VO越大表示通信所需帶寬越大,即表明消耗的資源和時(shí)間也就越多。

5.2 實(shí)驗(yàn)結(jié)果

5.2.1 VO空間開銷與興趣點(diǎn)規(guī)模的關(guān)系

本實(shí)驗(yàn)通過(guò)興趣點(diǎn)數(shù)量的增大,觀察VO開銷的變化,結(jié)果如圖4所示。其中,每個(gè)POI平均包含10個(gè)關(guān)鍵字,查詢點(diǎn)的關(guān)鍵字設(shè)為4個(gè)。

圖4 VO隨興趣點(diǎn)數(shù)量變化曲線

從圖4可以看出,隨著興趣點(diǎn)數(shù)量的增大,其包含的關(guān)鍵字?jǐn)?shù)量也增多,MIR樹和MRH樹的VO也呈增長(zhǎng)的趨勢(shì),并且不僅MIR樹的初始VO開銷比MRH樹高,而且其VO增長(zhǎng)率明顯比MRH樹的增長(zhǎng)率大,即MIR樹的帶寬和時(shí)間開銷均比MRH樹高。這是因?yàn)镸IR樹中的每個(gè)節(jié)點(diǎn)都含有開銷代價(jià)較大的倒排索引文件,而本文構(gòu)造的MRH樹的每個(gè)節(jié)點(diǎn)則使用開銷代價(jià)較小的位圖。

5.2.2 VO空間開銷與POI平均關(guān)鍵字?jǐn)?shù)量關(guān)系

本實(shí)驗(yàn)選取100萬(wàn)個(gè)POI作為變量測(cè)驗(yàn)數(shù)據(jù),查詢關(guān)鍵字設(shè)為4個(gè)。通過(guò)增加POI攜帶的平均關(guān)鍵字?jǐn)?shù)量,觀察VO開銷的變化趨勢(shì),結(jié)果如圖5所示。

圖5 VO隨POI攜帶平均關(guān)鍵詞數(shù)量變化曲線

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

從圖5可以看出,隨著POI攜帶的平均關(guān)鍵詞數(shù)量逐漸增大,MIR樹和MRH樹的VO開銷都呈增長(zhǎng)的趨勢(shì)。同樣的,MIR樹的初始VO比MRH樹高,其增長(zhǎng)率也比MRH樹高。這說(shuō)明隨POI攜帶的平均關(guān)鍵詞數(shù)量的增長(zhǎng),MIR樹在空間查詢中帶寬和時(shí)間的開銷代價(jià)都比MRH樹大。

5.2.3 VO空間開銷與查詢關(guān)鍵字?jǐn)?shù)量關(guān)系

本實(shí)驗(yàn)選取100萬(wàn)個(gè)POI作為測(cè)驗(yàn)數(shù)據(jù),每個(gè)POI攜帶關(guān)鍵字個(gè)數(shù)為10個(gè),通過(guò)增加查詢關(guān)鍵字?jǐn)?shù)量,觀察VO開銷值的變化,結(jié)果如圖6所示。

圖6 VO隨查詢關(guān)鍵字?jǐn)?shù)量變化曲線

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

從圖6可以看出,隨著查詢關(guān)鍵字的逐漸增多,MIR樹和MRH樹的VO開銷也增大,同樣的,MIR樹的初始VO開銷比MRH樹高,且其VO增長(zhǎng)率比MRH樹要高。這表明隨查詢關(guān)鍵字?jǐn)?shù)量的逐漸增大,MIR樹的開銷比MRH樹更高。

5.2.4 VO算法正確性驗(yàn)證

本文對(duì)VO算法的正確性進(jìn)行了相應(yīng)的實(shí)驗(yàn)驗(yàn)證。本實(shí)驗(yàn)分2組,第1組實(shí)驗(yàn)包括5個(gè)正確實(shí)驗(yàn)數(shù)據(jù)集,第2組實(shí)驗(yàn)包括5個(gè)隨機(jī)攜帶10%～20%虛假POI的數(shù)據(jù)集。實(shí)驗(yàn)以通過(guò)的實(shí)驗(yàn)數(shù)據(jù)占總的實(shí)驗(yàn)數(shù)據(jù)的百分比來(lái)評(píng)估算法的正確性,對(duì)每一組實(shí)驗(yàn)結(jié)果求均值。本文進(jìn)行了3次實(shí)驗(yàn),結(jié)果如圖7所示。在3次實(shí)驗(yàn)中,第2組實(shí)驗(yàn)數(shù)據(jù)分別攜帶10%、15%、20%的虛假POI。從圖7可以看出,在3次實(shí)驗(yàn)中第1組正確率均達(dá)100%,因?yàn)榈?組實(shí)驗(yàn)數(shù)據(jù)攜帶虛假的POI,其正確率為90%、85%、80%。實(shí)驗(yàn)結(jié)果證明了VO查詢算法的可靠性和完整性。

圖7 查詢算法正確率

6 結(jié)束語(yǔ)

在MIR樹的基礎(chǔ)上,本文構(gòu)造一種數(shù)據(jù)結(jié)構(gòu)MRH樹,利用位圖來(lái)替代MIR樹中高代價(jià)的倒排索引文件數(shù)據(jù)結(jié)構(gòu),并設(shè)計(jì)VO生成算法和VO驗(yàn)證算法,驗(yàn)證MRH樹在空間查詢中的可靠性、正確性和完整性。在POI規(guī)模、查詢關(guān)鍵字?jǐn)?shù)量與POI攜帶關(guān)鍵字個(gè)數(shù)不同的情況下分別進(jìn)行實(shí)驗(yàn),結(jié)果表明,MRH樹的通信開銷和計(jì)算時(shí)間均低于MIR樹。然而MRH樹仍將查詢關(guān)鍵字信息嵌入在樹的每個(gè)節(jié)點(diǎn)中,導(dǎo)致空間查詢驗(yàn)證的開銷較大,后續(xù)將采用其他驗(yàn)證數(shù)據(jù)結(jié)構(gòu)進(jìn)一步降低空間查詢驗(yàn)證的開銷。