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

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

字的对象不会在该聚集线性四分树中被索引.“聚集”是指在树中每一个节点中都存储一个聚集值,即该关键字
在此节点下的最大权重.如图 4 所示,“coffee”对应的线性四分树的根节点中的 0.176 表示树下所有的对象
{o 1 ,o 3 ,o 4 ,o 5 }中“coffee”的权重均不大于 0.176.线性四分树源于四分树,与四分树不同的是,线性四分树以 B+−树
的形式存储空间位置的编码值,不是直接存储空间位置(编码方法将在本节后面加以阐述).此外,线性四分树中
不存储不包含任何对象的空间码值.若采用四进制 Morton 码对图 1 所示的空间进行编码,其结果可如图 3 所示.
包含“coffee”关键字的对象有{o 1 ,o 3 ,o 4 ,o 5 },将这些对象所在位置对应的 Morton 码用 B+−树索引起来即形成
“coffee”关键字对应的聚集线性四分树,如图 4 所示.类似地,“cinema”对应的聚集线性四分树如图 5 所示.图 4 和
图 5 中的两棵聚集线性四分树是图 2 中“coffee”和“cinema”的关键字对应的聚集线性四分树的详细版.

Fig.2 Aggregate inverted linear quadtree
图 2 聚集倒排线性四分树

Fig.3 Encoded space
图 3 空间编码

Fig.4 Aggregate linear quadtree w.r.t. coffee Fig.5 Aggregate linear quadtree w.r.t. cinema
图 4 “coffee”对应的聚集线性四分树 图 5 “cinema”对应的聚集线性四分树
空间位置可遵循一定的规则进行编码,常用的有四进制或十进制 Morton 码,本文采用四进制 Morton 码.文
献[40]对空间位置编码方法进行了详细阐述,这里仅作简要说明.编码过程需要借助四分树,设四分树最大层次