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

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

对象的空间文本相似性值优于 nbs 中栈顶元素的空间文本相似性值.
算法 3. 基于虚拟网格的 OR 语义查询排序算法 VGrid.
Input:ALT:聚集倒排线性四分树,q:查询对象,d:空间距离约束,k:要求返回的对象个数;
output:RSet:前 k 个 f 值最小的对象集合.
1. RSet:=∅;nbs:=∅;
2. code=q 的位置点所对应的单元;
3. btset=所有与 q.T 相对应的 AIL;
4. nbs←{(code,f(q,code)};
5. while (|Rset|<k||Rset.f≥nbs.top.f)
6. nbs_t=从栈 nbs 中取栈顶;
7. if (nbs_t.code 存在于 btset 中任意一棵树中)
8. Oset=分别取出在 btset 中所有 code 值等于 nbs_t.code 的单元对应的对象;
9. for (Oset 中的每一个对象 o)
10. if (δ(q.loc.o.loc)≤d)
11. 将 f(q,o)更新入 RSet;
12. if (|Rset|<k||Rset.f≥nbs_t.f)
13. code=调用公式(4)计算 nbs_t 的邻近 8 个单元;
14. if (code 没有被标记为 visit & δ(q.loc,e.loc)≤d)
15. 计算 f(q,code);
16. code 被标记为 visit;
17. 将 code 入栈 nbs;
18. else
19. break;
20. return RSet;
这里需要说明两点:(1) 为保证算法的正确性,在算法 3 的第 15 行中计算虚拟网格中的一个单元到查询 q
的空间文本相似性时,单元格关键字权重采用的是该关键字在空间中的全局最大值;(2) VGrid 算法可同时支持
OR 语义和 AND 语义.在完成 AND 语义查询时仅需将算法 3 中的第 7 行修改为被查询单元或对象是否存在于
查询关键字对应的所有线性四分树即可.
(2) 运行实例
继续以图 1 和查询点 q={(5.8,5.8),{coffee,cinema},3,1}的例子说明算法 3(VGrid)的运行过程.首先找到查询
点 q 所在的单元,确定相应的 code 值为 303.在 visit 中将 303 标记为已访问.通过公式(3)计算查询点 q 到 303 单
元的空间文本相似性 f(q,303)=0.700.将(303,0.700)入栈 nbs 中.设关键字 coffee、cinema 分别对应的线性四分树
为 bt 1 和 bt 2 (即图 3 和图 4).栈顶元素 303 出栈.虽然单元 303 到查询点 q 的距离小于 d,但 303 没有在 bt 1 和 bt 2
中,说明 303 中没有对应查询文本的对象.利用公式(5)计算 303 的相邻 8 个单元,即{300,301,310,312,330,321,
320,302}.计算查询 q 到每一个单元的空间文本相似性,见表 2 的第 1 行.将单元 Morton 码值及其与查询对应的
空间文本相似性值按升序存入栈 nbs 中,并在 visit 中将这些单元标记为已访问.
从栈 nbs 中取栈顶 330.因为 330 到查询点 q 的距离小于 d,取出树 bt 1 和 bt 2 中 330 单元对应的对象,去重后
得 h={o 2 }.计算 o 2 与查询 q 的空间文本相似性 f=0.510,并存入结果集 R={(o 2 ,0.510)}.此时,结果集 R 中对象 o 2
的空间文本相似性大于栈顶元素与查询 q 的空间相似性(即 0.510>0.485).根据公式(4)计算栈顶 330 相邻 8 个单
元,即{303,312,313,331,333,332,323,321}.其中,{303,312,321}均已被访问,因此将剩余单元到查询点 q 的距离小
于 d 的单元,即{313,331,333,332,323}入栈,见表 2 第 2 行.将{313,331,333,332,323}标记为已访问.由于此时结果
集 R 中 o 2 与查询 q 空间文本相似性小于栈顶元素对应的空间文本相似性(即 0.510<0.576).所以,程序终止.输出