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

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

4. while nbs≠∅ do
5. e←从栈 nbs 中出栈顶;
6. if |R|=k then
7. break;
8. else if e 是一个对象 then
9. R=R∪e;
10. else if e 是一个非叶子节点 then
11. for e 每一个子节点 e′ do
12. if δ(q.loc,e′.loc)≤d then
13. for btset 中的每一棵聚集线性四分树
14. 计算 e′中关键字对应的权重加和;
15. 计算 f(q,e′);
16. 将子节点 e′和 f(q,e′)入栈 nbs;
17. else
18. for 叶子节点 e 中的每一个对象 o
19. if δ(q.loc,o.loc)≤d then
20. for btset 中的每一棵聚集线性四分树
21. 计算 o 中关键字对应的权重加和;
22. 计算 f(o,q);
23. 将对象 o 和 f(q,o)入栈 nbs;
24. return R;

4.3 VGird查询算法
因为 VQuad 算法在计算四分树某一层节点与查询点的空间文本相似性时,需要不断重复地访问线性四分
树,进行 Morton 码与空间位置的转换,从而影响了查询效率.实际上,无需将线性四分树构建成虚拟四分树,可直
接从线性四分树上的 Morton 码出发,通过二进制的位运算获得单元的邻近区域和区域中的空间文本对象.基于
这样的动机,本文提出了基于虚拟网格的 VGrid 查询算法.VGrid 将整个空间看成一个虚拟网格,网格中每一个
单元均有唯一的 Morton 码.利用单元的 Morton 码与单元位置坐标可相互转换的性质,邻近单元可通过公式(5)
在 O(1)时间复杂度下计算获得,提高了查询效率.
(1) VGrid 算法流程
算法的基本思想是以查询 q 所在位置为中心,从中心单元开始,循环寻找中心单元的邻近 8 个单元(如图 9
中的 n 0 ~n 7 所示)中包含的对象,计算该对象与查询 q 的空间文本相似性,不断更新查询结果集直至获得满足空
间限制的 Top-k 结果.为了防止空间单元的重复访问,采用 visit 布尔集合来标识单元是否已被访问.
具体地,首先找到查询点 q 所在的单元,确定相应的四进制 Morton 码,记为 code(第 2 行).找到查询 q 包含的
所有关键字对应的聚集线性四分树 btset(第 3 行).根据定义 3 计算查询 q 到单元 code 的空间文本相似性,以
(code,f(q,code))的形式存入栈 nbs(第 4 行).nbs 中的元素以空间文本相似性升序排序.取 nbs 栈顶 nbs_t.若栈顶对
应的码值 nbs_t.code 存在于线性四分树集合 btset 中的任意一棵树中,则从具有 nbs_t.code 的线性四分树中取出
nbs_t.code 单元下的对象组成 Oset(第 7 行~第 8 行).计算 Oset 中的对象与查询 q 的空间文本相似性,将满足空
间距离约束 d 的对象放入不断更新的候选结果集 RSet 中,以查询 q 到该对象的空间文本相似性为排序关键字
(第 9 行~第 11 行).当 Rset 中的第 k 个对象的空间文本相似性值大于栈顶元素的空间文本相似性值时,说明空间
中存在比候选集中更符合用户要求的查询结果.此时,利用公式(5)寻找栈顶单元的邻近 8 个单元,将 8 个单元中
满足空间距离约束 d 并且未被访问的单元的 code 值及其与查询的空间文本相似性存入 nbs,并在 visit 中将 code
单元标识为已访问(第 12 行~第 17 行).重复第 6 行～第 19 行,直至候选结果集|Rset|=k,且 Rset 中对象的第 k 个