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

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

4.2.1 虚拟四分树
建立虚拟四分树的目的是将查询中不同关键字对应的聚集线性四分树整合起来,通过计算虚拟四分树的
节点与查询之间的空间文本相似性,将不满足查询要求的节点较早地剪枝掉.虚拟四分树之所以称为“虚拟”在
于其物理上并不真实存在.由于四分树中每个层次在线性四分树的区域编码已知,所以根据树的层次以及区域
编码能够建立一棵虚拟四分树.图 8 是与图 6(b)一样的虚拟四分树.唯一不同的是,这里将每个层次的编码扩展
为 r(=3)位.空缺位用 X 字符补位.虚拟四分树的根节点即整个区域编码为 XXX(其中,X 可取{0,1,2,3}中的任意
值).第 1 层的 4 个区域编码分别为 0XX、1XX、2XX、3XX(仅左侧第 1 位有意义).虚拟四分树的第 2 层节点区
域编码范围是 00X~33X(仅左侧前 2 位有意义),虚拟四分树的第 3 层节点区域编码范围是 000~333.

Fig.8 Virtual quadtree
图 8 虚拟四分树
在查询过程中需要计算虚拟四分树上的一个区域与查询之间的空间文本相似性.然而,虚拟四分树仅是逻
辑上的概念,在物理上实际存储的是以 B+−树组织起来的码值.因此,在计算空间文本相似性时,在空间方面,用
区域中的最大 Morton 码值与最小 Morton 码值的横纵坐标所围成的区域限定区域范围,表示为(最小 Morton 码
值,最大 Morton 码值).通过区域码值与空间横纵坐标的转换即可确定该区域的空间位置及空间相似性.在文本
方面,将区域中所有单元的关键字权重最大值加和作为该区域对应查询的文本权重.由此,可利用公式(3)计算区
域与查询间的空间文本相似性.例如,图 8 中第 2 层编码为 12X 的区域,其在 B+−树上实际对应的编码为{120,
121,122,123}.该区域对应查询要求的文本权重,即 4 个单元内对应查询关键字权重最大值的加和.
4.2.2 VQuad 算法流程
VQuad 算法逻辑上将整个空间用四分树进行划分,利用最小最佳优先原则选择符合查询要求的 Top-k 个空
间文本对象.算法 2 展示了 VQuad 算法的具体过程.在算法 2 中,用栈 nbs 存放从虚拟四分树中取得的节点.栈中
元素以节点到查询 q 之间的空间文本相似性的值升序排序.首先,找到查询 q 包含的所有关键字对应的聚集线
性四分树 btset(第 2 行),将虚拟四分树的根节点入栈 nbs 中(第 3 行).当栈 nbs 不为空时,从 nbs 中取栈顶 e(第 5
行).如果 e 是空间文本对象,则将该对象存入结果集 R 中(第 8 行~第 9 行).如果 e 是节点,判断 e 是叶子节点或
非叶子节点,如果 e 是非叶子节点,则将节点 e 所在区域进行逻辑上四等分,计算 e 的 4 个孩子节点与查询 q 之
间的空间距离,判断该空间距离是否在用户允许范围 d 内.如果在空间限制范围内,则运用公式(3),计算 e 的孩子
节点与查询 q 之间的空间文本相似性,并将该孩子节点码值及其空间文本相似性 f(q,e′)入栈 nbs(第 10 行~第 16
行).如果 e 为叶子节点,则将 e 在不同的线性四分树中包含的所有对象取出,判断取出对象空间上是否在用户允
许范围 d 内.如果是,则计算对象与查询 q 之间的空间文本相似性并入栈 nbs 中(第 18 行~第 23 行).最后,当结果