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

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

集 R 中的对象个数达到 k 时,算法终止.
需要说明的是,VQuad 算法不仅可以支持 OR 语义,也可以支持 AND 语义.即只需在取出线性四分树上某一
层次的节点时,判断其是否在所有的聚集线性四分树中存在.如果在所有查询要求的关键字对应的线性四分树
中均存在,则执行算法的相关计算,即修改算法 2 中的第 13 行和第 20 行.
4.2.3 运行示例
我们用图 1 来说明算法 VQuad 的运行过程.设 AIL 的层数 r=3,查询点 q={(5.8,5.8),{coffee,cinema},3,1},其
中,d=3,k=1.
首先,虚拟四分树根节点的区域码值为(000,333).通过公式(3)计算查询点 q 与虚拟四分树根节点的空间文
本相似性 f(q,code)=0.344.将{(000,333),0.344}入栈 nbs 中.由于 nbs 不为空,栈顶出栈 e=(000,333).计算 e 的 4 个
孩子节点的码值,即{(000,033),(100,133),(200,233),(300,333)}.判断 4 个孩子均在查询点 q 的 d 范围内.计算 4 个
孩子节点与查询 q 的空间文本相似性,见表 1 中第 3 列.将节点码值及其与查询对应的空间文本相似性值按升
序存入栈 nbs 中(见表 1 中第 4 列).取栈顶 e=(300,333),因为单元(300,333)是四分树的中间节点,计算 e=(300,333)
的 4 个孩子节点的码值,即{(300,303),(310,313),(320,323),(330,333)}.计算查询点 q 到 d 范围内的孩子节点的空
间文本相似性,见表 1.将节点码值及其与查询对应的空间文本相似性值按升序存入栈 nbs 中(见表 1 中第 2 行).
重复上述操作,直至表 1 第 4 行,取当前栈顶 e=(330,330).因为单元(330,330)是叶子节点.从与查询关键字对
应的 B+−树中取出 330 单元以下的对象,即{o 2 }.因为 o 2 与查询点 q 的距离小于 d,则计算查询点 q 到对象 o 2 的
空间文本相似性.将对象及其与查询 q 的空间文本相似性的值入栈 nbs 中(见表 1 中第 4 行).第 5 行中,取栈顶
e=o 2 ,因为 o 2 是空间文本对象,将 o 2 存入结果集.此时 k=1,且栈 nbs 中栈顶元素的空间文本相似性上限小于当前
查询结果中最差的空间文本相似性,由定理 1 可知,程序停止.输出结果集 R={(o 2 ,0.510)}.
Table 1 A running example of VQuad
表 1 VQuad 算法运行实例
被访问单元划分后的 4 个孩子节点及与
序号 结果集 R 被访问的单元 栈 nbs 状态
查询 q 对应的空间文本相似性
{(000,033),0.671},{(100,133),0.698}, {(300,333),0.343},{(000,033),0.671},
1 {} {(000,333),0.344}
{(200,233),0.764},{(300,333),0.343} {(100,133),0.698},{(200,233),0.764}
{(330,333),0.485},{(310,313),0.576},
{(300,303),0.700},{(310,313),0.576}, {(000,033),0.671},{(100,133),0.698},
2 {} {(300,333),0.343}
{(320,323),0.707},{(330,333),0.485} {(300,303),0.700},{(320,323),0.707},
{(200,233),0.764}
{(330,330),0.485},{(310,313),0.576},
{(000,033),0.671},{(100,133),0.698},
{(330,330),0.485},{(331,331),0.743},
3 {} {(330,333),0.485} {(300,303),0.700},{(320,323),0.707},
{(332,332),0.743},{(333,333),0.760}
{(331,331),0.743},{(332,332),0.743},
{(333,333),0.760},{(200,233),0.764}
{o 2,0.510},{(310,313),0.576},
{(000,033),0.671},{(100,133),0.698},
4 {} {(330,330),0.485} {o 2,0.510} {(300,303),0.700},{(320,323),0.707},
{(331,331),0.743},{(332,332),0.743},
{(333,333),0.760},{(200,233),0.764}
{(310,313),0.576},{(000,033),0.671},
{(100,133),0.698},{(300,303),0.700},
{o 2,
5 {o 2,0.510} {} {(320,323),0.707},{(331,331),0.743},
0.510}
{(332,332),0.743},{(333,333),0.760},
{(200,233),0.764}

算法 2. 基于虚拟四分树的 OR 语义查询排序算法 VQUAD.
Input:ALT:聚集倒排线性四分树,k:要求返回对象的个数,d:空间距离约束,q:查询对象;
Output:R:前 k 个 f 值最小的对象集合.
1. R=∅;nbs=∅;
2. btset=AIL 中所有与 q.T 相对应的聚集线性四分树;
3. 将虚拟四分树的根节点入栈 nbs;