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

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

4 基于 OR 语义的受限 Top-k 空间关键字查询算法

本文的研究目标是基于 AIL,从带有空间位置和文本信息的对象集合 O 中,寻找在受限范围内与查询 q 空间
文本相似性最高的 k 个对象.AIL 融合了空间与文本信息,其中的线性四分树实质存储的是空间位置编码,倒排
文件中存储了文本信息.所以,基于 AIL 进行 Top-k 空间关键字查询有两种思路:(1) 将线性四分树转化为空间上
的四分树,改进已有经典算法,这是设计 VQuad 算法的初衷(详见第 4.2 节);(2) 从线性四分树的空间编码入手,
直接在编码后的空间上进行查询,这是设计 VGrid 算法的动机(详见第 4.3 节).在介绍具体算法之前,我们先来说
明在两种算法中都将用到的定义和定理.
4.1 相关定义
在后续算法中需要计算查询点到一个覆盖多个对象的矩形的空间文本相似性.因此,下面首先定义扩展的
空间文本对象,然后说明如何利用定义 3 计算查询点到扩展空间文本对象的空间文本相似性.
定义 5(扩展的空间文本对象). 扩展的空间文本对象 R 包含地理位置和文本关键字集合两个部分,其形式
化的表示为 R = (loc , ).T 该对象的空间位置 loc 用一个矩形表示,该矩形可覆盖 R 下的每一个空间文本对象.T 为
R 下的所有覆盖对象的关键字集合的并集,其中,针对每一个属于 T 的关键字由两个元素组成(t,w),t 是关键字本
身,w 是该关键字在 R 中的最大权重.
以图 7 为例说明定义 5.图 7 显示了一个扩展的空间文本对象 R,其中,R.loc 覆盖对象 o 3 和 o 4 .R.T={coffee
(0.088),cinema(0.075),library(0.119),swim(0.151)}.

Fig.7 Extended spatio-textual object R
图 7 扩展的空间文本对象 R

在扩展的空间文本对象上,依然可以利用公式(3)计算查询 q 与扩展空间文本对象 R 的空间文本相似性.其
中,空间相似性采用查询 q 到矩形 R.loc 的最小空间距离,文本相似性采用公式(2)即可.
下面的定理 1 证明了查询 q 与扩展的空间文本对象 R 的空间文本相似性是查询 q 到 R 中覆盖的任意对象
的空间文本相似性的上限.
定理 1. 对于 R 下覆盖的任意对象 o,f(q,R)≤f(q,o).
证明:从空间和文本两个角度证明.
从空间的角度,易知对于 R 中包含的任意对象 o,对象 o 到查询点 q 的空间距离不小于 R 到 q 的空间距离,
即 (.q locδ , .R loc ≤ ) δ ( .q loc , .o loc 因 ). 此 ,由公式(1)可知 f s (, )qR ≤ f s ( , ).q o
从文本的角度,易知对于 R 中的任意对象 o,o.t∈R.T,对象 o 对应于查询 q 的文本权重不大于 R 对应于查询
q.T 的文本权重,即 ∑ w ≤ R ..T W . 因此,由公式(2)可知 f (, )qR ≤ f (, ).q o
, to ∑
∈
∈
tq .T tq .T , to t t
综合上述空间和文本两个角度,由公式(3)可得 f(q,R)≤f(q,o).由于 f(q,o)的值越小越好,因此查询 q 与 R 的文
本相似性是查询 q 到 R 中覆盖的任意空间文本对象的空间文本相似性的上限. □
4.2 VQuad算法
VQuad 算法的基本思想是采用最小最佳优先原则,利用 AIL 中存储的空间位置重建虚拟四分树 [16] ,在虚拟
四分树上寻找满足 OR 语义的空间受限的 k 最近邻查询结果.文献[16]在虚拟四分树上进行 Top-k 关键字查询
处理,但其仅实现了 AND 语义.VQuad 算法改进了文献[16]以支持 OR 语义的空间受限查询.下面首先简要介绍
线性四分树与虚拟四分树的转换过程.接下来,在虚拟四分树的基础上详细介绍 VQuad 查询处理方法.