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

3200 Journal of Software 软件学报 Vol.31, No.10, October 2020

含所有的关键字,以实现剪枝.
本文在研究内容上,就文本约束而言,属于部分匹配约束;就排序方式而言,采用空间与文本相似性的线性
组合;就索引结构而言,采用文本优先的聚集倒排线性四分树.与现有工作的区别主要体现在以下 3 点:第一,本
文将整个区域划分为虚拟网格,网格中每一个单元均具有唯一的码值标识,非空网格单元以聚集线性四分树的
形式存储.第二,利用单元码唯一并与单元坐标可相互转换的性质,邻近单元可通过 O(1)时间复杂度的方法计算
来获得,极大地加快了查询速度.第三,空间和文本相关性的线性组合同时考虑了空间距离与文本相关性,并且
在此基础上增加了对空间距离的约束,通过对空间距离的约束有效地缩小了可查询的空间范围.
2 问题的形式化定义

空间中任意对象均包含地理位置和文本关键字集合,记为 o=(loc,T),其中,空间位置 o.loc=(x,y),文本关键字
集合 o.T={t 1 ,t 2 ,...,t n },t i 是文本关键字.任意两个空间文本对象的相似性包括空间相似性和文本相似性两个方面.
定义 1(空间相似性). 任意两个空间文本对象在空间中的相似程度用空间相似性表示.查询对象 q 与被查
询对象 o 的空间相似性定义为
δ (.qloc loc )
, .o
(, )o =
fq (1)
s
δ max
其中,δ max 表示空间中任意两点的最远距离.f s (q,o)可采用任意两点间的距离公式,本文采用的是欧几里德距离.
两个对象空间距离越近,f s (q,o)的值越小,空间相似性越大.
定义 2(文本相似性). 空间文本对象 o 中的每个关键字都被赋予一个权重,代表该关键字在对象 o 中的重要
程度.对于任意的关键字 t,在对象 o 中的重要程度记为 w t,o .w t,o =tf t,o ×idf t ,其中,tf t,o 是词频,idf t 表示逆向文件频率.
两个对象 q 和 o 的文本相似性为
∑ w , to
∈
(, ) 1=−
fq o tq .T (2)
t max P
∑ tq .T w , to 是所有查询关键字在 o 中的权重加和.maxP 是每个关键字在所有对象中的最大权重加和,用以
∈
归一化计算.f t (q,o)的值越小,文本相似性越大.定义 2 中的文本相似性定义支持查询关键字的 OR 语义.具体地,
即使查询 q.T 中的部分关键字不被包含在对象 o 中(即 w t,o =0),其文本相似性也不会为 0.
定义 3(空间文本相似性). 结合定义 1 和定义 2,任意两个空间文本对象的相似性为
f (, )qo = α f s (, ) (1qo + − α ) (, )f qo (3)
t
其中,α(α∈[0,1])是一个可调节参数,用以调节空间距离与文本相似性之间的重要程度.f(q,o)的值越小,q 与 o 的
空间文本相似性就越大.
本文问题描述如下:设空间文本对象集合 O={o 1 ,o 2 ,…,o n },用户查询 q=(loc,T,d,k).loc 是用户查询所在位置,T
是由一系列查询关键字组成的集合,d 是用户可以接受的最远距离,k 即最近邻对象个数,其中,d 的优先级比 k 高.
受限 Top-k 空间关键字查询即从 O 中查找在距离 d 范围内空间文本相似性最高的 k 个被查询对象.其形式化表
示见定义 4.
定义 4(受限 Top-k 空间关键字查询). 设查询对象 q 和被查询集合 O,一个对象 o∈O 是查询 q 的受限 Top-k
关键字查询结果当且仅当对象 o 满足
| oo′ | ′ O & ( , )f q o′∈ ≤ f ( , ) |q o ≤ k 并 且 f s (, )qo < d (4)

3 倒排聚集线性四分树 AIL

本文采用倒排聚集线性四分树索引所有的空间文本对象.倒排聚集线性四分树是倒排表与聚集线性四分
树的结合.倒排表中的每一个关键字指向一棵聚集线性四分树.图 2 是基于图 1 中的空间文本对象建立的倒排
聚集线性四分树示例.
一个关键字对应一棵聚集线性四分树.该树由包含该关键字的所有空间文本对象组成,那些不包含该关键