寻找双色反向最近邻的两和三维空间的最优区域外文翻译资料

英语原文共 34 页，剩余内容已隐藏，支付完成后下载完整资料

Geoinformatica (2016) 20:351–384

DOI 10.1007/s10707-015-0239-5

—————————————————————————————————————————————

寻找双色反向最近邻的两和三维空间的最优区域

Received: 17 April 2015 / Revised: 27 September 2015 Accepted: 5 October 2015 / Published online: 19 October 2015 # Springer Science Business Media New York 2015

摘要 MaxBRNN问题是找到一个最优的地区，例如在这一地区建立一个新的服务，此服务可能吸引客户接近的最大数量。MaxBRNN问题有很多实际应用的例如位置服务规划和急救计划。在典型的实际应用中，MaxBRNN问题的数据量是巨大的，因此高效的解决方案是非常急需的。在本文中，我们提出了两种有效的算法，即OptRegion，和3D-OptRegion，他们用来解决MaxBRNN问题或者二维或三维MaxBRNN问题，尤其是3D-OptRegion，我们提出了一个强大的剪枝策略：Fine-grained Pruning Strategy（细粒度的剪枝）策略来减小搜索空间。我们的方法使用三种优化技术，即扫描线（在三维空间中的扫描平面），基于限估计的剪枝策略，以及影响值计算（候选点），以提高搜索性能。在三维空间中，我们进一步使用细粒度剪枝策略进一步改善剪枝效果。广泛的实验评估使用真实和合成数据集来证实， OptRegion and 3D-OptRegion在所有问题的情况下都优于现有的算法。

关键词：空间数据库；反向最近邻查询；三维空间

—————————————————————————————————————————————

Fangshu Chen youyou_chen@foxmail.com

Huaizhong Lin linhz@zju.edu.cn

Yunjun Gao gaoyj@zju.edu.cn

Dongming Lu ldm@zju.edu.cn

College of Computer Science and Technology, Zhejiang University, Hangzhou, Peoplersquo;s Republic of China

1 简介

给定一个数据库，一个RNN(Reverse Nearest Neighbor) 查询返回的数据点，此数据点事一个给定的查询点的最近邻（RNN查询首次被引进[ 15 ]）。一个BRNN（双色反向最近邻）是RNN的双色版，其中所有的数据点构成了服务点集P和客户点集O。对于一个服务点pisin;P，一个BRNN查询在可以发现所有点oisin; O的在P中的近邻点p。这些O里的客户点o构成影响集P和P的影响值，这等于影响集的基数。例如，在图1a，对于一个服务点p2，其BRNN，即影响集，是{ o2、o3 }。

MaxBRNN问题[ 4, 5 ]的目的是寻找所有点都具有最大影响值的区域S，即所有在S中的p点的BRNN集的基数都是空间最大值。MaxBRNN可以被视为一个最优区域搜索的问题并吸引了大量研究工作的投入。

MaxBRNN问题有许多有趣的实际生活中的应用，如位置服务规划和急救计划。例如，在图1a中，有五个客户点o1到o5以及一个城市的四所商店p1到p4。现在，一家公司想建立一个新的商店，目标是找到一个能吸引尽可能多的顾客的地点，前提是顾客由于距离原因对于去便利商店更有兴趣。我们以每一个客户点oi（1le;ile;5）来画一个圆圈，圆心为oi，它和离它最近的商店之间的距离为半径。MaxBRNN问题转化为寻找与圆圈重叠部分面积最大的区域去设置一个新的商店，这其实就是三个圆圈o2、o3和o5的交叉点。

这里有几个在文献中被提出的可解决MaxBRNN的算法[ 5, 17, 26，29 ]。然而，当数据集变得非常大时，所有这些算法都会显得低端，因此我们急需高效的解决方案。

MaxBRNN问题假设每个客户只能访问离他最近的服务。然而，在现实中，客户可以选择访问其最邻近的服务。面对这种情况，MaxBRNN可概括为MaxBRkNN问题，即找到一个最佳的区域，在这区域设立一个服务来保证可以让他们寻找到最邻近服务点客户数量最大化。

在本文中，我们提出了两种称为OptRegion和3D-OptRegion的高效算法来解决二维和三维空间中的MaxBRNN和MaxBRkNN问题。我们的方法采用三种优化技术，即扫描线（三维空间中的扫描平面），修剪策略（基于上限估计）和影响值计算（候选点），以提高搜索性能。

我们的主要贡献（不包括会议版本[16]中的贡献）可以总结如下：

1.我们扩展OptRegion算法来解决Eu​​clidean空间中的MaxBRkNN问题。

