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

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

图 10 和图 11 展示了将两个数据集导入 QGIS 后,签到兴趣点 POI(point of interests)的分布情况.表 4 列出了数
据集的统计信息,包括 POI 数量、键字数量以及每个 POI 上的平均关键字数.实验中的所有算法用 Java 实现.
运行于 Intel(R) i5 2.30GHzCPU 处理器、4GB 内存的 Windows 8 计算机上.实验中,所有的 POI 组成被查询点集
合.查询点集合从 POI 集合中随机抽取 10 000 个.随机抽取的点位置即查询点位置信息.查询点的文本关键字按
照不同等级的词频随机分配.文本关键字的等级是根据关键字词频的上四分位、中位数划分的 3 个等级(即高
频、中频和低频词).实验默认设置见表 5.
文献[16]是第 1 篇在线性四分树上进行 Top-k 关键字查询的代表性工作,但其仅支持 AND 语义.本文提出
的 VQuad 算法是在文献[16]中提出的基于虚拟四分树算法基础上的改进,所以在支持 OR 语义方面,实验仅对比
了 VQuad 算法和 VGrid 算法在两个不同数据集上平均查询时间的变化情况(见第 5.2 节).为了验证两种算法在
AND 语义方面的有效性,第 5.3 节对两种算法支持 AND 语义的实验结果进行了对比分析.实验变动参数有关键
字个数(l)、返回结果数(k)、数据集大小等.由于文献[16]已验证了倒排线性四分树与经典索引结构的对比情况,
这里没有再对索引结构大小等进行赘述.

Fig.10 LA check-in datasets Fig.11 NYC check-in datasets
图 10 LA 签到数据集 图 11 NYC 签到数据集

Table 4 Statistics for the dataset
表 4 数据集的统计信息
Property LA NYC
POI 数量 215 614 206 416
关键字数量 175 704 240 781
每个对象的平均关键字数量 1.34 1.32
Table 5 Default setting
表 5 实验默认设置
实验设置的参数 字母表示 默认值
每个查询点的文本关键字数 l 3
查询返回的结果数 k 10
空间和文本比重参数 α 0.3
线性四分树划分深度 R 3
空间距离约束 d 10%×空间大小
5.2 支持OR语义的算法性能对比
图 12 对比展示了 VQuad 和 VGird 算法在两个不同真实数据集上的查询平均处理时间.从图 12 观察到两
种算法在 LA 和 NYC 数据集上的性能表现类似.从图 10 和图 11 可以看出,两个签到数据集 POI 分布类似且 POI
个数接近.无论是在 LA 的数据集上还是在 NYC 的数据集上,VGird 的平均处理时间均优于 VQuad.其原因在于,
VQuad 算法需要多次访问查询关键字对应的线性四分树.具体地,VQuad 查询过程中采用的虚拟四分树是一个
逻辑概念上的结构,物理上并不存在.因此,每次访问到某一个层次的四分树节点时,需要进行物理上线性四分
树存储的 Morton 码到虚拟四分树的转换(见第 4.2.1 节).同时,VQuad 算法在计算非叶子节点与查询点的空间文
本相似性时,需要该节点下覆盖对象的查询关键字的最大权重.然而,线性四分树上存储的是虚拟四分树上叶子