1

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

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

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

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

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

谢谢

4

2 回答 2

2

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

我们先来梳理一下已知好的数据结构的特殊情况。

  • 如果您的维度为 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-tree 实现（例如，https://github.com/mariusmuja/flann ）进行比较。如果这需要很长时间，您不应该期望更通用的指标能够更快地解决。

诚然，更通用的方法不能使用查询是云中的点的约束。如果有任何这样的解决方案，我会非常感兴趣。

于 2016-05-12T09:01:34.457 回答
0

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

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

于 2016-05-17T12:44:15.537 回答