用于O（log（n））的最近向量搜索的实现算法

Question

1. 假设我有n个表示为单位向量的文档，将其称为X。
2. 我有一个文档的向量表示形式，称其为Xi。
3. 如何在不进行强力搜索（线性时间）的情况下找到X中最接近Xi的*向量。

*距离可以是L2；在讨论单位向量时，比例成比例地等于余弦相似度。

我的近似方法（固定时间）：1.为每个向量维排序所有文档。2.使用排序索引仅对数据的子集进行暴力破解：f.e.包括每个向量维度中最接近的1000个文档，通过蛮力计算通过所有（或大多数）维度中接近的文档（1000）的L2距离。 （最多1000个）

但是，我想知道是否有一种“更干净”的精确解决方案，例如用于最接近点对问题的分而治之的算法，其运行时间为log（n）。

PS：内存也应线性扩展。但这应该没问题。

示例：我将32个浮点数存储1M文档的100维矢量表示形式。

• 矢量表示：1M * 100暗点* 32bit = 3.2Gbit = 400MB
• 排序索引：1M * 100种* 32bit = 3.2Gbit = 400MB

Answer 1

据我所知，没有算法可以在O（log n）最坏的情况下工作。但是，对于更多的矿石或更少的随机分布点，有一些精确的空间划分方法可以以O（log n）平均的方式工作。如果您的文档X是不可变的，则可以使用k-d tree。如果需要支持修改，则应尝试R* tree，它复杂得多，但支持对X的插入和删除，而且查询时间更一致（但仍取平均值O（log n））。这两个结构都使用线性空间。