多维反向k近邻查询
Published:
近十年来,空间点数据的反向k最近邻(R$k$NN)查询引起了研究者的广泛关注。给定一个数据点 q,反向k最近邻(R$k$NN)查询查找每一条将q当作它的k个近邻之一的数据点。由于q与这些数据点很接近,所以q对这些点的影响很大。例如,居民有极大的可能会去最近的k个商店购物。因此,在市场调研中,可以通过检索所有将这家商店当作k 个最近邻之一的居民点,来评估一家新开的便利店q潜在的客户。R$k$NN还可在更多的商业选址场景中使用,具有很重要的现实意义和实用价值。在本文中,提供一种设施或服务的对象(如购物市场、加油站)称为设施,使用该设施的对象(如居民、司机)称为用户。在这个上下文中,给定一个查询设施q, 其R$k$NN返回所有将q作为k个最接近的设施之一的用户。本文将基于这种上下文介绍四种R$k$NN算法, 即six regions 、TPL、FINCH、InfZone。
[本文总阅读量: 次]
简介
近十年来,空间点数据的反向k最近邻(R$k$NN)查询引起了研究者的广泛关注。给定一个数据点 q,反向k最近邻(R$k$NN)查询查找每一条将q当作它的k个近邻之一的数据点。由于q与这些数据点很接近,所以q对这些点的影响很大。例如,居民有极大的可能会去最近的k个商店购物。因此,在市场调研中,可以通过检索所有将这家商店当作k 个最近邻之一的居民点,来评估一家新开的便利店q潜在的客户。R$k$NN还可在更多的商业选址场景中使用,具有很重要的现实意义和实用价值。在本文中,提供一种设施或服务的对象(如购物市场、加油站)称为设施,使用该设施的对象(如居民、司机)称为用户。在这个上下文中,给定一个查询设施q, 其R$k$NN返回所有将q作为k个最接近的设施之一的用户。本文将基于这种上下文介绍四种R$k$NN算法, 即six regions 、TPL、FINCH、InfZone。
注:本文大多数算法描述参考于[7],更多R$k$NN算法和细节请参考原文。
基本定义和步骤
R$k$NN查询分为双色R$k$NN查询和单色R$k$NN查询。
双色R$k$NN查询:存在一个设施集F、一个用户集U。给定一个查询设施q(不一定在F中),一个双色R$k$NN查询返回每个用户$u\in U$,对于这些用户$u, q$是{$q\cup F$}中离它最近的k个设施之一。
单色R$k$NN查询:给定一组设施F和一个查询设施q(不一定在F中),一个单色R$k$NN查询返回每个设施$f\in F$,其中q是{$q\cup F−f$}中离它k个最近的设施之一。
在本文中,我们关注的是在欧氏空间中回答R$k$NN查询。由于R$k$NN查询的大部分应用是基于位置的服务,几乎所有现有的技术(如six regions [3]、TPL[4,5]、FINCH[6]、InfZone[1]等)都集中在二维位置数据上。因此,我们重点介绍在二维数据集上的算法。此外,双色R$k$NN查询在实际场景中有更多的应用程序。因此,本文主要焦点是双色查询。所有这些算法都假设数据集被R-tree或其变体(如R*-tree)进行索引。因此,接下来的介绍中,我们还假设设施和用户数据集都由两个R*树进行索引。
假设$dist(a, b)$表示两个对象的欧式距离。对于一个用户p, 如果存在至少k个设施F’, 对于任意f $\in $ F’, p到f的距离比q小,即$dist(p, f) < dist(p, q)$,则用户p不可能是q的R$k$NN之一,因为q不可能是p的kNN。
由于数据集的数量可能十分庞大,通过遍历所有用户并判断其是否满足条件,这是十分耗时且不合理的操作。前文提到,数据集会被R*-tree索引,每个R*-tree节点包含了大量的数据。因此,可通过先剪枝不合适的R*-tree实体(一个节点或一条数据),来减少查询开销。如果一个用户R*-tree实体$e$与至少k个设施(不包含q)的距离小于$q$,那么$e$可以被剪枝,因为e中包含的所有数据都具有至少k个比q近的设施。因此它们不可能是q的RkNN。
每个算法都可以分成两个步骤:
Filtering: 过滤阶段,每个算法使用一组设施来过滤不包含R$k$NN的搜索空间。由于使用所有数据的可能非常昂贵,算法首先会挑选一些设施来过滤搜索空间。这些设施称为过滤设施,包含这些设施的集合称为过滤集(表示为$S_{fil}$)。
**Verification: **验证阶段,检索不能使用$S_{fil}$过滤的用户,它们是可能的R$k$NN,称为候选用户。然后通过确认它是否是R$k$NN来验证每个候选用户。
算法
(1) Six-regions
Filtering: Stanoi等人[3]提出了一种基于Six-regions(6个区域)的方法,将以查询q为中心的整个空间划分为6个相等的区域,每个区域60$^{\circ}$,(下图中的P1到P6)。每个区域中,q的第k个最接近的设施定义了可以过滤的区域。换句话说,假设$d_i^k$是区域$P_i$中q与其第k个最近的设施之间的距离。那么任何在$P_i$中并且距离q大于$d_i^k$的用户u都不能是q的R$k$NN。
上图中展示了一个RkNN (k = 2)查询,设施包含q和四个编号从a到d的设施。在区域$P_2$中,d是距离q第二近的设施,则阴影区域可以被过滤,即$P_2$区域中只有位于白色区域的用户可以是R$k$NN。处于阴影区域的用户u不能是R$k$NN,因为它肯定更接近b和d,则所有u的kNN(k=2)不可能包含$q$。可以用三角形证明处于阴影部分的用户必然远离$q$。例如,对于设施d和用户u,可形成△qdu(如图(a))。因为$\angle dqu \le 60^{\circ}$ , 并且 $\angle qdu \ge 60^{\circ}$, 则 $dist(u,d) \le dist(u,q)$(大角对大边)。
Verification: 如前所述,位于分区$P_i$中的用户u,如果$dist(u,q) > d_i^k$,则$u$不能是$q$的R$k$NN 。在验证阶段,通过访问用户R*-tree来检索候选用户,并过滤mindist(e, q) >$d_i^k$的节点, 并通过Filtering步骤过滤$dist(u,q) > d_i^k$的用户,得到候选用户。然后每个候选用户通过一个布尔范围query来验证是否是q的R$k$NN。布尔查询以u为中心,半径为$dist(u, q)$作圆。当且仅当在以u为中心的圆中只有小于k个设施时,返回true,$u$是$q$的R$k$NN。如图(b)所示,以$u$为圆心,半径为$dist(u,q)$的圆,只包含两个设施。因此$u$为$q$的R$k$NN(k=2)。
(2) TPL
Filtering: Tao等人[4,5]提出的TPL可以说是R$k$NN查询中最流行的算法。他们首次将半空间剪枝的概念用于R$k$NN查询,并激发了许多后续工作。给定一个设施f和一个查询q, f和q之间的一条垂直平分线$B_{f:q}$ 将空间分成两半。设$H_{f:q}$表示包含f的半空间,$H_{q:f}$表示包含q的半空间,位于$H_{f:q}$中的每个点p,都满足$dist(p, f) < dist(p, q)$,也就是说,f可以裁剪位于$H_{f:q}$中的每个点p。
考虑下图(a)的例子,其中包含了一个查询q和四个设施(a到d)。因为p位于$H_{a:q}$中,因此,$dist(p, a) < dist(p, q)$,所以点p可以被设施a裁剪。请注意,被至少k个半空间裁剪的点p才不能是q的R$k$NN,才可以被过滤。如下图,假设k = 2,点p可以被过滤,因为它会被$H_{a:q}$和$H_{c:q}$裁剪。
TPL的过滤算法从根节点开始访问设施R*-tree的节点,并将它们按与q的最小距离升序排列放入堆中。迭代地访问堆,如果一个被访问的实体e(可以是一个节点或者一个设施)可以被过滤(例如,e被至少k个设施裁剪),它将被忽略。否则,如果e是中间节点或叶节点,则将其子节点插入堆中。另一方面,如果e是一个设施,且无法裁剪,则将其插入过滤集$S_{fil}$中,其半空间用于过滤搜索空间。当堆为空时,过滤算法终止。在图(a)中,假设过滤算法以$b、c、a、d$的顺序迭代访问设施,当访问设施$b、c、a$时(即$S_{fil}= {b, c, a}$),过滤区域由半空间$H_{b:q}, H_{c:q}, H_{a:q}$的交集组成。如果k = 2,则阴影区域可以被过滤,因为其中的每个点都位于至少两个半空间中。如,当访问设施d时,可以使用筛选集对它进行剪枝。因此,在$S_{fil}$中不用插入d。
上面提到,TPL中的一个重要操作是确定设施实体是否可以使用一组过滤设施$S_{fil}$进行过滤。一种穷举的过滤策略如下:
设$S_{fil}$为包含m≥k个设施的过滤集,${f_1,…,f_k)}$为$S_{fil}$任意一个包含$k$个设施的子集。它们形成的过滤空间为 $\cap_{i=1}^{k} H_{f_i:q}$,每一个出现在这个空间中的点将被过滤。穷举过滤策略枚举每个这样的子集,并检查是否可以使用这些子集过滤R*-tree的节点。但是,这样的子集数量($C_m^{k}$)可能会很大。因此,TPL在过滤能力上做出了妥协,使用了以下成本较低的过滤策略(以下称为宽松过滤策略)。
首先,TPL根据希尔伯特值(Hilbert)对$S_{fil}$中设施按其空间位置进行排序。设排序后的顺序为$S_{fil} ={f_1,…,f_m)}$。然后,宽松过滤策略将其分成$m$个子集,分别为:${f_1,…,f_k)}$,${f_2,…,f{k+1})}$,…,${f_m,…,f{k-1})}$。总过滤成本为$O(km)$,因为要考虑m个子集,每个子集包含k个设施。如图(a), 假设$S_{fil} ={a,b,c}$。宽松过滤策略生成三个子集 ${a,b}$ 、${b,c}$和${c,a}$,并可过滤与穷举滤波相同的区域(即阴影区域)。这是因为在这种情况下,最大可能子集的个数等于m,即$C_{3}^{2} =3=m$。但是,在$S_{fil}$中添加一个新设施可能会减少过滤的面积,并且在添加该设施之前可以过滤的点可能不会再被过滤。假设设施e被插入,排序后的$S_{fil}$为${a, b, c, e}$。宽松过滤算法使用${a, b}, {b, c}, {c, e}和{e, a}$对搜索空间进行过滤。上图(b)展示了可以使用这些子集过滤的阴影区域。注意,经过过滤的区域已经变小,导致点p不能再被过滤。
为了更好地过滤节点e(节点或数据点),TPL使用一种名为kTrim的算法。对于包含k个连续设施的$S_{fil}$的子集,该算法裁剪掉节点中可以被这个子集过滤的部分。kTrim使用每个子集(共m个)迭代地修剪节点。在任何阶段,如果整个节点被裁剪,节点或数据点就可以被过滤,算法就会停止。
Verification: TPL迭代地访问用户R*-tree的节点,并使用$S_{fil}$对它们进行过滤。无法筛选的用户被插入到候选集中。与六个区域不同,TPL不会使用布尔范围查询来验证候选区域。取而代之地,TPL使用了一种更聪明的策略,它要求R*-tree的每个节点最多访问一次。具体地说,在过滤阶段遇到的设施R*-tree的节点和数据点保持在集合P中,验证算法轮询运行。在每一轮中,P中的一个节点被取出,并将其子节点被插入到P中。选择被取出的节点是基于它可以验证多少个候选节点。在每一轮中,利用P中的节点和数据点来识别可以用P验证的候选项,即可以确认为R$k$NN或保证不为R$k$NN。这样的候选项将被验证并从候选者集中删除。当候选集为空时,算法停止。
(3) FINCH
Filtering: Wu等人提出了一种名为FINCH的算法[6],旨在通过使用一种更方便的过滤策略来改进TPL。具体来说,它不使用子集来过滤节点,而是使用一个包围不能被过滤区域的凸多边形。多边形之外的任何条目都可以被过滤。考虑图(a)的例子,其中白色区域是非过滤的区域。FINCH用一个凸多边形来近似这个区域(参见下图中的白色区域,边界用虚线表示)。任何在这个多边形之外的节点都可以被过滤,也就是阴影部分。
凸多边形的计算成本较高,并且,每当一个新的设施添加到$S_{fil}$,它需要$O(m^2)$的时间开销来计算凸多边形,其中$m$是过滤集$S_{fil}$中设施的数量。然而,FINCH的过滤比TPL更有效,因为判断一个点是否包含在凸多边形里,可以在对数$O(log ~m)$时间内完成。因此,可以在$O(log ~m)$内过滤一个点。过滤一个节点需要$O(m)$,因为它可能需要计算矩形与凸多边形的交点。
Verification: 识别凸多边形内的用户并将其插入到候选集中。与6区域方法类似,每个候选用户都需要使用布尔范围查询进行验证。
(4) InfZone
Filtering: Cheema等人[1,2]提出InfZone算法,利用影响区域的概念来改善验证阶段。影响区域是指当且仅当p位于该区域内时,点p为q的R$k$NN的区域。一旦计算了影响区域,就可以通过定位位于影响区域内的用户来回答R$k$NN查询。一种方法建立影响区的方法是绘制所有设施的半空间,被小于k个设施过滤的区域对应于影响区。例如,在下图中,q和所有设施之间的半空间被绘制为$Ha:q, Hb:q, Hc:q,和Hd:q$, 则阴影区域是过滤区域,白色区域是影响区域。回想一下,FINCH和TPL没有考虑$Hd:q$,因为当访问d时,会发现它位于过滤区域,因此会被忽略。作者提出了几个性质,以减少必须考虑的设施的数量,以正确计算合适的影响区域。该算法首先初始化影响区域为整个数据空间(矩形)。每当访问设施f时,其半空间$Hf:q$用于更新影响区,例如,通过删除至少k个设施修剪的部分。对于当前影响区域的每个顶点v,如果$minDist(e,v) > dist(v,q)$, 则不需要这个实体e(一个节点或一个设施)计算影响区域。因此,该算法只考虑不满足该条件的实体。请注意,检查是否需要设施实体需要$O(m)$,因为遍历影响区域的顶点数为$O(m)$。当在$S_{fil}$中插入新设施时,更新影响区域需要$O(m^2)$,其中m是$S_{fil}$中的设施总数。在它的扩展版[2]中,该成本优化到了$O(km)$。
Verification: 根据影响区域的定义,当且仅当p在影响区域内时,点p为R$k$NN。因此,算法将迭代访问用户R*-tree的实体,并忽略不与影响区域重叠的实体。位于影响区域内的用户则为R$k$NN。结果表明,影响区域为星形多边形,点包含在星形多边形边数可以在对数时间内完成,即验证用户的成本为$O(log~ m)$。为了过滤一个用户节点(即一个矩形),需要判断矩形是否与影响区相交,它花费$O(m)$。为了加快检查某个实体(节点或点)是否与影响区域重叠,InfZone被近似为两个圆:一个完全包含影响区域,另一个完全包含它(所有影响区域)。首先对照这些圆检查每个实体的重叠部分,以确定是否与影响区重叠。
复杂度分析:
过滤方法 | six-regions | TPL | FINCH | InfZone |
---|---|---|---|---|
筛选设施节点 | O(1) | O(km) | O(m) | O(m) |
筛选设施数据点 | O(1) | O(km) | O(log m) | O(m) |
在$S_{fil}$中增加一个新设施 | O(log k) | O(log m) | O($m^2$) | O($m^2$) |
验证方法 | six-regions | TPL | FINCH | InfZone | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
过滤用户节点 | O(1) | O(km) | O(m) | O(m) | ||||||||||||
过滤用户点 | O(1) | O(km) | O(log m) | O(log m) | ||||||||||||
验证一个候选用户 | 布尔范围查询 | 范围查询 | 布尔范围查询 | O(log m) | ||||||||||||
预期候选人人数 | $\frac{6k | U | }{F}$ | $\frac{k | U | }{F}$ 至 $\frac{6k | U | }{F}$ | $\frac{k | U | }{F}$ 至 $\frac{6k | U | }{F}$ | $\frac{k | U | }{F}$ |
参考文献:
[1] M. A. Cheema, X. Lin, W. Zhang, and Y. Zhang. Influence zone: Efficiently processing reverse k nearest neighbors queries. In ICDE, pages 577–588, 2011.
[2] M. A. Cheema, W. Zhang, X. Lin, and Y. Zhang. Efficiently processing snapshot and continuous reverse k nearest neighbors queries. VLDB J., 21(5):703–728, 2012.
[3] I. Stanoi, D. Agrawal, and A. E. Abbadi. Reverse nearest neighbor queries for dynamic databases. In ACM SIGMOD Workshop, pages 44–53, 2000.
[4] Y. Tao, D. Papadias, and X. Lian. Reverse knn search in arbitrary dimensionality. PVLDB, pages 744–755, 2004.
[5] Y. Tao, D. Papadias, X. Lian, and X. Xiao. Multidimensional reverse k nn search. VLDB J., 16(3):293–316, 2007.
[6] W. Wu, F. Yang, C. Y. Chan, and K.-L. Tan. Finch: Evaluating reverse k-nearest-neighbor queries on location data. PVLDB, 1(1):1056–1067, 2008.
[7] Yang, S., Cheema, M. A., Lin, X., & Wang, W. (2015). Reverse k nearest neighbors query processing: experiments and analysis. PVLDB, 8(5), 605-616.