algorithm - 测量稀疏向量与 30k 其他预定义稀疏向量之间的最小角度

Question

我有一个稀疏向量，比方说<0,0,...,0,8,3,...>

我想从一组预定义的 30k 个向量中找到 k 个最近的向量。我正在做的特定“近”计算类似于标量乘法来找到向量之间的角度。

有没有办法优化这个过程(除了进行 30k 次计算并保存前 k 个结果的天真方法)？我感兴趣的是优化运行时间，而不是 mem

Answer 1

一个简单的解决方案是预先计算所有角度并将它们存储在查找表(上三角矩阵)中。那将花费 30k * 30k/2 = 450m。那将是最快的。