algorithm - 如何在 500,000 个点的 100 维空间中找到最近的 2 个点？

Question

我有一个在 100 维空间中有 500,000 个点的数据库，我想找到最接近的 2 个点。我该怎么做？

更新：空间是欧几里得，对不起。并感谢所有的答案。顺便说一句，这不是家庭作业。

score 17 · Accepted Answer

算法简介中有一章致力于在 O(n*logn) 时间内找到二维空间中的两个最近点。你可以在谷歌书籍上查看。事实上，我向大家推荐它，因为他们将分而治之的技术应用于这个问题的方式非常简单、优雅和令人印象深刻。

虽然它不能直接扩展到您的问题（因为常量7将替换为2^101 - 1），但对于大多数数据集来说应该没问题。所以，如果你有合理的随机输入，它会给你O(n*logn*m)复杂性，其中n点数和m维数。

编辑
这一切都假设你有欧几里得空间。即向量的长度v为sqrt(v0^2 + v1^2 + v2^2 + ...)。但是，如果您可以选择指标，则可能还有其他选项可以优化算法。

score 7 · Accepted Answer

使用 kd 树。您正在查看最近邻问题，并且有高度优化的数据结构来处理这类确切的问题。

PS有趣的问题！

score 6 · Accepted Answer

6

您可以尝试使用ANN 库，但这只能提供最多 20 维的可靠结果。

于 2010-10-10T05:50:21.630 回答

score 6 · Accepted Answer

对您的数据运行 PCA 以将向量从 100 维转换为 20 维。然后创建一个 K-Nearest Neighbor 树（KD-Tree）并根据欧几里得距离得到最近的 2 个邻居。

一般如果没有。尺寸非常大，那么您必须采用蛮力方法（并行 + 分布式/地图缩减）或基于聚类的方法。

score 4 · Accepted Answer

使用称为 KD-TREE 的数据结构。您将需要分配大量内存，但您可能会在此过程中根据您的数据发现一两个优化。

几年前，我的朋友在写博士论文时遇到了类似的问题。他的工作在 10 个维度上大约有 100 万个点。我们构建了一个 kd-tree 库来解决它。如果您想离线联系我们，我们也许可以挖掘代码。

5 回答 5