只使用点云作为查询点的D维k最近邻搜索的C++数据结构

Question

在具有周期边界条件的D维空间中有N个点云，其中N可以在500 ~ 10^8之间，D可以在1~ 20之间。点的分布变化很大，从完全均匀到非常集中。对于点云中的每一点，我都需要找到离这一点最近的k个邻域。我还需要找出在每个点的距离内存在多少个点，特别是最大范数距离。我不需要知道哪些点在半径内，只是多少点，但这是一个很好的补充。

我试过kd-树，但它们不处理包装边界，对于较大的树，复制是不可行的。此外，在更高的维度上，它会变慢。

我刚刚遇到了Vantage树，并尝试了一些代码，但它比kd树慢。虽然我找到的代码使用了递归搜索方法，但没有批处理。一方面，它可以本机处理包装条件，因此不需要重复。

我想看看我是否可以通过转换到迭代方法来从VP树中挤出更多的性能，看看我是否可以批量搜索，但是我有一个想法。所有这些数据结构都用于查找与任意查询点最近的邻居，而我的查询点仅限于点云中的点。我认为这个限制可能会允许更多的性能结构(可能是导航网之类的？)我试图寻找能够解决这一问题的结构，但我的google-fu却让我失望了。因此，想知道是否有人知道可以处理以下内容的数据结构：

• 处理少量和大量的点，即500-10^8点
• 最多处理20个维度
• 具有周期性边界的工作(即平面环面)
• 最大工作距离(软要求)。欧几里德可以给我一个潜在的列表，我可以手动挑选，但最好是最大范数)
• 可以找到k-NN来查询点，也可以找到与查询点之间的距离存在多少个点。
• 查询点只是结构中的点，而不是任意点。
• 查询可以批处理。也就是说，我需要为点云中的每一点找到k- NN。我还需要找出每一点在di内有多少个点，也就是说，每个点有一个不同的搜索半径。
• 不需要支持插入或删除。

谢谢

Answer 1

我怀疑对于你非常复杂的问题是否有一个完整和明确的答案，所以我只是分享我的想法。您的问题规范结合了许多不能很好地工作的事物(高维、非欧几里德度量、完全不同类型的查询)。如果一个算法必须假设泛型情况，它必然是缓慢的。

让我们首先对已知良好数据结构的特殊情况进行分类。

• 如果维度为1，则使用排序映射。
• 如果您的维度是2-3 (甚至是4)，那么排序查找和地理数据库应该是最佳的。https://en.wikipedia.org/wiki/R-tree
• 如果你的点有一个较高的维度，但相关性很强，维数约简可以将你的点云映射到一个有如此低维的云，并将问题简化为一个简单的问题。减缩
• 如果你的点数低于10^6，蛮力是最便宜的。用度量计算所有点的距离，然后对k结果进行部分排序。这些简单的缓存相关计算比使用树结构更快。排序
• 如果您的k是有界的，例如k <= 20，并且为查询时间进行优化，则预先计算一个包含所有结果的表。
• 如果您的维度中只有少数是周期性的，我认为您应该调整kd-树算法来处理它们(对于类似于Vantage树的维度添加更复杂的比较节点)。

如果所有这些都不适用(如果你有一个实际的应用，请与我们分享)，你的情况是非常通用的。

除了您提到的算法之外，您还应该尝试几何近邻访问树(GNAT)。http://infolab.stanford.edu/~sergey/near.html应用于通用度量(包括您的度量)，并处理非统一的发行版。

而且，我认为你的期望很高。您可以比较一个好的kd树实现(例如，https://github.com/mariusmuja/flann)，它仅用欧几里德度量来解决这个问题。如果这需要很长时间，您不应该期望更多的通用度量来更快地解决问题。

不可否认，更通用的方法不能使用您的约束，即查询是云中的点。如果有这样的解决办法，我会非常感兴趣。

Answer 2

如果Java是一种选项(性能与当前的C++相似)，请查看埃尔基库。它提供了许多多维索引的实现，包括降维和空间填充曲线的方法。它还为kNN (euclidic/non)、集群检测、范围查询等提供了许多算法(通常可以用自定义距离度量来定义自己的查询筛选器)。对于kNN，我可以特别推荐CoverTree和(稍微慢一点，但更通用) PH树，我测试了最多27个维度。PH树特别适用于高度聚类和大型数据集(我测试了100,000,000点)。(免责声明:PH树基于我自己的研究，但我认为您的用例非常适合。)

然而，据我所知，这些方法都不允许像您所提议的那样进行特殊的优化。