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

Question

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

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

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

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

• 处理少量和大量的点，即500-10^8点
• 处理多达 20 个维度
• 使用周期性边界(即平坦环面)
• 使用 maxnorm 距离(软要求。Euclidean 可以给我一个我可以手动剔除的潜在列表，但最好使用 maxnorm)
• 可以找到k-NN到查询点以及找到有多少点存在与查询点的距离
• 查询点只是结构中的点，不是任意点
• 可以批处理查询。即我需要为点云中的每个点找到第 k 个 NN。我还需要找出每个点 i 在 d[i] 中存在多少个点。即每个点都有不同的搜索半径。
• 不需要支持插入或删除。

谢谢

Answer 1

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

我们先梳理一下已知好的数据结构的特例。

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

如果所有这些都不适用(如果您有实际应用，请与我们分享)，您的案例非常通用。

除了您提到的算法之外，您还应该尝试使用几何近邻访问树 (GNAT)。 http://infolab.stanford.edu/~sergey/near.html 它们适用于通用指标(包括您的指标)，还可以处理非均匀分布。

此外，我认为您的期望很高。您可以与仅使用欧几里得度量解决问题的良好 kd 树实现(例如 https://github.com/mariusmuja/flann)进行比较。如果这需要很长时间，您不应该期望更通用的指标可以更快地解决。

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