2020, Vol. 31
2. 燕山大学 信息科学与工程学院, 河北 秦皇岛 066004
2. School of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China
随着智能手机和移动终端的普及, 越来越多的应用中出现了地理位置与文本信息交融的现象[1, 2].一方面, 越来越多的场所, 例如商店、饭店、游乐场等, 都附加了与其地理位置相关的文本描述信息; 另一方面, 文本信息也通过地名、街道地址等特征与地理信息相关联.研究表明, 大约有五分之一的互联网搜索与地理位置相关, 包括地名、邮政编码等[3].在同时含有空间信息和文本信息的对象上进行空间文本查询(简称为空间关键字查询)是当前研究的热点问题之一[4], 即给定查询点位置和文本信息, 从大量空间文本对象中找到符合查询要求的对象.
Top-k空间关键字搜索是空间关键字查询领域中非常重要的操作之一, 其根据给定的评分函数在数据集中返回得分最高的k个对象[5-13].现有大部分空间关键字查询工作最先考虑的是满足用户所有文本要求和位置邻近性要求的对象, 可称其为基于AND语义的查询.然而, 基于AND语义的查询结果需完全匹配查询关键字, 有时会使用户错失一些较好的选择.以图 1为例, 空间中的每个对象(即黑色点o1至o6)均具有地理位置坐标和相应的关键字集合, 其中每一个关键字对应一个权值, 表示该关键字的重要程度(如用户评分).例如, 对象o2是一个电影院, 对象o4是一个综合性商场.假设用户初到该城市, 在查询点q(红色点)的位置查找一家电影院, 并想喝杯咖啡.基于AND语义的Top-2查询将返回对象集合{o4, o5}, 因为仅此两个对象同时包含{cinema, coffee}两个关键字.观察图 1中的对象, 很明显, 对象o2和o1均部分满足用户要求, 且对象o2和o1在对应查询关键字上的权重均大于对象o4和对象o5在相应查询关键字上的权重(设权重越高越好), 此外, q到对象集合{o1, o2}的距离较到对象集合{o4, o5}更近.换句话说, 如果用户更看重品质, 基于AND语义查询返回的结果将错过更符合用户品质要求的对象(即对象o2和对象o1), 并且, 该对象距离查询用户位置并不远.本文关注的基于OR语义的受限Top-k空间关键字查询可解决此类问题.
|
Fig. 1 A simple example 图 1 查询示例 |
研究者针对Top-k空间关键字搜索问题提出了许多索引技术和查询算法[14].其中最普遍使用的是IR-tree索引.在该索引中, 根据所有对象的地理位置建立一棵R树, 每个节点关联一个倒排文件.当数据量较小时, IR- tree处理效率较高, 而当数据量增多时, 其查询和更新效率就会下降; 此外, 由于在空间中只建立了一棵树, 树的维护时间较长[15, 16].为了解决上述不足, 文献[13]提出了一种倒排线性四分树索引结构IL-Quadtree.IL- Quadtree为每个关键字都建立了一棵线性四分树, 快速返回符合查询关键字要求的k个对象.当用户进行查询时, 只访问查询关键字所对应的线性四分树, 直接忽略掉那些不包含目标关键字的对象.然而, 文献[16]仅满足AND语义要求.本文从查询OR语义出发, 综合考虑用户的地理位置和查询关键字与空间文本对象匹配的情况, 返回在用户空间范围要求内的空间文本相似性最高的前k个对象, 即支持OR语义的受限Top-k空间关键字查询.
本文采用倒排聚集线性四分树AIL索引所有的空间文本对象.即在倒排文件中存储所有关键字, 倒排文件中的每个关键字指向包含该关键字的所有对象组成的聚集线性四分树.在AIL的基础上, 本文提出了两种查询处理算法VQuad和VGrid.受文献[16]的启发, VQuad算法将整个空间区域看成一个虚拟四分树, 基于此, 虚拟四分树采用最小最佳优先原则返回同时支持OR语义与空间距离约束的结果.VQuad算法是一个自顶向下的空间搜索算法.然而, 线性四分树在物理上存储的并不是空间层次型结构, 造成了在非空间层次结构上构建层次结构信息时, VQuad重复遍历线性四分树.我们发现, 线性四分树中的空间编码相当于将整个区域划分为虚拟网格, 线性四分树中的对象位置与网格单元中的码值具有一一对应的关系.利用该对应关系, 在网格中可以通过O(1)的时间复杂度访问任意单元的邻近单元, 避免了线性四分树的重复遍历.基于上述想法, 本文提出了一种基于虚拟网格的高效查询算法VGrid.
综上所述, 本文贡献总结如下.
●在倒排聚集线性四分树的基础上, 提出了一种支持OR语义的基于虚拟四分树的Top-k空间关键字搜索算法VQuad.
●从线性四分树中空间位置的编码特点出发, 提出了一种基于虚拟网格遍历的高效OR语义查询的Top-k空间关键字搜索算法VGrid.
●在真实数据集上进行了大量的实验, 验证了所提方法在支持OR语义和AND语义上的有效性和高效性.
本文第1节回顾Top-k空间关键字查询领域的相关工作.第2节给出问题的形式化描述以及相关定义.第3节阐述聚集倒排线性四分树索引结构AIL, 并详细介绍在该树上的相关操作.第4节提出基于OR语义的受限Top-k空间关键字查询处理算法VQuad和VGrid.第5节阐述在真实数据上进行的一系列实验, 并对实验结果进行分析.最后, 第6节对全文进行总结.
1 相关工作空间关键字查询的文本约束可分为4种[11]:完全匹配、部分匹配、模糊匹配和布尔约束.文献[8, 16-20]属于完全匹配约束(即AND语义约束), 查询完全满足用户关键字要求的对象.适用于用户对文本相似性要求较高的情况.文献[7, 12, 15, 21-24]属于部分匹配约束(即OR语义约束), 查询满足用户部分关键字要求的对象.相较于完全匹配约束, 当查询用户对文本相似性要求的严格程度不那么高时, 可以采用部分匹配的方式.模糊匹配[25-29]要求对象关键字与查询关键字进行字符串相似度匹配.布尔约束[30-33]是用一个布尔表达式指定必须包含或可包含的关键词以及不包含的关键词.
就查询结果的排序方式而言, 排序公式一般为空间距离和文本相关性的某种组合.例如, 文献[30, 34]仅依据查询对象与被查询对象的空间距离作为排序依据; 文献[35]以空间和文本相关性的比值作为排序依据; 文献[16, 36-39]采用的是空间和文本相关性的线性组合; 文献[16, 35-39]使用户对于空间距离与文本相关性的重要程度有一定的选择权, 但不能完全约束空间距离, 导致查询返回的结果有距离用户过远的可能.本文采取空间距离与文本相关性的线性组合排序, 并且增加了对空间距离的约束, 充分考虑了用户对空间距离与文本重要程度的实际需求.
现有的在空间文本对象上建立的索引结构可分为空间优先和文本优先两类.空间优先的索引是先根据空间划分建立索引, 然后在每个节点中存放有关的关键字信息.空间优先的索引中使用最多的是IR-tree[19, 22]和IR2-tree[18]等.IR-tree为R-tree中的每个节点关联了一个倒排文件.IR2-tree为R-tree中的每个节点关联了签名文件, 签名文件概括了一个节点所包含的关键字信息.当数据量较小时, IR-tree和IR2-tree的处理较为高效, 当数据量增大时, 这类索引的效率将明显下降, 并且剪枝困难, 影响到算法效率[15].另一类是文本优先的索引, 这类索引是在现有文本索引(如倒排文件)上进行的改进, 将每一个关键字映射到一个含有空间信息的数据结构上, 如I3[15]、S2I[13]、IL-Quadtree[16]等.I3索引使用四分树(quadtree)将位置空间进行划分, 提出关键字单元作为基本存储单元, 根据不同关键字在单元格中出现的次数, 分为频繁和非频繁的关键字.对于非频繁的关键字, 直接用一个页面存储相关对象, 通过查找表直接映射到数据文件中的物理位置; 对于频繁的关键字, 为频繁的关键字设计头文件指向关键字单元格所在磁盘页, 其中, 头文件是一个类似于四分树的结构, 每个节点存储关于频繁关键字的概要信息.IL-Quadtree针对每个关键字建立一棵线性四分树.通过检测不同树的相同节点, 检验该区域是否包含所有的关键字, 以实现剪枝.
本文在研究内容上, 就文本约束而言, 属于部分匹配约束; 就排序方式而言, 采用空间与文本相似性的线性组合; 就索引结构而言, 采用文本优先的聚集倒排线性四分树.与现有工作的区别主要体现在以下3点:第一, 本文将整个区域划分为虚拟网格, 网格中每一个单元均具有唯一的码值标识, 非空网格单元以聚集线性四分树的形式存储.第二, 利用单元码唯一并与单元坐标可相互转换的性质, 邻近单元可通过O(1)时间复杂度的方法计算来获得, 极大地加快了查询速度.第三, 空间和文本相关性的线性组合同时考虑了空间距离与文本相关性, 并且在此基础上增加了对空间距离的约束, 通过对空间距离的约束有效地缩小了可查询的空间范围.
2 问题的形式化定义空间中任意对象均包含地理位置和文本关键字集合, 记为o=(loc, T), 其中, 空间位置o.loc=(x, y), 文本关键字集合o.T={t1, t2, ..., tn}, ti是文本关键字.任意两个空间文本对象的相似性包括空间相似性和文本相似性两个方面.
定义1(空间相似性).任意两个空间文本对象在空间中的相似程度用空间相似性表示.查询对象q与被查询对象o的空间相似性定义为
| ${f_s}(q, o) = \frac{{\delta (q.loc, o.loc)}}{{{\delta _{\max }}}}$ | (1) |
其中, δmax表示空间中任意两点的最远距离.fs(q, o)可采用任意两点间的距离公式, 本文采用的是欧几里德距离.两个对象空间距离越近, fs(q, o)的值越小, 空间相似性越大.
定义2(文本相似性).空间文本对象o中的每个关键字都被赋予一个权重, 代表该关键字在对象o中的重要程度.对于任意的关键字t, 在对象o中的重要程度记为wt, o.wt, o=tft, oidft, 其中, tft, o是词频, idft表示逆向文件频率.两个对象q和o的文本相似性为
| ${f_t}(q, o) = 1 - \frac{{\sum\nolimits_{t \in q.T} {{w_{t, o}}} }}{{\max P}}$ | (2) |
定义3(空间文本相似性).结合定义1和定义2, 任意两个空间文本对象的相似性为
| $f(q, o) = \alpha {f_s}(q, o) + (1 - \alpha ){f_t}(q, o)$ | (3) |
其中, α(α∈[0,1])是一个可调节参数, 用以调节空间距离与文本相似性之间的重要程度.f(q, o)的值越小, q与o的空间文本相似性就越大.
本文问题描述如下:设空间文本对象集合O={o1, o2, …, on}, 用户查询q=(loc, T, d, k).loc是用户查询所在位置, T是由一系列查询关键字组成的集合, d是用户可以接受的最远距离, k即最近邻对象个数, 其中, d的优先级比k高.受限Top-k空间关键字查询即从O中查找在距离d范围内空间文本相似性最高的k个被查询对象.其形式化表示见定义4.
定义4(受限Top-k空间关键字查询).设查询对象q和被查询集合O, 一个对象o∈O是查询q的受限Top-k关键字查询结果当且仅当对象o满足
| $ \left| {{o}'} \right|{o}'\in O\And f\left( q,{o}' \right)\le f\left( q,o \right)\left| \le \right.k并且{{f}_{s}}\left( q,o \right)<d $ | (4) |
本文采用倒排聚集线性四分树索引所有的空间文本对象.倒排聚集线性四分树是倒排表与聚集线性四分树的结合.倒排表中的每一个关键字指向一棵聚集线性四分树.图 2是基于图 1中的空间文本对象建立的倒排聚集线性四分树示例.
|
Fig. 2 Aggregate inverted linear quadtree 图 2 聚集倒排线性四分树 |
一个关键字对应一棵聚集线性四分树.该树由包含该关键字的所有空间文本对象组成, 那些不包含该关键字的对象不会在该聚集线性四分树中被索引.“聚集”是指在树中每一个节点中都存储一个聚集值, 即该关键字在此节点下的最大权重.如图 4所示, “coffee”对应的线性四分树的根节点中的0.176表示树下所有的对象{o1, o3, o4, o5}中“coffee”的权重均不大于0.176.线性四分树源于四分树, 与四分树不同的是, 线性四分树以B+-树的形式存储空间位置的编码值, 不是直接存储空间位置(编码方法将在本节后面加以阐述).此外, 线性四分树中不存储不包含任何对象的空间码值.若采用四进制Morton码对图 1所示的空间进行编码, 其结果可如图 3所示.包含“coffee”关键字的对象有{o1, o3, o4, o5}, 将这些对象所在位置对应的Morton码用B+-树索引起来即形成“coffee”关键字对应的聚集线性四分树, 如图 4所示.类似地, “cinema”对应的聚集线性四分树如图 5所示.图 4和图 5中的两棵聚集线性四分树是图 2中“coffee”和“cinema”的关键字对应的聚集线性四分树的详细版.
|
Fig. 3 Encoded space 图 3 空间编码 |
|
Fig. 4 Aggregate linear quadtree w.r.t. coffee 图 4 “coffee”对应的聚集线性四分树 |
|
Fig. 5 Aggregate linear quadtree w.r.t. cinema 图 5 “cinema”对应的聚集线性四分树 |
空间位置可遵循一定的规则进行编码, 常用的有四进制或十进制Morton码, 本文采用四进制Morton码.文献[40]对空间位置编码方法进行了详细阐述, 这里仅作简要说明.编码过程需要借助四分树, 设四分树最大层次为r.自顶向下地对空间位置进行四等分直至层数r.在任意层次h(h≤r)下, 将SW、SE、NW、NE这4个方向的等分区域分别标记为0、1、2、3, 如图 6(a)所示.在空间上建立四分树(如图 6(b)所示).四分树上一个h层的空间位置可用一个h位的四进制串表示, 称为位置Morton码.如在图 6(b)所示的第3层, 任意一个空间位置都是一个3位的四进制串.四进制串中从左向右的任意一位表示的是该位置在相应层次的方向.具体地, 第3层的Morton码左侧第1位数字表示该节点在四分树深度为1时区域位于的方向.如图 6(b)所示的中间4个区域的编码为120、121、122、123, 其中左侧第1位的“1”表示这4个区域均处于四分树第1层的SE方向.左侧第2位数字表示深度为2时该节点所属区域的方向.继续上面的例子, 左侧第2位的“2”表示这4个区域均处于四分树第2层划分的NW方向.第3位的0、1、2、3表示第3层上4个方向的划分.在线性四分树中索引的均是底层(最深层)的Morton码.因此, 采用Morton码对图 1所示的空间进行编码, 图 3和图 6(b)所示的最底层叶子节点编码是一致的.
|
Fig. 6 Encoded Morton 图 6 Morton编码 |
线性四分树是将上述非空叶子节点的四进制Morton码值以数字的形式索引起来.综上所述, 聚集线性四分树AIL的创建算法如算法1所示.
算法1.构建倒排聚集线性四分树AIL.
Input:空间文本对象集合O, 关键字域值D;
Output:倒排聚集线性四分树AIL.
1.为所有的查询关键字创建倒排表AIL;
2.for每一个对象o∈O
3. cm=计算对象o的Morton码;
4. for关键字w∈o.T //对于对象o中的每一个关键字
5. if cm不在关键字w对应的B+-树中
6. 将cm插入到w对应的B+-树;
7. else
8. 在cm对应的叶子节点中添加对象o;
9.为AIL中所有的节点添加聚集值;
4 基于OR语义的受限Top-k空间关键字查询算法本文的研究目标是基于AIL, 从带有空间位置和文本信息的对象集合O中, 寻找在受限范围内与查询q空间文本相似性最高的k个对象.AIL融合了空间与文本信息, 其中的线性四分树实质存储的是空间位置编码, 倒排文件中存储了文本信息.所以, 基于AIL进行Top-k空间关键字查询有两种思路:(1)将线性四分树转化为空间上的四分树, 改进已有经典算法, 这是设计VQuad算法的初衷(详见第4.2节); (2)从线性四分树的空间编码入手, 直接在编码后的空间上进行查询, 这是设计VGrid算法的动机(详见第4.3节).在介绍具体算法之前, 我们先来说明在两种算法中都将用到的定义和定理.
4.1 相关定义在后续算法中需要计算查询点到一个覆盖多个对象的矩形的空间文本相似性.因此, 下面首先定义扩展的空间文本对象, 然后说明如何利用定义3计算查询点到扩展空间文本对象的空间文本相似性.
定义5(扩展的空间文本对象).扩展的空间文本对象R包含地理位置和文本关键字集合两个部分, 其形式化的表示为
以图 7为例说明定义5.图 7显示了一个扩展的空间文本对象R, 其中, R.loc覆盖对象o3和o4.R.T={coffee (0.088), cinema(0.075), library(0.119), swim(0.151)}.
|
Fig. 7 Extended spatio-textual object R 图 7 扩展的空间文本对象R |
在扩展的空间文本对象上, 依然可以利用公式(3)计算查询q与扩展空间文本对象R的空间文本相似性.其中, 空间相似性采用查询q到矩形R.loc的最小空间距离, 文本相似性采用公式(2)即可.
下面的定理1证明了查询q与扩展的空间文本对象R的空间文本相似性是查询q到R中覆盖的任意对象的空间文本相似性的上限.
定理1.对于R下覆盖的任意对象o, f(q, R)≤f(q, o).
证明:从空间和文本两个角度证明.
从空间的角度, 易知对于R中包含的任意对象o, 对象o到查询点q的空间距离不小于R到q的空间距离, 即
从文本的角度, 易知对于R中的任意对象o, o.t∈R.T, 对象o对应于查询q的文本权重不大于R对应于查询q.T的文本权重, 即
综合上述空间和文本两个角度, 由公式(3)可得f(q, R)≤f(q, o).由于f(q, o)的值越小越好, 因此查询q与R的文本相似性是查询q到R中覆盖的任意空间文本对象的空间文本相似性的上限.
4.2 VQuad算法VQuad算法的基本思想是采用最小最佳优先原则, 利用AIL中存储的空间位置重建虚拟四分树[16], 在虚拟四分树上寻找满足OR语义的空间受限的k最近邻查询结果.文献[16]在虚拟四分树上进行Top-k关键字查询处理, 但其仅实现了AND语义.VQuad算法改进了文献[16]以支持OR语义的空间受限查询.下面首先简要介绍线性四分树与虚拟四分树的转换过程.接下来, 在虚拟四分树的基础上详细介绍VQuad查询处理方法.
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行).最后, 当结果集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行).
|
Table 1 A running example of VQuad 表 1 VQuad算法运行实例 |
重复上述操作, 直至表 1第4行, 取当前栈顶e=(330, 330).因为单元(330, 330)是叶子节点.从与查询关键字对应的B+-树中取出330单元以下的对象, 即{o2}.因为o2与查询点q的距离小于d, 则计算查询点q到对象o2的空间文本相似性.将对象及其与查询q的空间文本相似性的值入栈nbs中(见表 1中第4行).第5行中, 取栈顶e=o2, 因为o2是空间文本对象, 将o2存入结果集.此时k=1, 且栈nbs中栈顶元素的空间文本相似性上限小于当前查询结果中最差的空间文本相似性, 由定理1可知, 程序停止.输出结果集R={(o2, 0.510)}.
算法2.基于虚拟四分树的OR语义查询排序算法VQUAD.
Input:ALT:聚集倒排线性四分树, k:要求返回对象的个数, d:空间距离约束, q:查询对象;
Output:R:前k个f值最小的对象集合.
1. R=Ønbs=Ø
2. btset=AIL中所有与q.T相对应的聚集线性四分树;
3.将虚拟四分树的根节点入栈nbs;
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中的n0~n7所示)中包含的对象, 计算该对象与查询q的空间文本相似性, 不断更新查询结果集直至获得满足空间限制的Top-k结果.为了防止空间单元的重复访问, 采用visit布尔集合来标识单元是否已被访问.
|
Fig. 9 The eight neighbor cells for the cell 303 图 9 303单元的8个邻近单元 |
具体地, 首先找到查询点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个对象的空间文本相似性值优于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分别对应的线性四分树为bt1和bt2(即图 3和图 4).栈顶元素303出栈.虽然单元303到查询点q的距离小于d, 但303没有在bt1和bt2中, 说明303中没有对应查询文本的对象.利用公式(5)计算303的相邻8个单元, 即{300, 301, 310, 312, 330, 321, 320, 302}.计算查询q到每一个单元的空间文本相似性, 见表 2的第1行.将单元Morton码值及其与查询对应的空间文本相似性值按升序存入栈nbs中, 并在visit中将这些单元标记为已访问.
从栈nbs中取栈顶330.因为330到查询点q的距离小于d, 取出树bt1和bt2中330单元对应的对象, 去重后得h={o2}.计算o2与查询q的空间文本相似性f=0.510, 并存入结果集R={(o2, 0.510)}.此时, 结果集R中对象o2的空间文本相似性大于栈顶元素与查询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中o2与查询q空间文本相似性小于栈顶元素对应的空间文本相似性(即0.510 < 0.576).所以, 程序终止.输出的结果集R={(o2, 0.510)}.
|
|
Table 2 Running instance of VGRID 表 2 VGRID算法运行实例 |
(3) 邻近8个单元的计算方法
Morton码[23]是空间网格划分后每一个单元(cell)的唯一标识, 与单元的空间坐标可进行相互转换.利用这个性质, 通过二进制位运算很容易获得某单元周围邻近8个单元的码值乃至位置坐标.下面首先说明Morton码与空间坐标的相互转换方法, 接下来说明如何通过二进制的位运算在O(1)时间内获得邻近单元的码值.
已知某单元的十进制坐标为(x, y), 其Morton码的具体计算方法如下.先将单元位置坐标(x, y)的值转化为二进制形式, 令x=xr-1...x1x0, y=yr-1...y1y0, 其中, xi, yi∈{0, 1}, r为线性四分树划分的深度.该单元对应的二进制编码为n=yr-1xr-1...y1x1y0x0.例如, 图 3中单元303的坐标为(5, 5), 将两个坐标转化为二进制, 分别是x=110, y=110, 则该单元对应的编码为n=110011, 转化为四进制后即Morton码为303.
在算法3的第13行需要查找中心单元邻近的8个单元, 如图 9所示.其中, 任意单元的8个邻近单元的计算方法如公式(5)[36].设中心单元的Morton码值为code, 则有:
| ${m_q} = {n_q}{ \oplus _q}\Delta {n_i} = ((({n_q}|{t_y}) + (\Delta {n_i} \wedge {t_x})) \wedge {t_x})|((({n_q}|{t_x}) + (\Delta {n_i} \wedge {t_y})) \wedge {t_y})$ | (5) |
在公式(5)中, mq是邻近单元Morton码的二进制表示.nq是中心单元code的二进制表示.tx和ty是两个二进制常数: tx=01...0101表示“01”重复r次, ty=10...1010表示“10”重复r次.Δni是基本方向增量之一, 即计算中心单元任意方向的单元码值时坐标的变化量, 8个方位的基本增量即Δn0= (-1, -1), Δn1=(0, -1), Δn2=(1, -1), Δn3=(1, 0), Δn4=(1, 1), Δn5=(0, 1), Δn6=(-1, 1), Δn7=(-1, 0).采用上文单元码值的计算方法, 将∆ni由坐标值转换为Morton码(见表 3第2列).公式(5)采用的是位运算:“+”表示相加; “|”表示OR; “^”表示AND.设线性四分树划分深度r=3, 计算中心单元303(转换成二进制为110011)的邻近8个单元码值的过程见表 3.
|
|
Table 3 Increment of direction 表 3 方向增量 |
5 实验 5.1 实验设置
实验采用Foursquare上真实的签到数据集[41, 42], 包括纽约(NYC)和洛杉矶(LA)两个城市用户的签到数据.图 10和图 11展示了将两个数据集导入QGIS后, 签到兴趣点POI(point of interests)的分布情况.表 4列出了数据集的统计信息, 包括POI数量、键字数量以及每个POI上的平均关键字数.实验中的所有算法用Java实现.运行于Intel(R) i5 2.30GHzCPU处理器、4GB内存的Windows 8计算机上.实验中, 所有的POI组成被查询点集合.查询点集合从POI集合中随机抽取10 000个.随机抽取的点位置即查询点位置信息.查询点的文本关键字按照不同等级的词频随机分配.文本关键字的等级是根据关键字词频的上四分位、中位数划分的3个等级(即高频、中频和低频词).实验默认设置见表 5.
|
Fig. 10 LA check-in datasets 图 10 LA签到数据集 |
|
Fig. 11 NYC check-in datasets 图 11 NYC签到数据集 |
|
|
Table 4 Statistics for the dataset 表 4 数据集的统计信息 |
|
|
Table 5 Default setting 表 5 实验默认设置 |
文献[16]是第1篇在线性四分树上进行Top-k关键字查询的代表性工作, 但其仅支持AND语义.本文提出的VQuad算法是在文献[16]中提出的基于虚拟四分树算法基础上的改进, 所以在支持OR语义方面, 实验仅对比了VQuad算法和VGrid算法在两个不同数据集上平均查询时间的变化情况(见第5.2节).为了验证两种算法在AND语义方面的有效性, 第5.3节对两种算法支持AND语义的实验结果进行了对比分析.实验变动参数有关键字个数(l)、返回结果数(k)、数据集大小等.由于文献[16]已验证了倒排线性四分树与经典索引结构的对比情况, 这里没有再对索引结构大小等进行赘述.
5.2 支持OR语义的算法性能对比图 12对比展示了VQuad和VGird算法在两个不同真实数据集上的查询平均处理时间.从图 12观察到两种算法在LA和NYC数据集上的性能表现类似.从图 10和图 11可以看出, 两个签到数据集POI分布类似且POI个数接近.无论是在LA的数据集上还是在NYC的数据集上, VGird的平均处理时间均优于VQuad.其原因在于, VQuad算法需要多次访问查询关键字对应的线性四分树.具体地, VQuad查询过程中采用的虚拟四分树是一个逻辑概念上的结构, 物理上并不存在.因此, 每次访问到某一个层次的四分树节点时, 需要进行物理上线性四分树存储的Morton码到虚拟四分树的转换(见第4.2.1节).同时, VQuad算法在计算非叶子节点与查询点的空间文本相似性时, 需要该节点下覆盖对象的查询关键字的最大权重.然而, 线性四分树上存储的是虚拟四分树上叶子节点中所有对象在对应关键字的最大权重.因此, 虚拟四分树的非叶子节点的关键字最大权重需要从该节点下的所有叶子节点获得, 导致线性四分树的重复访问, 影响了查询效率.相比之下, 在空间方面, VGird算法中通过二进制的位运算(见公式(5))直接获得附近单元位置, 利用visit布尔数组防止了单元的重复访问; 在文本关键字方面, VGird直接运用的是聚集线性四分树中存储的每个关键字的最大权重.因此, 查询效率得到了明显提高.
|
Fig. 12 Performance on different datasets 图 12 不同数据集上的查询平均处理时间 |
图 13对比展示了查询平均处理时间在不同查询关键字个数l下的变化情况.这里用LVQuad和LVGrid分别表示在LA数据集运行VQuad算法和VGrid算法.NVQuad和NVGrid分别表示在NYC数据集上运行VQuad算法和VGrid算法.查询关键字数量从1增加到5.随着查询关键字个数的增加, VQuad和VGrid均需要访问更多的关键字对应的线性四分树, 因此查询平均处理时间会随着关键字个数的增加而增加.图 13印证了我们的想法, 两种算法的查询平均处理时间均随着查询关键字个数的增加亦在增长.然而, 两种算法的增加幅度是逐渐降低的.这是因为在OR语义环境下, 更多的查询关键字意味着用户对查询需求的放松.线性四分树中会有更多的候选结果供选择.在k确定的前提下, 一定程度地舒缓了查询时间的增长幅度.通过对比图 13中的4条曲线可以发现, 无论是在LA数据集还是在NYC数据集下, VGrid算法的查询效率均比VQuad算法要好, 由图 13可以看出, VGrid比VQuad平均快2.5倍.
|
Fig. 13 Performance on different number of query keywords 图 13 不同查询关键字数量上的查询平均处理时间 |
图 14对比展示了查询平均处理时间在不同查询返回结果个数k下的变化情况.观察图 14发现, 两种算法的平均处理时间均随着查询返回结果的个数k的增加而增加.显而易见, 由于用户提高了查询要求, 两种算法均需要更多的时间在空间中寻找满足查询要求的结果.同时, 从图 14还可以发现, 随着k的增大, 在相同的数据集上, VQuad算法的增长幅度比VGrid平均要大0.05ms.这是因为, 随着查询返回结果个数的增加, VQuad算法访问了虚拟四分树上更多的非叶子节点, 增加了对关键字权重的计算次数, 而VGrid算法可直接在线性四分树上获取关键字权重, 相比之下提高了查询的效率.最终, 从图 14可以看出, VGrid算法在两个数据集的查询平均处理时间相差不大(约差0.07ms).
|
Fig. 14 Performance on different k 图 14 不同查询结果数量上的查询平均处理时间 |
我们从原始数据集中随机抽取50 000、100 000、150 000、200 000个POI对象组成了不同的被查询对象集合.从图 10和图 11可以看出, 两个数据集中的POI不是均匀分布的.所以, 不同大小的数据集不是在整个空间上均匀增长, 而是随着POI分布的密集程度而增长.图 15对比显示了查询平均处理时间在不同POI数据集大小下的变化情况.可以看出, 整体上来看, 两种算法的性能均随着数据集数量的增加而下降.平均而言, 随着POI数量的增加, 在四分树上一个节点或网格单元下覆盖的POI数量会增多.这就造成了从一个四分树节点或网格单元下需要抽取更多的POI对象进行检验.但无论在哪个数据集上, VGrid的性能都是优于VQuad的.我们发现, 两种算法在数据从150 000增长到200 000时, NYC数据集上的增长幅度高于LA数据集.通过分析图 10和图 11后发现, 在相同的POI集合大小下, NYC数据集比LA的数据集分布得更为分散.整体上来看, 两种算法在处理时间上是高效的, VQuad在1.1ms以下, VGrid在0.43ms以下.
|
Fig. 15 Performanceon different datasize 图 15 不同大小的数据集上的查询平均处理时间 |
图 16对比展示了查询平均处理时间在不同α值下的变化.α是一个可调节参数, 用来调节空间相似性与文本相似性的重要程度.α越大表示空间相似性的重要程度越大, 反之, 文本相似性的重要程度越大.由图 16可以看出, 当α从0.1变到0.9时, 两种算法在LA数据集和NYC数据集上的平均查询处理时间均保持平稳, 两种算法的性能始终保持大约0.5ms的差距.
|
Fig. 16 Performance on different α 图 16 不同参数值α上的查询平均处理时间 |
由于VGrid中递归计算邻近8个单元, 为了验证算法在空间搜索方面的效率, 图 17对比展示了VGrid算法在两个数据集上的空间搜索占比的变化情况.空间搜索占比即查找到用户要求的k个最近邻结果, 算法遍历过的空间与整个空间面积比值.k从10增加到50.此时, d被设置为无穷大.由图 17可以看出, 查询搜索空间占比会随着查询返回结果个数的增加而增加.这是比较自然的现象, 因为满足要求的结果分布在更远的单元.有趣的是, 相同k值设置下NVGrid要找到查询结果, 比LYGrid搜索的空间更广.这从另一方面验证了在NYC上的查询平均处理时间比在LA上要更长.即使k增长到50, 搜索空间的占比也低于4.5%.
|
Fig. 17 Percentage on different k 图 17 不同查询结果数量上的搜索空间占比 |
5.3 支持AND语义的算法性能对比
本文提出的VGrid算法和VQuad算法可同时支持OR语义和AND语义.为了全面验证算法的性能, 本节对比展示了两种算法在支持AND语义方面的性能.
图 18对比展示了VQuad和VGrid算法在支持AND语义时在两个真实数据集上的平均查询处理时间.与支持OR语义的情况相比, 其相同之处是, 在两个数据集上, 算法VGrid的平均处理时间依然均优于VQuad; 不同之处在于, 从整体上来讲, VQuad在OR语义上运行的时间比AND语义长0.2ms, 而VGrid在AND和OR语义上的运行时间很近, 平均都是0.49ms.这是因为, VQuad算法的处理单位是虚拟四分树上的节点, 而VGrid的处理单位是网格单元.基于虚拟四分树的VQuad本质上是一种自顶向下的算法, 在支持AND语义时, 节点剪枝效果更明显, 而VGird本质上是基于中心单元的遍历, 所以AND语义与OR语义差别不大.
|
Fig. 18 Performance on different datasets w.r.t AND constraints 图 18 不同数据集上支持AND语义的查询效率 |
图 19对比展示了查询平均处理时间在查询关键字数量从1增加到5的变化情况.随着查询关键字个数的增加, VQuad和VGrid的查询平均处理时间均有所增加, 其原因与支持OR语义的原因相同, 这里不再赘述.在l=1时, AND语义与OR语义无差异.当l继续增加时, 4条线均在l增加到3时发生了陡变.当l增加到4、5时, 增长速率减缓.图 20对比展示了AND语义下两种算法在不同返回结果个数k下的变化情况.从图 20不难发现, 两种算法的平均处理时间大体上均随着查询返回结果的个数k的增加而增加.从两组数据来看, VGrid较VQuad性能更稳定.平均来讲, 在不同数据集上, VQuad的平均查询处理时间为1.25ms, VGrid的平均查询处理时间是0.69ms.图 21和图 22对比展示了POI数据集大小、参数α值变化时算法的性能.两者的变化趋势与图 15、图 16类似, 这里也不再赘述.
|
Fig. 19 Performance on different number of query keywords w.r.t AND constraints 图 19 不同查询关键字数量上支持AND语义的查询效率 |
|
Fig. 20 Performance on different number results w.r.t AND constraints 图 20 不同查询结果数量上支持AND语义的查询效率 |
|
Fig. 21 Performanceon different size of query datasets w.r.t AND constraints 图 21 不同大小的数据集上支持AND语义的查询查询效率 |
|
Fig. 22 Performance on different α 图 22 不同参数值α上支持AND语义的查询效率 |
6 总结
基于位置的地理信息服务在人们的生活中发挥着越来越重要的作用, 针对空间文本对象查询的研究成为工业界和学术界关注的研究热点问题之一.为了给用户提供更多高品质的选择结果, 本文针对基于聚集倒排线性四分树的高效OR语义的受限Top-k空间关键字查询的问题进行了研究.综合考虑空间距离、空间文本相似程度的需求, 基于聚集倒排线性四分树, 分别提出基于虚拟四分树的VQuad和基于虚拟网格的VGrid算法.两种算法均可同时支持AND语义和OR语义.通过一系列的实验发现, 由于VGrid直接利用了线性四分树上空间编码的特点, 在所有的实验设置中其性能均优于VQuad且算法性能更稳定.未来考虑将此技术思想应用到在道路网络上的查询研究中.
| [1] |
Zhu H, Yang X, Wang B, Lee WC. Range-based obstructed nearest neighbor queries. In: Proc. of the ACM SIGMOD. 2016. 2053-2068.
|
| [2] |
Li Y, Huang Z, Zhu R, Li G, Shu L, Tian S, Ma M. Parameterized spatio-textual publish/subscribe in rode sensor networks. IEEE Access, 2017, 5(99): 22940-22952.
http://www.onacademic.com/detail/journal_1000040191127310_8cf6.html |
| [3] |
Sanderson M, Kohler J. Analyzing geographic queries. In: Proc. of the Int'l ACM SIGIR Conf. 2004.
|
| [4] |
Chan KH, Long C, Wong CW. On generalizing collective spatial keyword queries. IEEE Trans. on Knowledge and Data Engineering, 2018, 30(9): 1712-1726.
[doi:10.1109/TKDE.2018.2800746] |
| [5] |
Han XX, Yang DH, Li JZ. TKEP:An efficient top-K query processing algorithm on massive data. Chinese Journal of Computers, 2010, 33(8): 1405-1417(in Chinese with English abstract).
http://www.cqvip.com/Main/Detail.aspx?id=34873202 |
| [6] |
Zhu R, Wang B, Yang X, Zheng B, Wang G. SAP:Improving continuous top-k queries over streaming data. IEEE Trans. on Knowledge and Data Engineering, 2017, 29(6): 1310-1328.
[doi:10.1109/TKDE.2017.2662236] |
| [7] |
Hu HQ, Li GL, Bao ZF, Feng JH, Wu YW, Gong ZG, Xu YQ. Top-k spatio-textual similarity join. IEEE Trans. on Knowledge and Data Engineering, 2016, 28(2): 551-565.
[doi:10.1109/TKDE.2015.2485213] |
| [8] |
Wang Y, Jian X, Yang ZH, Li J. Query optimal k-plex based community in graphs. Data Science and Engineering, 2017, 2(4): 274-274.
[doi:10.1007/s41019-017-0059-8] |
| [9] |
Yang J, Zhang Y, et al. Categorical top-k spatial influence query. World Wide Web, 2017, 20: 175-203.
[doi:10.1007/s11280-016-0383-3] |
| [10] |
Cong G, Jensen CS, Wu D. Efficient retrieval of the top-k most relevant spatial Web objects. Proc. of the VLDB Endowment, 2009, 2(1): 337-348.
[doi:10.14778/1687627.1687666] |
| [11] |
Chan KH, Li C. Hybrid indexing and seamless ranking of spatial and textual features of Web documents. In: Proc. of the SSTD. 2017. 357-375.
|
| [12] |
Li ZS, Lee KC, Zheng BH, Lee WC, Lee D, Wang XF. IR-tree:An efficient index for geographic document search. IEEE Trans. on Knowledge and Data Engineering, 2011, 23(4): 585-599.
|
| [13] |
Rochajunior JB, Gkorgkas O, Jonassen S, Nørvåg K. Efficient processing of top-k spatial keyword queries. In: Proc. of the SSTD. 2011. 205-222. https://ieeexplore.ieee.org/document/5560653
|
| [14] |
Liu XP, Wan CX, Liu DX, Liao GQ. Survey on spatial keyword search. Ruan Jian Xue Bao/Journal of Software, 2016, 27(2): 329-347(in Chinese with English abstract).
空间关键字搜索研究综述 [doi:10.13328/j.cnki.jos.004934] |
| [15] |
Zhang D, Tan KL, Tung AKH. Scalable top-k spatial keyword search. In: Proc. of the EDBT. 2013. 359-370.
|
| [16] |
Zhang CY, Zhang Y, Zhang WJ, Lin XM. Inverted linear quadtree: Efficient top k spatial keyword search. In Proc. of the ICDE. 2013. 901-912.
|
| [17] |
Wu DM, Yiu ML, Cong G, Jensen CS. Joint top-k spatial keyword query processing. IEEE Trans. on Knowledge and Data Engineering, 2012, 24(10): 1889-1903.
[doi:10.1109/TKDE.2011.172] |
| [18] |
Felipe ID, Hristidis V, Rishe N. Keyword search on spatial databases. In: Proc. of the ICDE. 2008. 656-665.
|
| [19] |
Chen L, Xu JL, Lin X, Jensen CS, Hu HB. Answering why-not spatial keyword top-k queries via keyword adaption. In: Proc. of the ICDE. 2016. 697-708.
|
| [20] |
Chan KH, Long C, Wong CW. Inherent-cost aware collective spatial keyword queries. In: Proc. of the SSTD. 2017. 357-375.
|
| [21] |
Zhang DX, Chan CY, Tan KL. Processing spatial keyword query as a top-k aggregation query. In: Proc. of the SIGIR. 2014. 355-364.
|
| [22] |
Wu DM, Cong G, Jensen CS. A framework for efficient spatial Web object retrieval. VLDB Journal, 2012, 21(6): 797-822.
[doi:10.1007/s00778-012-0271-0] |
| [23] |
Chen LS, Cong G, Cao X, Tan KL. Temporal spatial-keyword top-k publish/subscribe. In: Proc. of the ICDE. 2015. 255-266.
|
| [24] |
Liu J, Ke D, Sun H, Ge Y, Zhou X. Clue-based spatio-textual query. Proc. of the VLDB Endowment, 2017, 10(5): 529-540.
|
| [25] |
Wang J, Gao H, Li J, Yang D. An index supporting spatial approximate keyword search on disks. Journal of Computer Research and Development, 2012, 49(10): 2142-2152.
http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jsjyjyfz201210010 |
| [27] |
Yao B, Li FF, Hadjieleftheriou M, Hou K. Approximate string search in spatial databases. In: Proc. of the ICDE. 2010. 545-556.
|
| [28] |
Lin X, Xu JL, Hu HB. Reverse keyword search for spatio-textual top-k queries in location-based services. In: Proc. of the ICDE. 2017. 375-386.
|
| [29] |
Zheng K, Zhou XF, Fung PC, Xie KX. Spatial query processing for fuzzy objects. VLDB Journal, 2012, 21(5): 729-751.
[doi:10.1007/s00778-012-0266-x] |
| [30] |
Cary A, Wolfson O, Rishe N. Efficient and scalable method for processing top-k spatial Boolean queries. In: Proc. of the SSDBM. 2010. 87-95.
|
| [31] |
Gao YJ, Qin X, Zheng BH, Chen G. Efficient reverse top-k Boolean spatial keyword queries on road networks. IEEE Trans. on Knowledge and Data Engineering, 2015, 27(5): 1205-1218.
[doi:10.1109/TKDE.2014.2365820] |
| [32] |
Chen G, Zhao JW, Gao YJ, Chen L, Chen R. Time-aware Boolean spatial keyword queries. IEEE Trans. on Knowledge and Data Engineering, 2017, 29(1): 2601-2614.
http://ieeexplore.ieee.org/document/8014478/ |
| [33] |
Zhao PP, Fang HL, Sheng VS, Li ZX, Xu JJ, Wu J, Cui ZM. Monochromatic and bichromatic ranked reverse Boolean spatial keyword nearest neighbors search. World Wide Web, 2017, 20(1): 39-59.
[doi:10.1007/s11280-016-0399-8] |
| [34] |
Li GL, Feng JH, Xu J. DESKS: Direction-aware spatial keyword search. In: Proc. of the ICDE. 2012. 474-485.
|
| [35] |
Wu DM, Yiu ML, Jensen CS, Cong G. Efficient continuously moving top-k spatial keyword query processing. In: Proc. of the ICDE. 2011. 541-552.
|
| [36] |
Huang WH, Li GL, Tan KL, Feng JH. Efficient safe-region construction for moving top-k spatial keyword queries. In: Proc. of the CIKM. 2012. 932-941.
|
| [37] |
Shi JM, Wu DM, Mamoulis N. Textually relevant spatial skylines. IEEE Trans. on Knowledge and Data Engineering, 2016, 28(1): 224-237.
[doi:10.1109/TKDE.2015.2465374] |
| [38] |
Choudhury FM, Culpepper JS, Sellis T, Cao X. Maximizing bichromatic reverse spatial and textual k nearest neighbor queries. Proc. of the VLDB Endowment, 2016, 9(6): 456-467.
|
| [39] |
Xie X, Lin X, Xu J, Jensen CS. Reverse keyword-based location search. In: Proc. of the ICDE. 2017. 375-386.
|
| [40] |
Aizawa K, Motomura K, Kimura S, Kadowaki R, Jia F. Constant time neighbor finding in quadtrees: An experimental result. In: Proc. of the Int'l Symp. on Communications, Control and Signal Processing. 2008. 505-510.
|
| [41] |
Bao J, Zheng Y, Mokbel MF. Location-based and preference-aware recommendation using sparse geo-social networking data. In: Proc. of the SIGSPATIAL. 2012. 199-208.
|
| [42] |
Wei LY, Zheng Y, Peng WC. Constructing popular routes from uncertain trajectories. In: Proc. of the KDD. 2012. 195-203.
|
| [5] |
韩希先, 杨东华, 李建中. TKEP:海量数据上一种有效的Top-K查询处理算法. 计算机学报, 2010, 33(8): 1405-1417.
http://www.cqvip.com/Main/Detail.aspx?id=34873202 |
| [14] |
刘喜平, 万常选, 刘德喜, 廖国琼. 空间关键字搜索研究综述. 软件学报, 2016, 27(2): 329-347.
空间关键字搜索研究综述 [doi:10.13328/j.cnki.jos.004934] |
| [26] |
Hu J, Fan J, Li GL, Chen SS. Top-k fuzzy spatial keyword search. Chinese Journal of Computers, 2012, 35(11): 2237-2246(in Chinese with English abstract).
|