language-agnostic - 在对数时间内找到向量之间的最小角度

Question

我有 n=10000 10 维向量。
对于每个向量 v1我想知道向量v2最小化 v1 之间的角度和 v2 .

有没有比 O(n^2) 更快地解决这个问题的方法?

Answer 1

你所得到的本质上是球体上最近点的问题(因为向量之间的角度大致是它们的单位向量所在球体上点之间的距离)，所以你可能会做一些事情二元(也许三元会更容易避免太多边界问题)空间分区分解。

但这对编码来说会很不愉快，并且可能不会比 naive 方法快多少，因为只有 10,000 个点(特别是，您首先将点划分为 3^10 = 59049 个盒子，尽管其中大部分都是空的) .一亿个十元点积应该不到一秒。