Page 223 - 《软件学报》2020年第10期

潘晓 等:支持 OR 语义的高效受限 Top-k 空间关键字查询技术 3199

中的每个关键字指向包含该关键字的所有对象组成的聚集线性四分树.在 AIL 的基础上,本文提出了两种查询
处理算法 VQuad 和 VGrid.受文献[16]的启发,VQuad 算法将整个空间区域看成一个虚拟四分树,基于此,虚拟四
分树采用最小最佳优先原则返回同时支持 OR 语义与空间距离约束的结果.VQuad 算法是一个自顶向下的空间
搜索算法.然而,线性四分树在物理上存储的并不是空间层次型结构,造成了在非空间层次结构上构建层次结构
信息时,VQuad 重复遍历线性四分树.我们发现,线性四分树中的空间编码相当于将整个区域划分为虚拟网格,
线性四分树中的对象位置与网格单元中的码值具有一一对应的关系.利用该对应关系,在网格中可以通过 O(1)
的时间复杂度访问任意单元的邻近单元,避免了线性四分树的重复遍历.基于上述想法,本文提出了一种基于虚
拟网格的高效查询算法 VGrid.
综上所述,本文贡献总结如下.
● 在倒排聚集线性四分树的基础上,提出了一种支持 OR 语义的基于虚拟四分树的 Top-k 空间关键字搜索
算法 VQuad.
● 从线性四分树中空间位置的编码特点出发,提出了一种基于虚拟网格遍历的高效 OR 语义查询的 Top-k
空间关键字搜索算法 VGrid.
● 在真实数据集上进行了大量的实验,验证了所提方法在支持 OR 语义和 AND 语义上的有效性和高效性.
本文第 1 节回顾 Top-k 空间关键字查询领域的相关工作.第 2 节给出问题的形式化描述以及相关定义.第 3
节阐述聚集倒排线性四分树索引结构 AIL,并详细介绍在该树上的相关操作.第 4 节提出基于 OR 语义的受限
Top-k 空间关键字查询处理算法 VQuad 和 VGrid.第 5 节阐述在真实数据上进行的一系列实验,并对实验结果进
行分析.最后,第 6 节对全文进行总结.

1 相关工作

空间关键字查询的文本约束可分为 4 种 [11] :完全匹配、部分匹配、模糊匹配和布尔约束.文献[8,16−20]属
于完全匹配约束(即 AND 语义约束),查询完全满足用户关键字要求的对象.适用于用户对文本相似性要求较高
的情况.文献[7,12,15,21−24]属于部分匹配约束(即 OR 语义约束),查询满足用户部分关键字要求的对象.相较于
完全匹配约束,当查询用户对文本相似性要求的严格程度不那么高时,可以采用部分匹配的方式.模糊匹配 [25−29]
要求对象关键字与查询关键字进行字符串相似度匹配.布尔约束 [30−33] 是用一个布尔表达式指定必须包含或可
包含的关键词以及不包含的关键词.
就查询结果的排序方式而言,排序公式一般为空间距离和文本相关性的某种组合.例如,文献[30,34]仅依据查询
对象与被查询对象的空间距离作为排序依据;文献[35]以空间和文本相关性的比值作为排序依据;文献[16,36−39]采
用的是空间和文本相关性的线性组合;文献[16,35−39]使用户对于空间距离与文本相关性的重要程度有一定的
选择权,但不能完全约束空间距离,导致查询返回的结果有距离用户过远的可能.本文采取空间距离与文本相关
性的线性组合排序,并且增加了对空间距离的约束,充分考虑了用户对空间距离与文本重要程度的实际需求.
现有的在空间文本对象上建立的索引结构可分为空间优先和文本优先两类.空间优先的索引是先根据空
间划分建立索引,然后在每个节点中存放有关的关键字信息.空间优先的索引中使用最多的是 IR-tree [19,22] 和
2
2
IR -tree [18] 等.IR-tree 为 R-tree 中的每个节点关联了一个倒排文件.IR -tree 为 R-tree 中的每个节点关联了签名文
2
件,签名文件概括了一个节点所包含的关键字信息.当数据量较小时,IR-tree 和 IR -tree 的处理较为高效,当数据
量增大时,这类索引的效率将明显下降,并且剪枝困难,影响到算法效率 [15] .另一类是文本优先的索引,这类索引
是在现有文本索引(如倒排文件)上进行的改进,将每一个关键字映射到一个含有空间信息的数据结构上,如
3
I 3[15] 、S2I [13] 、IL-Quadtree [16] 等.I 索引使用四分树(quadtree)将位置空间进行划分,提出关键字单元作为基本存
储单元,根据不同关键字在单元格中出现的次数,分为频繁和非频繁的关键字.对于非频繁的关键字,直接用一
个页面存储相关对象,通过查找表直接映射到数据文件中的物理位置;对于频繁的关键字,为频繁的关键字设计
头文件指向关键字单元格所在磁盘页,其中,头文件是一个类似于四分树的结构,每个节点存储关于频繁关键字
的概要信息.IL-Quadtree 针对每个关键字建立一棵线性四分树.通过检测不同树的相同节点,检验该区域是否包