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

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

Key words: inverted linear quad-tree; OR semantics; geo-textual object; spatial keywords query; mobile computing

随着智能手机和移动终端的普及,越来越多的应用中出现了地理位置与文本信息交融的现象 [1,2] .一方面,
越来越多的场所,例如商店、饭店、游乐场等,都附加了与其地理位置相关的文本描述信息;另一方面,文本信息
也通过地名、街道地址等特征与地理信息相关联.研究表明,大约有五分之一的互联网搜索与地理位置相关,包
[3]
括地名、邮政编码等 .在同时含有空间信息和文本信息的对象上进行空间文本查询(简称为空间关键字查询)是
[4]
当前研究的热点问题之一 ,即给定查询点位置和文本信息,从大量空间文本对象中找到符合查询要求的对象.
Top-k 空间关键字搜索是空间关键字查询领域中非常重要的操作之一,其根据给定的评分函数在数据集中
返回得分最高的 k 个对象 [5−13] .现有大部分空间关键字查询工作最先考虑的是满足用户所有文本要求和位置邻
近性要求的对象,可称其为基于 AND 语义的查询.然而,基于 AND 语义的查询结果需完全匹配查询关键字,有时
会使用户错失一些较好的选择.以图 1 为例,空间中的每个对象(即黑色点 o 1 至 o 6 )均具有地理位置坐标和相应
的关键字集合,其中每一个关键字对应一个权值,表示该关键字的重要程度(如用户评分).例如,对象 o 2 是一个电
影院,对象 o 4 是一个综合性商场.假设用户初到该城市,在查询点 q(红色点)的位置查找一家电影院,并想喝杯咖
啡.基于 AND 语义的 Top-2 查询将返回对象集合{o 4 ,o 5 },因为仅此两个对象同时包含{cinema,coffee}两个关键
字.观察图 1 中的对象,很明显,对象 o 2 和 o 1 均部分满足用户要求,且对象 o 2 和 o 1 在对应查询关键字上的权重均
大于对象 o 4 和对象 o 5 在相应查询关键字上的权重(设权重越高越好),此外,q 到对象集合{o 1 ,o 2 }的距离较到对象
集合{o 4 ,o 5 }更近.换句话说,如果用户更看重品质,基于 AND 语义查询返回的结果将错过更符合用户品质要求
的对象(即对象 o 2 和对象 o 1 ),并且,该对象距离查询用户位置并不远.本文关注的基于 OR 语义的受限 Top-k 空间
关键字查询可解决此类问题.

(a) (b)
Fig.1 A simple example
图 1 查询示例
研究者针对 Top-k 空间关键字搜索问题提出了许多索引技术和查询算法 [14] .其中最普遍使用的是 IR-tree
索引.在该索引中,根据所有对象的地理位置建立一棵 R 树,每个节点关联一个倒排文件.当数据量较小时,IR-
tree 处理效率较高,而当数据量增多时,其查询和更新效率就会下降;此外,由于在空间中只建立了一棵树,树的维
护时间较长 [15,16] .为了解决上述不足,文献[13]提出了一种倒排线性四分树索引结构 IL-Quadtree.IL- Quadtree 为
每个关键字都建立了一棵线性四分树,快速返回符合查询关键字要求的 k 个对象.当用户进行查询时,只访问查
询关键字所对应的线性四分树,直接忽略掉那些不包含目标关键字的对象.然而,文献[16]仅满足 AND 语义要
求.本文从查询 OR 语义出发,综合考虑用户的地理位置和查询关键字与空间文本对象匹配的情况,返回在用户
空间范围要求内的空间文本相似性最高的前 k 个对象,即支持 OR 语义的受限 Top-k 空间关键字查询.
本文采用倒排聚集线性四分树 AIL 索引所有的空间文本对象.即在倒排文件中存储所有关键字,倒排文件