在对数时间内找到矢量之间的最小角度

Question

我有n=1000010维向量.对于每一个向量v1我想知道向量v2的夹角最小化之间v1和v2.

有没有办法比这更快地解决这个问题O(n^2)？

Answer 1

您可以在 O(n) 时间内对所有向量进行归一化，并将它们的参数化到生成的 9 维超球面上。然后，您可以在 n-1 维空间中使用空间搜索结构（例如 Kd 树）来加速最近邻居查询。有众所周知的方法（ANN）可以做到这一点。