基于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树仍将查询关键字信息嵌入在树的每个节点中,导致空间查询验证的开销较大,后续将采用其他验证数据结构进一步降低空间查询验证的开销。