logo标签列表

如何利用最近邻搜索算法进行固定半径搜索？

algorithmnearest-neighborrange-query
6

最近邻搜索问题有很多解决方法，所以我想知道如果我想要进行固定半径范围搜索，是否可以利用那些最近邻搜索算法？

也许我可以一遍又一遍地进行kth-nearest-neighbor搜索，直到找到一个超出半径范围的点，但我认为这可能会造成很多浪费。

3个答案，阿拉亚长时间沉默！ - gsamaras
@G.Samaras，实际上我认为你的回答不错，正在阅读一些关于LSH的论文（并思考是否将其用于仅有3D问题）... - Alaya
@G.Samaras，抱歉没有回复您的消息... - Alaya
4个回答
4
不仅是“最近邻搜索问题有很多工作需要做”，而且你的问题还有许多需要回答的问题。最重要的是维度数量。
如果您不确定为什么维度很重要，请确保查看我的答案。

高维空间

假设你的点位于高维空间中，你应该选择局部敏感哈希(LSH)。这个算法的一个好的实现是E²LSH。他们还提供幻灯片，如果你想自己实现或更好地理解发生了什么。请注意，E²LSH解决了随机版本的R近邻问题，他们称之为(R, 1-δ)-近邻问题，其中δ与近似有关，正如他们在手册中提到的那样。

你也可以查看我关于LSH的回答这里。我在C++中使用它，并强烈推荐它用于您想执行的固定半径搜索！

低维空间

使用CGAL的空间搜索。我在C++中已经多次使用它来处理这种情况。同样，如果您想自己实现，可以在他们精美的文档中找到大量信息，并进行相关的谷歌查询。

顺便说一句，你的回答很好，我给你加了个赞。:)

2
采用空间哈希的方法：
假设问题空间被一个大小为 s 的网格分成超立方体，其中 s = r / sqrt(d)。
有趣的是，s = r / sqrt(d) 保证了在一个这样大小的超立方体内的任意两点之间的距离都小于或等于 r。
可以对网格分区进行编号，以便可以通过由其中一个角的索引形成的元组来识别每个超立方体。这些索引元组可以用作哈希结构（空间哈希）中的键。
现在，这是困难的部分，你必须注意到对于网格中的任何超立方体 A，存在一组邻居超立方体 N = (N1、N2、...)，它们与给定超立方体的最小距离小于或等于给定半径，从几何上看，它们看起来像一个超球体。可以将集合 N 的元素表示为相对于 A 的网格索引的增量。请注意，这些索引增量仅取决于 d。
例如，在二维情况下，你有以下几何结构：
   NNN    index deltas:    (-1,  2) ( 0,  2) ( 1,  2)
  NNNNN           (-2,  1) (-1,  1) ( 0,  1) ( 1,  1) ( 2,  1)
  NNANN           (-2,  0) (-1,  0) ( 0,  0) ( 1,  0) ( 2,  0)
  NNNNN           (-2, -1) (-1, -1) ( 0, -1) ( 1, -1) ( 2, -1)
   NNN                     (-1, -2) ( 0, -2) ( 1, -2)

因此，您已经拥有了实现高维球内部有效搜索所需的所有内容：

  1. 使用包含它们的超立方体的索引元组作为键将输入点推入空间哈希中。

  2. 给定一个点 p，搜索的方法是确定它所在的超立方体 A，然后使用索引增量集获取可能包含比 r 更近的点的邻居超立方体 N 集合。

  3. 从空间哈希中检索属于超立方体 N 的点，并检查哪些点足够靠近 p。

还有一些额外的优化可以执行，例如不检查属于 A 的点，因为它们保证都足够接近。可以根据 p 相对于 A 的位置执行 N 的预过滤。

请注意，选择 s = r / sqrt(d) 可以在具有小超立方体和不太大的集合 N 之间提供很好的折衷。

使用 k-d 树或四叉/八叉/...树：

每次在树上向下移动一级时，都要检查它所代表的空间是否与查询超球体相交。如果是，则继续向下搜索，否则将其完全从搜索中丢弃。

似乎使用网格是最快的方法，但我怀疑当搜索半径相对较小或维度很高时，它可能需要大量的内存使用。 - Alaya
最坏情况下的内存使用发生在每个点都位于不同的超立方体中，这样你就会得到一个空间哈希表，其中条目数与点数相同。因此，没有大量的内存使用。另一方面，集合N的大小随着维度的增加呈指数级增长，导致计算成本为O(f(M)*exp(d))，其中M是点数，f是某个未确定的函数。 - salva
1
网格大小不应该设置为r/sqrt(d)而是应该设置为r吗？因为使用r，您只需要在8个相邻的超立方体中搜索加上查询超立方体，总共只有9个超立方体，而使用r/sqrt(d)，您需要在8个相邻的超立方体中搜索加上与它们相邻的其他12个超立方体，总共有20个超立方体。 r/sqrt(d)的唯一优点是不必在查询超立方体内搜索，但其缺点远远超过它（20个超立方体对9个超立方体）。 - Géry Ogam
1
@Maggyero：你需要考虑的实际上是由超立方体集合覆盖的超体积。在二维情况下：20 * (r / sqrt(2))**2 = 10 * r**2 对比 9 * r**2，所以情况并不那么糟糕。对于更大的维度，r/sqrt(d) 的情况会更好一些。 - salva
2
在这种情况下，请参考那篇文章，其中对可能的算法进行了广泛的分析。 - Neithrik
如果您只有一个查询，那么您至少需要查看所有点来了解它们的值。 - Neithrik
那是蛮力破解，你可以做得比那更好。Riko下次回复评论时，你可能想要标记另一个人，这样他就会收到通知。使用@otherguy。 - gsamaras
@G.Samaras 不，对于一个查询，你不能做得比那更好，因为你需要遍历所有点一次，才能获取它们的变量。 - Neithrik
这就是为什么构建索引会有帮助。请看我的回答。 - gsamaras
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接