algorithm - 在一组向量中找到最佳的余弦相似度

我有n个向量，每个向量有m个元素(实数)。我想找到所有对之间的余弦相似度最大的对。

直接的解决方案将需要O(n2m)时间。

有没有更好的解决方案？

更新

Cosine similarity / distance and triangle equation启发我可以将“余弦相似度”替换为“弦长”，
失去精度，但会大大提高速度。 (存在许多解决公制空间中的最近邻居的解决方案，例如ANN)

最佳答案

余弦相似性sim(a,b)是related to Euclidean distance |a - b|，由

|a - b|² = 2(1 - sim(a,b))

用于单位向量a和b。

这意味着当通过L2范数归一化后，欧几里得距离最小时，余弦相似度最大，问题减少到closest pair of points problem，可以在O(n lg n)时间内解决。