2020, Vol. 41
随着移动终端设备以及基于位置的服务(location-based service, LBS)的快速发展, 移动查询作为LBS中的一个重要类别, 近些年得到了广泛关注.其中, 移动k近邻(moving k nearest neighbor, MkNN)查询是移动查询领域的当前研究热点[1-2].给定一个移动对象q以及一个静态数据对象集合P，当q移动时, MkNN查询连续返回q的k个最近邻对象.该查询具有广泛的应用, 例如:为城市中漫步的游客连续推荐k个最近邻的景点或餐馆；为正在高速公路行驶的司机连续找到k个最近的加油站.
然而, 通常情况下MkNN查询返回的k个对象间的距离较近, 空间位置形成聚集且拥有相似的周边环境, 这样的结果有时并不能让用户满意.例如, 查询结果均位于火车站附近, 那里通常交通拥堵, 停车困难.为了增强查询结果的可用性, 避免产生空间聚集的结果, 查询结果空间多样化是一种常用的手段[3-4].空间多样化技术使得查询结果在满足用户需求的同时, 相互之间距离较远.正如文献[3]中描述, 进行空间查询的用户更加偏好距离查询位置近, 并且空间多样化的结果.用户可以根据对象的周边环境(比如是否有步行可达的商场或体育馆)或对区域的偏好(比如旅行者喜好探索未曾去过的区域)来进行选择.
根据以上应用需求, 本文提出了空间多样化约束下的移动k近邻(moving k nearest neighbor query with spatial diversity constraints, SDC-MkNN)查询.当查询对象移动时, 连续返回距离查询对象最近的k个对象, 并且要求结果对象间相互距离不小于距离阈值.在此, 本文使用欧氏距离来度量对象之间的相互距离, 这样可以充分体现对象间的空间位置关系.例如, 在为旅行者推荐景点时, 如果使用MkNN查询, 返回的结果由于位置接近, 可能已被全部访问.此时, 用户更倾向于使用SDC-MkNN查询为其推荐彼此相距较远的结果.
对于SDC-MkNN查询, 一种简单的解决方法是在查询对象移动的每个时间戳, 都将其作为静态查询来处理.然而, 求解空间约束下的k近邻问题为NP-hard问题, 频繁地重新计算查询结果会花费大量的运行时间.因此, 如何有效地减少重复计算次数, 提高查询效率是本文的挑战.安全区域技术[1]是解决移动查询问题的常用方法, 但现有技术并未考虑结果对象之间的距离约束关系.
针对以上问题, 本文首先提出了支配区域的概念.当查询对象在某个区域内移动时, 如果对象集Si始终优于对象集Sj, 则称该区域为Si对于Sj的支配区域.基于这个概念, 计算出了安全区域Re, 并且提出了一种精确算法.为了进一步提高查询效率, 仅用最优结果集构建出近似安全区域Rρ, 并且提出了一种近似算法.当查询对象在Rρ中移动时, 查询结果保持不变, 并且该集合始终为当前位置最优结果集的ρ近似解.从实验结果看出, 近似算法进一步降低了重新计算查询结果的次数.
1 相关工作近些年, MkNN查询被广泛研究.先前工作通常采用基于Voronoi图的方法来构建安全区域.一个k阶Voronoi图由若干个区域组成，只要查询对象位于同一个区域中, 查询结果始终为形成该区域的k个对象.文献[1]提出的V*-Diagram方法能够快速计算出一个近似k阶Voronoi图的区域.文献[2]提出了influential neighbor set方法, 通过使用safe guarding对象维护当前kNN.以上方法均未考虑对象间的距离关系.文献[5]提出了移动k多样化近邻查询问题, 与本文查询目标类似, 但其采用双目标评价函数(相关性与多样性之和)来评价对象集, 通过参数来调节两者之间的比重, 返回具有最大目标函数值的对象集.然而, 对于查询用户来说参数调节困难, 导致查询结果可能相关性较高且仍空间聚集.本文采用更加简洁的度量模型(距离和), 并且要求查询结果相互之间满足距离约束, 从而有效避免了空间聚集现象的产生.
查询结果多样化被广泛运用于时空查询领域.文献[6]提出了k最近多样化邻居(kNDN)问题, 找到满足多样化约束的k个近邻对象, 使用Gower Coefficient函数来度量对象之间的多样性, 并且提出了启发式搜索算法来解决该问题.文献[7]研究k多样化近邻查询问题.在Hamming空间内, 根据查询对象位置以及查询半径, 找到一个由k个对象组成的, 并且多样化程度最大的集合.集合的多样化程度由其中任意两个对象之间的距离的最小值来度量(值越大, 多样化程度越高).文献[8-9]研究角度多样性, 对象之间的多样化程度是通过目标对象相对于查询对象的方向之间的差异来定义的.文献[8]的目标是为多边形的查询对象从不同的角度找到近邻对象, 查询结果能够对查询对象周围形成良好的覆盖.文献[9]的目标是发现最优的k个对象能够最大化相关性的同时最小化两两之间的角度相似性.文献[4]提出了路网中的多样化空间关键字查询问题, 目标在于寻找k个对象能够最大化一个由相关性与多样性组成的线性方程.多样性由对象之间的路网距离来定义.并且提出了一种基于签名的倒排索引技术, 结合基于关键字的剪枝技术来减小搜索空间.文献[10]基于线性skylines解决多样化k近邻问题提出了有效算法, 能够快速找到在邻近性与多样性方面均不被占有的结果集.文献[11]提出了具有多样性的top-k最短路径(KSPD)问题.给定查询起点与终点, KSPD找到长度总和最小的k条最短路径, 并且任意两条路径的相似性低于阈值约束.以上工作均为静态查询, 本文研究目标为移动状态下的空间多样化k近邻查询, 因此, 以上方法均不适用.
空间偏好查询是空间查询的一种重要类别, 通过考虑目标对象的空间位置, 以及目标对象周围的特征对象属性对该对象进行评分, 返回前k个目标对象.文献[12]给出了top-k空间偏好查询的定义, 并且使用两类空间约束(即范围约束与最近邻约束)对目标对象进行评分.文献[13]提出位置敏感的组偏好查询, 该查询为一组用户返回一个最优空间对象, 并且通过两个方面来评价对象:①所有用户到该对象的距离和；②该对象到满足所有用户偏好的最近邻点的距离和.文献[14]提出了空间组偏好查询, 该查询为一组用户返回top-k对象, 提出了satisfaction degree模型, 用于对候选对象进行评价.该模型不仅考虑了候选对象与查询对象间的距离因素, 还将候选对象在社交网络中的评分考虑进来.空间偏好查询目的在于返回评分较高的目标对象, 希望目标对象周围能够最大程度地满足用户偏好，但并未考虑返回的k个对象之间的空间距离关系.
2 问题定义本文假设欧式空间中包含一个静态二维数据对象集合P.对于∀pi, pj ∈P, 使用d(pi, pj)代表pi与pj之间的欧式距离.空间多样化约束下的k近邻查询q包括3个参数:查询对象位置λ、查询结果的数量k和空间多样化约束σ, 即q=〈λ, k, σ〉.下文中q也可作为一个移动的查询对象.
定义1 空间多样化约束下的k近邻(SDC-kNN)查询.给定对象集合P及查询q, SDC-kNN查询目标为找到P中的一个大小为k的子集S, S中任意两对象之间距离不小于σ, 并且S中所有对象到q的距离和最小, 即
|
式中:|S|表示S中包含的对象个数；S′代表任意一个大小为k且其中任意两对象之间距离不小于σ的对象集；函数f(q, S)代表q与S中所有对象的距离和, 即
|
定理1 SDC-kNN查询问题是NP-hard问题.
证明 SDC-kNN查询问题可以映射为最大独立集(MIS)问题.MIS的目标为发现图中的最大节点集, 并且要求节点集中任意两个节点之间没有边相连.MIS问题已被证明为NP-hard问题.
首先构建一个图G.集合P中的每个对象映射为G中的一个节点, 如果两个对象之间距离小于σ, 那么就在其对应的节点之间加入一条边.给定一个SDC-kNN查询q, 假设所有节点到查询点的距离都相同且k=|P|, 那么查询q等同于在G中寻找最大独立集.因此, SDC-kNN查询问题为NP-hard问题.证毕.
当查询q移动时, 即q在不同的时间可能位于不同的地点, 该查询变成了空间多样化约束下的移动k近邻查询.
定义2 空间多样化约束下的移动k近邻(SDC-MkNN)查询.给定对象集合P以及移动查询q=〈λ, k, σ〉, 当查询对象移动到λ′时, SDC-MkNN查询连续返回SDC-kNN查询q′=〈λ′, k, σ〉的结果.
当一个SDC-MkNN查询到来时, 首先将其当作静态SDC-kNN查询来处理.由定理1可知, 静态SDC-kNN查询为NP-hard问题, 如果在每个时间戳都根据查询对象的当前位置重新计算, 这将花费大量的代价.因此, 在第3节展示了基于安全区域技术的算法, 有效减少重复计算次数, 提高查询效率.
3 基于安全区域技术的算法解决静态SDC-kNN查询问题可以通过列举集合P中所有大小为k的对象集, 找到满足多样化约束的最优结果集, 时间复杂度为O(|P|k).因此本文重点在于计算当前结果集的安全区域.
3.1 精确算法首先引入支配区域的概念, 基于这个概念使用函数f(·)值最优的两个对象集(top-2)计算出一个安全区域.当查询对象在该区域内移动时, 查询结果保持不变.
1) 支配区域.给定查询q以及两个对象集Si与Sj, 如果q在某个区域内移动时, Si始终优于Sj, 称该区域为Si对于Sj的支配区域.
定义3 支配区域.给定一个SDC-MkNN查询q, Si, Sj⊆P, 为满足多样化约束、大小为k的两个集合, 且满足f(q, Si) < f(q, Sj).Si对于Sj的支配区域表示为D(Si, Sj).当q移动到q′时, 如果q′位于D(Si, Sj)中, f(q′, Si) < f(q′, Sj)始终成立.
下面对支配区域D(Si, Sj)进行数学推导.已知f(q′, Si)=∑px∈Sid(q′, px)，f(q′, Sj)=∑py∈Sjd(q′, py).
根据三角不等式，∀ p∈P，d(q, p)-d(q, q′)≤d(q′, p).用d(q, py)-d(q, q′)替换f(q′, Sj)中的d(q′, py)，得
|
若要使得f(q′, Si) < (q′, Sj)成立，可以让f(q′, Si)< ∑py∈Sj{d(q, py)－d(q, q′)}.
于是可得
|
(1) |
在此，假设Si={px1, px2, …, pxk}，Sj={py1, py2, …, pyk}，且引入变量θi, j=(f(q, Sj)－f(q, Si))/k，并构建以下不等式组：
|
(2) |
显然，若不等式组(2)成立，则不等式(1)一定成立.因此发现，对于不等式
d(q′, pxm)+d(q, q′) < d(q, pxm)+θi, j, m∈[1, k], q′可能的位置构成了一个椭圆型区域Ei, jm.该椭圆以pxm和q为焦点，d (q, pxm) +θi, j为长轴：
|
(3) |
通过对所有椭圆区域取交集，可以得到q′的一个可行区域.只要q′位于该区域中，不等式(1)始终成立.从而保证f(q′, Si) < f(q′, Sj)始终成立.根据定义3可知，该区域是Si对于Sj的支配区域，即
|
(4) |
2) 安全区域.给定查询q，假设S1, S2, …, SN为所有满足空间约束的对象集合，且f(q, S1)＜f(q, S2)＜f(q, S3)＜, …, ＜f(q, SN).根据定义3，可以构建S1(当前最优解)的一个安全区域Re，即
|
(5) |
通过定理2可以得出Re=D (S1, S2)，即q点在支配区域D (S1, S2)中移动时，最优解S1保持不变.
定理2 Re=D (S1, S2).
证明 对于支配区域D(S1, Sn), n∈[3, N]，可以通过构建如下不等式组进行求解.在此，假设S1={px1, px2, …, pxk}，θ1, n=(f(q, Sn)－f(q, S1))/k.
|
由于f(q, S2)＜f(q, Sn)，所以θ1, 2 < θ1, n.根据式(3)可知E1, 2m⊆E1, nm, m∈[1, k].进一步根据式(4)可以得到D (S1, S2)⊆ D (S1, Sn).因此，Re=D (S1, S2).证毕.
下面给出Re的一个举例.图 1中存在6个空间二维对象o1, o2, …, o6.给定查询q=〈(0, 0), 3, 3〉，通过计算可得S1={o1, o3, o5}与S2={o1, o4, o5}，为满足空间多样化约束(σ=3)且具有最小距离和的top-2最优结果集，根据式(3)，计算得到如图 1所示的3个椭圆形区域E1, 21, E1, 22, E1, 23.从而3个椭圆的交集为安全区域Re(深色区域)
|
图 1 Re的一个举例 Fig.1 An example of Re |
3) 精确算法.通过使用安全区域Re，提出了一种精确算法(exact algorithm，EA)，如表 1所示.当查询到来时，首先求得当前位置的top-2查询解S1与S2，之后使用函数C(·)计算S1的一个安全区域Re，并返回S1；此后进行查询维护，当查询对象移动到新的位置q′时，检查q′是否位于Re中，如果成立，则最优解S1将保持不变，否则计算q′的top-2查询结果集以及新的安全区域Re.
|
表 1 精确算法 Table 1 Exact algorithm |
4) 复杂度分析.EA的主要代价在于使用函数T(·)计算top-2最优结果集，其时间复杂度为O(|P|k).若对象离开安全区域Re，T(·)需要被调用.本文用qe表示Re边界点，那么q与qe之间的最小距离为
|
因此，EA的时间复杂度为O(|P|k·fr).
3.2 近似算法为了进一步提高查询效率，提出了一种近似算法.该算法使用近似安全区域Rρ来减少重复计算频率.区别于Re，Rρ仅使用最优结果集top-1来构建.当查询对象在Rρ内移动时，先前最优结果为当前位置精确结果的ρ近似(ρ < 1，由用户设定).
1) 近似安全区域.假设q的最优结果集为S，当查询对象移动到q′时的最优结果集为Snew.那么对于∀ p∈P，根据三角不等式可得
|
由于S为q时的最优集，所以f(q, Snew)≥f(q, S)成立.因此，
|
若ρ·f(q′, S)≤f(q, S)-k·d (q, q′)成立，则ρ·f(q′, S)≤f(q′, Snew)成立，即S为Snew的ρ近似解.q′需满足：
|
(6) |
由不等式(6)构建的区域称为近似安全区域Rρ.
2) 近似算法.基于近似安全区域Rρ，提出了一种近似算法(ρ-approximate algorithm，ρAA)，如表 2所示.该算法可连续返回一个ρ近似解.
|
|
表 2 近似算法ρAA Table 2 Approximate algorithm ρAA |
3) 复杂度分析.在ρAA中，同样使用函数T(·)计算当前最优结果.当q移动到q′时，若
实验数据集取自文献[15]中所使用的真实数据集, 包含New York 50 334个Foursquare签到地点.本节对所提出的算法EA, ρAA以及一个基于采样的算法BASE在查询效率上进行对比.BASE算法在查询对象移动的每个时间戳都重新计算查询结果.每组实验随机生成20条轨迹, 每条轨迹包含100个时间戳.实验结果显示了算法的平均CPU时间以及重新计算查询结果的次数.默认参数为k=3, 多样化距离约束σ=2 km, 近似率ρ=0.7, 距离间隔为100 m(代表连续两个时间戳之间查询对象的移动距离).
所有算法均由C++编程实现.实验在PC机上执行, 处理器为3.40 GHz Intel Core i7-6700 CPU, 内存16 GB, 64位Windows操作系统.
图 2显示了当参数k变化时, 三种算法的运行时间以及重复计算次数的变化.由于三种算法均包含静态SDC-kNN查询计算, 随着k的增加计算代价显著增加.由于BASE算法在每个时间戳都需要计算查询结果, 所以计算次数始终为100.EA与ρAA使用了安全区域技术减少了重复计算次数, 运行时间明显好于BASE.由于ρAA使用参数ρ得到了面积较大的安全区域Rρ, 从而具有最佳性能.
|
图 2 查询结果数量k对三种算法性能的影响 Fig.2 Effects of k on the performances of the three algorithms (a)—执行时间；(b)—重复计算次数. |
图 3显示了距离阈值σ对三种算法效率的影响.可以看出, 随着σ的增加算法执行时间均有所下降.原因在于σ的增加, 满足距离阈值约束的对象集数量下降, 从而提升了SDC-kNN查询的计算效率.
|
图 3 距离阈值σ对三种算法性能的影响 Fig.3 Effects of σ on the performances of the three algorithms (a)—执行时间；(b)—重复计算次数. |
图 4显示了不同近似率ρ对ρAA的影响.从图 4a, 图 4b中发现, 随着ρ的增加, ρAA的运行时间以及重复计算次数都相应增加.原因在于ρ的增加, 导致安全区域Rρ面积缩小.尤其当ρ=1时, ρAA产生精确结果, 但其代价高于EA.从图 4c中可知, 在ρ变化的所有情况下, ρAA返回结果的精度(即, S为算法返回的结果, S*为精确结果)均大于ρ, 从而证明了ρAA的有效性.
|
图 4 近似率ρ对三种算法性能的影响 Fig.4 Effects of ρ on the performances of the three algorithms (a)—执行时间；(b)—重复计算次数；(c)—返回结果的精度. |
最后, 比较了本文提出的算法与文献[5]中PCPM算法的性能.正如在相关工作中所描述的, 文献[5]与本文查询目标类似, 但其采用双目标评价函数(相关性与多样性之和)来评价对象集, 相关性为查询对象与结果对象的距离, 多样性为结果对象间的相互距离.PCPM可以连续返回精确的查询结果.从图 5中可以看出, EA与ρAA在执行时间和返回对象间平均距离方面均优于PCPM算法.特别是结果对象间的平均距离, 均大于默认约束阈值2 km, 因结果对象间的平均距离越大, 空间多样化越好, 从而证明了本文提出的算法的有效性.
|
图 5 与PCPM算法对比 Fig.5 Comparison with PCPM algorithm (a)—执行时间；(b)—返回对象间平均距离. |
本文提出了空间多样化约束下的移动k近邻(SDC-MkNN)查询.该查询可以连续地返回k个距离查询对象近但相互之间距离较远的对象.基于安全区域技术思想, 提出了精确算法(EA)以及近似算法(ρAA), 通过减少重新计算查询结果的次数提高查询效率.通过实验证实了两种算法均能够有效地处理SDC-MkNN查询.相较于基本算法, EA以及ρAA(当ρ=0.7时)可以分别节省60%与80%以上的查询时间.
| [1] |
Nutanong S, Zhang R, Tanin E, et al. Analysis and evaluation of V*-diagram:an efficient algorithm for moving KNN queries[J]. The VLDB Journal, 2010, 19(3): 307-332. DOI:10.1007/s00778-009-0163-0 |
| [2] |
Li C W, Gu Y, Qi J Z, et al. Processing moving KNN queries using influential neighbor sets[J]. Proceedings of the VLDB Endowment, 2014, 8(2): 113-124. DOI:10.14778/2735471.2735473 |
| [3] |
Tang J Y, Sanderson M.Spatial diversity, do users appreciate it?[C]//Proceedings of the 6th Workshop on Geographic Information Retrieval.Zurich, 2010: 18-19.
|
| [4] |
Zhang C Y, Zhang Y, Zhang W J, et al.Diversified spatial keyword search on road networks[C]//Proceedings of the 17th International Conference on Extending Database Technology.Athens, 2014: 367-378.
|
| [5] |
Gu Y, Liu G L, Qi J Z, et al. The moving k diversified nearest neighbor query[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(10): 2778-2792. DOI:10.1109/TKDE.2016.2593464 |
| [6] |
Jain A, Sarda P, Haritsa J R.Providing diversity in k-nearest neighbor query results[C]//Proceedings of the 8th Advances in Knowledge Discovery and Data Mining.Sydney, 2004: 404-413.
|
| [7] |
Abbar S, Amer-Yahia S, Indyk P, et al.Diverse near neighbor problem[C]//Proceedings of the 29th Symposium on Computational Geometry.Rio de Janeiro, 2013: 207-214.
|
| [8] |
Lee K C, Lee W C, Leong H V. Nearest surrounder queries[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(10): 1444-1458. DOI:10.1109/TKDE.2009.172 |
| [9] |
Kucuktunc O, Ferhatosmanoglu H. λ-diverse nearest neighbors browsing for multidimensional data[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(3): 481-493. DOI:10.1109/TKDE.2011.251 |
| [10] |
Costa C F, Nascimento M A, Schubert M. Diverse nearest neighbors queries using linear skylines[J]. GeoInformatica, 2018, 22(4): 815-844. |
| [11] |
Liu H P, Jin C Q, Yang B, et al. Finding top-k shortest paths with diversity[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(3): 488-502. DOI:10.1109/TKDE.2017.2773492 |
| [12] |
Yiu M L, Dai X Y, Mamoulis N, et al.Top-k spatial preference queries[C]//Proceedings of the 23rd IEEE International Conference on Data Engineering.Istanbul, 2007: 1076-1085.
|
| [13] |
Li M, Chen L S, Cong G, et al.Efficient processing of location-aware group preference queries[C]//Proceedings of the 25th ACM International Conference on Information and Knowledge Management.Indianapolis, 2016: 559-568.
|
| [14] |
Zhang Z, Jin P Q, Tian Y, et al.Efficient processing of spatial group preference queries[C]//Proceedings of the 24th International Conference on Database Systems for Advanced Applications.Chiang Mai, 2019: 642-659.
|
| [15] |
Bao J, Zheng Y, Mokbel M F.Location-based and preference-aware recommendation using sparse geo-social networking data[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems.Redondo Beach, 2012: 199-208.
|