仅使用点云作为查询点的 D 维 k 最近邻搜索的 C++ 数据结构
C++ Data Structure for k Nearest Neighbour Search in D dimension using only point cloud as query points
我有一个 D 维 space 中 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] 中存在多少个点。即每个点都有不同的搜索半径。
- 不需要支持插入或删除。
谢谢
我怀疑你这个非常复杂的问题是否有一个完整而明确的答案，所以我只是分享我的想法。
您的问题规范结合了许多不能很好地协同工作的东西（高维、非欧几里德度量、完全不同类型的查询）。如果一个算法必须假设通用情况，它必然很慢。
先梳理一下已知好的数据结构的特例
- 如果您的维度是 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，并且您针对查询时间进行了优化，则预先计算 table 和所有结果。
- 如果你的维度中只有少数是周期性的，我认为你应该调整 kd-tree 算法来处理它们（为那些类似于 Vantage Point Trees 中的维度添加更复杂的比较节点）。
如果所有这些都不适用（如果您有实际应用，请与我们分享），您的案例非常通用。
除了您提到的算法之外，您还应该尝试使用几何近邻访问树 (GNAT)。
http://infolab.stanford.edu/~sergey/near.html
它们适用于通用指标（包括您的指标），还可以处理非均匀分布。
另外，我觉得你的期望很高。您可以与仅使用欧几里德度量解决问题的良好 kd 树实现（例如，https://github.com/mariusmuja/flann）进行比较。如果这需要很长时间，您不应该期望更通用的指标可以更快地解决。
不可否认，更通用的方法不能使用您的约束，即查询是云中的点。如果有这样的解决方案，我会很感兴趣。
如果 Java 是一个选项（性能类似于现在的 C++），请查看 ELKI 库。它提供了许多多维索引的实现，包括降维方法和space-填充曲线。它还为 kNN (euclidic/non-euclidic)、聚类检测、范围查询等提供了大量算法（您通常可以使用自定义距离度量定义自己的查询过滤器）。
对于 kNN，我可以特别推荐 CoverTree and (a bit slower, but more general purpose) the PH-Tree，我都测试了最多 27 个维度。 PH-Tree 特别适用于高度集群和大型数据集（我测试了超过 100,000,000 个点）。 （免责声明：PH-Tree 基于我自己的研究，但我认为您的用例非常适合。）
但是据我所知，none 这些方法允许按照您的建议进行特殊优化。
我有一个 D 维 space 中 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] 中存在多少个点。即每个点都有不同的搜索半径。
- 不需要支持插入或删除。
谢谢
我怀疑你这个非常复杂的问题是否有一个完整而明确的答案，所以我只是分享我的想法。 您的问题规范结合了许多不能很好地协同工作的东西（高维、非欧几里德度量、完全不同类型的查询）。如果一个算法必须假设通用情况，它必然很慢。
先梳理一下已知好的数据结构的特例
- 如果您的维度是 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，并且您针对查询时间进行了优化，则预先计算 table 和所有结果。
- 如果你的维度中只有少数是周期性的，我认为你应该调整 kd-tree 算法来处理它们（为那些类似于 Vantage Point Trees 中的维度添加更复杂的比较节点）。
如果所有这些都不适用（如果您有实际应用，请与我们分享），您的案例非常通用。
除了您提到的算法之外，您还应该尝试使用几何近邻访问树 (GNAT)。 http://infolab.stanford.edu/~sergey/near.html 它们适用于通用指标（包括您的指标），还可以处理非均匀分布。
另外，我觉得你的期望很高。您可以与仅使用欧几里德度量解决问题的良好 kd 树实现（例如，https://github.com/mariusmuja/flann）进行比较。如果这需要很长时间，您不应该期望更通用的指标可以更快地解决。
不可否认，更通用的方法不能使用您的约束，即查询是云中的点。如果有这样的解决方案，我会很感兴趣。
如果 Java 是一个选项（性能类似于现在的 C++），请查看 ELKI 库。它提供了许多多维索引的实现，包括降维方法和space-填充曲线。它还为 kNN (euclidic/non-euclidic)、聚类检测、范围查询等提供了大量算法（您通常可以使用自定义距离度量定义自己的查询过滤器）。 对于 kNN，我可以特别推荐 CoverTree and (a bit slower, but more general purpose) the PH-Tree，我都测试了最多 27 个维度。 PH-Tree 特别适用于高度集群和大型数据集（我测试了超过 100,000,000 个点）。 （免责声明：PH-Tree 基于我自己的研究，但我认为您的用例非常适合。）
但是据我所知，none 这些方法允许按照您的建议进行特殊优化。