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

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

出,当α从 0.1 变到 0.9 时,两种算法在 LA 数据集和 NYC 数据集上的平均查询处理时间均保持平稳,两种算法的
性能始终保持大约 0.5ms 的差距.
由于 VGrid 中递归计算邻近 8 个单元,为了验证算法在空间搜索方面的效率,图 17 对比展示了 VGrid 算法
在两个数据集上的空间搜索占比的变化情况.空间搜索占比即查找到用户要求的 k 个最近邻结果,算法遍历过
的空间与整个空间面积比值.k 从 10 增加到 50.此时,d 被设置为无穷大.由图 17 可以看出,查询搜索空间占比会
随着查询返回结果个数的增加而增加.这是比较自然的现象,因为满足要求的结果分布在更远的单元.有趣的
是,相同 k 值设置下 NVGrid 要找到查询结果,比 LYGrid 搜索的空间更广.这从另一方面验证了在 NYC 上的查
询平均处理时间比在 LA 上要更长.即使 k 增长到 50,搜索空间的占比也低于 4.5%.

Fig.14 Performance on different k Fig.15 Performanceon different datasize
图 14 不同查询结果数量上的查询平均处理时间 图 15 不同大小的数据集上的查询平均处理时间

Fig.16 Performance on different α Fig.17 Percentage on different k
图 16 不同参数值α上的查询平均处理时间 图 17 不同查询结果数量上的搜索空间占比

5.3 支持AND语义的算法性能对比
本文提出的 VGrid 算法和 VQuad 算法可同时支持 OR 语义和 AND 语义.为了全面验证算法的性能,本节对
比展示了两种算法在支持 AND 语义方面的性能.
图 18 对比展示了 VQuad 和 VGrid 算法在支持 AND 语义时在两个真实数据集上的平均查询处理时间.与
支持 OR 语义的情况相比,其相同之处是,在两个数据集上,算法 VGrid 的平均处理时间依然均优于 VQuad;不同
之处在于,从整体上来讲,VQuad 在 OR 语义上运行的时间比 AND 语义长 0.2ms,而 VGrid 在 AND 和 OR 语义
上的运行时间很近,平均都是 0.49ms.这是因为,VQuad 算法的处理单位是虚拟四分树上的节点,而 VGrid 的处理
单位是网格单元.基于虚拟四分树的 VQuad 本质上是一种自顶向下的算法,在支持 AND 语义时,节点剪枝效果
更明显,而 VGird 本质上是基于中心单元的遍历,所以 AND 语义与 OR 语义差别不大.
图 19 对比展示了查询平均处理时间在查询关键字数量从 1 增加到 5 的变化情况.随着查询关键字个数的
增加,VQuad 和 VGrid 的查询平均处理时间均有所增加,其原因与支持 OR 语义的原因相同,这里不再赘述.在 l=1
时,AND 语义与 OR 语义无差异.当 l 继续增加时,4 条线均在 l 增加到 3 时发生了陡变.当 l 增加到 4、5 时,增长