如何在500维点找到100维空间中最接近的2个点？

Question

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

更新:太空是欧几里得,对不起.并感谢所有的答案.顺便说一句,这不是功课.

Answer 1

" 算法导论"中有一章致力于在O(n*logn)时间内在二维空间中找到两个最近点.你可以在谷歌书籍上查看.事实上,我建议每个人都使用分治技术来解决这个问题非常简单,优雅和令人印象深刻.

虽然它无法直接扩展到您的问题(因为常量7将替换为2^101 - 1),但它应该适用于大多数数据集.因此,如果您有合理的随机输入,它会给您O(n*logn*m)复杂n的点数和m维数.

编辑
这就是假设你有Euclidian空间.即,矢量的长度v是sqrt(v0^2 + v1^2 + v2^2 + ...).但是,如果您可以选择指标,则可以使用其他选项来优化算法.

Answer 2

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

PS趣味问题!

Answer 3

您可以尝试使用ANN库,但这样可以提供最多20个维度的可靠结果.

Answer 4

在您的数据上运行PCA,将矢量从100维转换为20维.然后创建一个K-Nearest Neighbor树(KD-Tree)并根据欧几里德距离得到最近的2个邻居.

一般如果没有.尺寸非常大,那么你必须要么采用蛮力方法(并行+分布式/地图缩减)或基于聚类的方法.