2.我们提出了一种高效的算法，即3D-OptRegion来解决三维空间中的Max-3D-BRNN问题，该算法可应用于任意的Lp范数空间。该算法采用扫描（平面）技术快速找到重叠球体。

3.我们在三维空间中提出了一种有效的细粒度修剪策略，通过这种策略可以在不进行评估的情况下修剪大多数候选点。

4.给出OptRegion算法和3D-OptRegion算法的正确性分析，并分析OptRegion中使用的上界估计技术的准确性。

5.我们对真实和合成数据集进行了广泛的实验，以证明我们提出的算法的性能。

本文是其初步会议版本[16]的重大延伸。相比初步版本，我们将查询扩展到三维空间和BRkNN查询（kge;1），提出了一种有效的三维空间修剪策略，并对我们上限估计的准确性进行了理论分析和实验验证约束估计。

MaxBRkNN问题在实际应用中是必需的，例如，当规划一个新的便利店时，考虑到顾客不仅可以被吸引到最近的商店，还可以被吸引到第二近的和最邻近的商店，那么MaxBRkNN查询变得非常必要。

Max-3D-BRNN问题也有很多现实生活中的应用，我们在这里给出三个典型的例子：1）在一些应急应用中，比如在中国的地震中，我们经常需要快速响应MaxBRNN搜索，以快速将供应/救援或救援工作的服务中心，客户点oisin;O的位置可能会动态变化，因此我们必须将时间视为另一个维度，因为在不同时刻位置不同。 2）另一个例子是传感器网络分布。假设我们计划为传感器添加一个新的群集节点以相互通信，并且传感器位于山中的不同位置和高度，自然这些位置必须在三维空间中进行描述。 3）在位置规划示例中，顾客不仅考虑与商店的距离，还考虑在那里驾车的时间，并且我们还可以将顾客偏好视为其他维度。因此，将MaxBRNN问题扩展到三维空间甚至更高的空间是非常重要的。在本文中，我们提出了一种有效的三维空间MaxbrNN修剪策略，并且它很容易扩展到高维空间（我们在高维空间中留下MaxBRNN问题作为我们以后工作的一项任务）。

本文的其余部分安排如下。第2节给出相关工作的调查。第3节提出MaxBRNN，MaxBRkNN和Max-3D-BRNN问题。第四节和第5节分别描述了二维和三维空间中MaxBRNN的算法。 第6节分析了算法的时间复杂性和正确性。 第7部分通过对真实和合成数据集进行广泛的实验来评估所提出的算法和修剪策略，最后我们在第8节中总结了该论文。

2 相关工作

有两种类型的RNN查询，即单色和双色RNN [16]。在单色情况下，所有点都属于同一类别。在双色情况下，点分为两类，例如服务和客户。文献[21-23]研究了原始RNN问题，提出的算法主要基于一些空间分割和修剪策略。近年来，双色RNN（BRNN）问题已经在路网中的自组织网络和连续环境中得到了广泛的研究[3,6,10,12,14,18,20,25]。在[28]中，他们也将BRNN问题推广到地表情景中。

Cabello[4，5]等人首先提出MaxBRNN问题，该问题最大限度地提高了新服务的潜在客户数量，他们称之为MAXCOV问题，并提出二维欧几里德空间的解。他们还研究了BRNN查询中的其他优化标准：最小化与相关客户的最大距离的MINMAX，以及MAXMIN，这最大化了与关联客户的最小距离。 MaxBRNN查询具有挑战性，因为存在可以构建新服务的候选位置的无限数量。 Wong等人[26]定义MaxBRNN将找到包含最优位置的最大一致区域，并提出一个称为MaxOverlap的算法来解决它。 算法MaxOverlap[26]利用了一种称为区域到点变换的技术，该技术也被OptRegion算法采用。它将最佳区域搜索问题转换为最佳交点搜索问题，以避免搜索指数数量的区域。尽管如此，MaxOverlap不能很好地扩展，因为最佳交点的计算非常昂贵。

Wong等人[27]扩展了二维和三维空间中Lp范数的MaxOverlap算法[26]。他们还扩展MaxOverlap来解决MaxBRkNN问题，通过考虑k-最近邻居而不是仅仅一个最近邻居。这增加了要计算的交点的数量，因此当k很大时会导致更多的性能恶化。在[27]中，他们还将他们的算法与Buffer-Adapt算法[10]进行了比较，该算法最初设计用于解决L1范数（曼哈顿距离空间）中的问题MaxBRNN。在[17]中的算法MaxSegment试图通过检查二维和三维空间中圆的相交弧来加速找到最佳交点。在[17]中的实验结果表明MaxSegment算法在所有情况下都比MaxOverlap算法[27]更快。但是，由于它们不使用任何修剪策略，因此可能会有很多需要检查的交叉弧，这非常耗时。

