- 假设我有n个文档表示为单位向量，称之为X
- 我有一个文件的矢量表示，称之为Xi
- 在没有粗搜索(线性时间(的情况下，我如何找到X中距离Xi最近的*向量
*距离可以是L2；当我们谈论单位向量时，成比例地等于余弦相似性。
我的近似方法(恒定时间(：1.对每个向量维度的所有文档进行排序。2.使用排序索引仅通过数据的子集进行暴力：例如，包括每个向量维度的所有最接近的1000个文档，暴力通过在所有(或大多数(维度上出现的那些文档(1000(计算L2距离。(最大1000(
然而，我想知道是否有一个"更干净"的精确解决方案，比如在log(n(时间内运行的最近点对问题的分治算法。
PS：内存也应该线性缩放。但这应该没问题。
示例：我将1M文档的100维矢量表示存储为32位浮点。
- 矢量表示：1M*100 dims*32bit=3.2Gbit=400MB
- 排序索引：1M*100个排序*32bit=3.2Gbit=400MB
据我所知，没有一种算法能在O(logn(最坏的情况下工作。然而，对于更多或更少随机分布的点，有一些精确的空间划分方法，它们以O(logn(平均值工作。如果你的文档集X是不可变的，你可以使用k-d树。如果您需要支持修改，您应该尝试R*树，它要复杂得多，但支持对X的插入和删除，而且它具有更一致的查询时间(但仍平均为O(logn((。这两种结构都使用线性空间。
回答我自己的问题：
到目前为止，我发现的最好的解决方案是Spotify的近似最近邻居搜索(哦，是的(：https://github.com/spotify/annoy
除此之外，sklearn还提供了一些快速近似最近邻居搜索的功能。https://scikit-learn.org/stable/modules/neighbors.html