She*_*Rox 6 python indexing search time-complexity cosine-similarity
我已经预制了一个充满 512 维向量的数据库，并希望对它们实现一种有效的搜索算法。
余弦相似度：
在这种情况下，最好的算法将包含余弦相似性度量，它基本上是一个归一化的点积，即：
def cossim(a, b): numpy.inner(a, b)/(numpy.linalg.norm(a)*numpy.linalg.norm(b))
在 Python 中。
线性搜索：
这种情况下最明显和最简单的搜索是线性搜索O(n)，它迭代整个数据库并最终选择最相似的结果：
def linear_search(query_text, db): # where db is set of 512D vectors
most_similar = ("", 0) # placeholder
for query in db:
current_sim = cossim(query_text, query) # cossim function defined above
if current_sim > most_similar[1]:
most_similar = (query, current_sim)
return most_similar[0]
如您所见，应该扫描整个数据库，如果数据库包含数十万个向量，这可能会非常低效。
拟线性搜索：（部分解决）
余弦相似度和欧几里得距离之间存在基本关系（在这个答案中很好地解释了） - 我们可以从以下等式推导出欧几里得距离：
|a - b|² = 2(1 - cossim(a,b))
正如答案中提到的，随着两个向量之间的余弦变大，欧几里得距离会变小，因此我们可以将其转化为最近点对问题，可以使用递归分治算法在拟线性 O(n log n)时间内解决。
因此，我必须实现我自己的分治算法，该算法将找到最接近的一对 512 维向量。
但不幸的是，由于向量的高维数，这个问题并不能直接解决。经典的分治算法只针对二维。
二分查找索引（未解决）：
根据我的知识，优化余弦相似度搜索的最佳方法是建立索引，然后执行二分搜索。
这里的主要问题是索引 512 维向量非常困难，除了局部敏感哈希之外，我还没有意识到其他任何事情可能对索引我的数据库有用或可能没有用的东西（主要关注的是降维，这可能导致准确度相应降低）。
有一种新的Angular Multi-index Hashing方法，不幸的是，如果向量稀疏，该方法仅适用于基于二进制的向量和与维度无关的相似度计算，但事实并非如此。
最后，还有An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions，乍一看可能是最好的解决方案，但在文档中指出：
不幸的是，查询时间的指数因素确实意味着我们的算法对于大的 d 值并不实用。然而，我们在第 6 节中的经验证据表明，对于我们测试的许多分布，常数因子比定理 1 中给出的界限小得多。我们的算法可以在高达 20 的维度上提供比蛮力搜索的显着改进，并且平均误差相对较小。
我们正在尝试对20 * 25.6 = 512维度向量执行查询，这将使上述算法效率非常低。
有一个类似的问题包含类似的问题，但不幸的是尚未找到索引的解决方案。
除了拟线性搜索之外，还有什么方法可以优化此类向量的余弦相似度搜索？也许还有其他索引高维向量的方法？我相信这样的事情以前已经做过了。
我相信我已经找到了可能是一个解决方案的解决方案，它包括用于索引几百维向量数据库的随机分区树，我相信这正是我所需要的。（见这里）
谢谢！