局部敏感散列是解决这个问题的好工具。

选择n 个随机的 400 维向量。（小心，否则并非所有方向都以相同的概率被选择；选择每个维度作为标准高斯。）每个方向都真正定义了一个通过原点的超平面，将您的空间切成两半。这些向量中的任何一个与一些新向量的点积的符号告诉你它在超平面的哪一侧。所以计算n点积会得到n 0/1 位，这会产生 n 位散列。

任何散列到相同值的新向量必须位于与原点相同的一小片空间中。这些正是彼此具有高余弦相似度的向量，因为它们的相互角非常小。同样，任何散列到几乎相同值的东西——在几位上有所不同——都可能在附近。因此，您可以将最相似向量的搜索限制在一个或多个散列候选向量桶内的事物。

它对内存没有直接帮助，因为您可能需要任何特定的存储桶来满足请求。您还会失去一些准确性，因为不能保证最相似的向量位于您检查的存储桶中（尽管很可能，您检查的越多）。它让您主要以速度换取准确性。但是，您可能会发现您可以摆脱一些缓存方案，其中一些存储桶很少被访问，因此不会留在内存中。

您可以在 Oryx 中看到它的实现，我认为这非常简单。

大部分复杂性是因为它允许您指定要评估的向量的目标百分比，并根据该值和您机器的核心数计算出最佳哈希大小。

有多种方法。

1.基于L2归一化欧式距离的KD Tree

KD Tree 是一种高效的空间分割方法。参见维基百科。
因此它被用于直观地进行欧式距离邻居搜索。
为什么我说它也适用于余弦相似度，考虑 余弦相似度和 L2 归一化欧几里得距离之间的等价性。
什么时候$\mathbf{x}$和$\mathbf{y}$是单位向量，则：

$$\begin{align} ||\mathbf{x} - \mathbf{y}||_2^2 &= (\mathbf{x} - \mathbf{y})^\top (\mathbf{x} - \mathbf{y}) \\ &= \mathbf{x}^\top \mathbf{x} - 2 \mathbf{x}^\top \mathbf{y} + \mathbf{y}^\top \mathbf{y} \\ &= 2 - 2\mathbf{x}^\top \mathbf{y} \\ &= 2 - 2 \cos\angle(\mathbf{x}, \mathbf{y}) \end{align}$$ 因此，对于向量u和一组向量V 之间的相似度排序，它将产生相同的结果。请参阅堆栈交换帖子。

2.优先搜索K-Means树算法

这是一个近似的方法。
使用余弦相似度作为距离度量。
请参阅论文Scalable Nearest Neighbor Algorithms for High Dimensional Data。

3. K-Means 聚类后在子搜索空间内搜索

这是一个近似的方法。
通过余弦相似度进行 K-Means 聚类后，我们得到 k 个子集和各自的质心。我们可以让 k 为 1000 或更大。
所以对于给定的查询点，我们的步骤是：

1. 找到最近的质心，并找到相应的子集。
2. 在这个子集中搜索和排序。