数百万个三维点：如何找到离给定点最近的十个点？

Question

数百万个三维点：如何找到离给定点最近的十个点？

algorithmgraphgraphicsknnnearest-neighbor

71

一个3D点由(x,y,z)定义。任意两个点（X，Y，Z）和（x，y，z）之间的距离是d= Sqrt [（X-x）^2 +（Y-y）^2 +（Z-z）^2]。现在有一个包含一百万个条目的文件，每个条目都是空间中的一些点，没有特定顺序。给定任何点（a，b，c），找到离它最近的10个点。您将如何存储这一百万个点，并从该数据结构中检索这10个点。

答案：我们可以使用KD树来存储这一百万个点，因为KD树是一种高维数据结构，可以用于快速查找最近邻居。对于每个节点，树按照特征进行拆分，并将点分配给相应的子节点，直到叶子节点包含单个点。要查找最近的10个点，请遍历树以查找最接近（a，b，c）的叶子节点。然后，向上回溯树，检查每个祖先节点是否有更接近（a，b，c）的点。如果是，则将其子节点中的其他点添加到候选列表中。最后，按与（a，b，c）的距离排序并选择前10个点。

- Kazoom

1

你是在被告知点(a,b,c)之前还是之后创建并填充数据结构？例如，如果您先创建数据结构，然后用户输入(a,b,c)并希望立即得到答案，则David的答案无效。 - Tyler

3

好的观点（无双关语！）当然，如果事先不知道（a，b，c），那么更多是优化现有点列表以便根据3D位置进行搜索，而不是实际执行搜索的问题。 - David Z

6

需要澄清的是，是否需要考虑准备数据结构和将百万点存储在该数据结构中的成本，或者仅考虑检索性能。如果这个成本并不重要，那么无论你检索这些点的次数有多少，kd树都会胜出。但如果这个成本很重要，那么你还应该指定你期望运行搜索的次数（对于少量的搜索来说暴力搜索会胜出，对于更大的kd搜索会胜出）。 - Unreason

12个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rubys · Answer 1

计算它们之间的距离，并在O(n)时间内进行Select(1..10, n)。我想那将是一个朴素的算法。

- Unreason · Answer 2

这个问题需要进一步定义。

1) 关于预索引数据的算法决策取决于您是否可以将整个数据保存在内存中。使用kd树和八叉树，您不必将数据保存在内存中，并且性能从这一事实中获益，不仅因为内存占用更低，而且因为您不必读取整个文件。

使用暴力搜索，您必须读取整个文件并重新计算每个新点的距离。

但是，这可能对您不重要。

2) 另一个因素是您将不得不多少次搜索一个点。

正如J.F. Sebastian所述，有时即使在大型数据集上，暴力搜索也更快，但请注意考虑他的基准测试从磁盘读取整个数据集（一旦建立了kd树或八叉树并写入某个位置就不必要了），并且它们只测量一次搜索。