Zhou等[29]将MaxBRNN问题推广到反映现实世界的场景，其中客户可能对不同的服务站点有不同的偏好，并提出了一种称为MaxFirst的有效算法来解决一般化的MaxBRkNN问题。 MaxFirst利用分支定界原理，递归地将空间划分为四元组，并计算象限BRNN大小的上限和下限。然后该算法仅在可能包含最佳区域的那些象限中检索。

实验结果表明，MaxFirstis比MaxOverlap更高效。但是，在某些情况下，可能还需要处理很多象限，并且可扩展性差。

Z. Chen等人[7]将MaxBRNN问题扩展到道路网络空间。 P.Ghaemi等[13]在空间网络中解决MaxBRNN问题而不是Lp-范数空间问题，他们提出了两种有效的EONL和BONL算法来解决这个问题。 F.Chen等[8]着重研究了欧几里得空间中容量约束情形下的MaxBRNN问题。 [18,25]将BRNN查询扩展到ad-hoc网络和移动系统，他们采用ad-hoc网络中的通信技术来解决BRNN查询。

[9,24]研究的最大范围（MaxRS）问题也旨在最大化区域的影响值。但是，这个问题与我们的MaxBRNN问题有很大的不同。首先，该区域的形状和大小在MaxRS问题中是固定的，但在MaxBRNN问题中，我们对结果区域（或区域）一无所知。

其次，在MaxRS问题中，已知覆盖区域的扩展，然而，在我们的问题中，我们必须通过计算RNN来计算区域的半径，这使得我们的问题变得更加复杂。

3 初步措施

在本节中，我们将本文研究的问题形式化，然后讨论用于解决问题的区域到点转换。

3.1问题定义

假设在空间D中有一组服务点P和一组客户点O，每个点oisin;O都有一个权重w（o），用来表示客户数量或重要性。

对于一个点oisin;O，kNN（o，P）表示P中最接近o的top-k点集合。对于D中的一个点（sisin;P或不），BRkNN（s，O，Pcup;{s}）代表O中的点的集合，它将s作为它们在Pcup;{s}中的最近邻居之一。为了简单起见，我们在以下讨论中取k = 1，这可以容易地扩展到情况kgt; 1。

定义1（影响集/值）给定一个点s，我们定义s的影响集为BRNN（s，O，Pcup;{s}）。 s的影响值等于Sigma;oisin;BRNN（s，O，Pcup;{s}）w（o）。

定义2（最近位置区域，NLR）给定一个顾客点o，o的最近位置区域R被定义为以o为中心的区域，并包含所有的点s，其中d（o，s）le;d（o， NN（O，P））。 NN（o，P）是P中o的最近邻，d（x，y）是点x和y之间的距离。 NLR的权重R w（R）等于o的权重。

在定义2中，当考虑Lp范数空间和三维空间时，我们采用符号NLR来捕获一般情况。在计算d（x，y）时可以采用Minkowski距离。当在二维空间中考虑欧氏距离，即L2范数空间时，NLR是以半径d（o，NN（o，P））为中心的围绕o的圆。

定义3（一致区域，[26]）如果满足以下条件，则区域R被认为是一致的：forall;s，sisin;R，s，snotin;P，s的影响值等于s。

根据[26]中的定义，给定一个一致的区域R，R的影响值表示为I（R），并定义为I（R）=Sigma;oisin;BRNN（s，O，Pcup;{s}）w （o），其中s表示R中的任意新服务器点。

根据定义3和上面的描述，我们可以给出最大一致区域的定义如下：给定一个一致的区域R，我们说R是最大一致区域，如果不存在另一个一致区域R0满足以下 条件：（1）Rsub;R0和（2）I（R）= I（R0），我们也称最大一致区域为最佳区域。

问题1（MaxBRNN）给定空间D中的服务点集合P和顾客点集合O，我们希望找到一个最大一致区域（最优区域）S，使得S中的所有点具有最大影响值。

例如，在图1a中，MaxBRNN（最优）区域S是三个NLR o2，o3和o5的交集，并且S的影响值是三个NLR权重的总和。非正式地说，MaxBRNN返回具有最大重叠NLR的区域。

当考虑顾客点的最近邻居时，顾客点

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[24622]，资料为PDF文档或Word文档，PDF文档可免费转换为Word