Vector DB

References

• [FIXME][EP09] 向量数据库和出海创业
• Locality Sensitive Hashing (LSH): The Illustrated Guide
• Write You a Vector Database

常用的向量检索算法

1. 量化（以一定的模型性能换取查询效率），RabitQ。

2. Locality Sensitive Hashing (LSH)：传统的 hash 函数一般都希望减少碰撞，将一个 key 映射到尽可能分散的空间，而 LSH 则恰恰相反，通过将比较近的 embedding 映射到尽可能相同的 bucket 中，这样就能快速找到相邻的节点。

   

3. NSW(Navigate Small World)

   

   选择若干个 entry，然后维护一个有固定大小上限的队列，以类似 BFS 的方式，将距离目标向量最近的向量入队。需要多个 entry 的原因是，如果只采用一个，很容易陷入局部最优解。

   为了加速查询，我们会限制图中点之间的边的数量为 max_m。当我们插入一个节点的时候，其邻居节点的边可能会超过 max_m，所以我们需要重新计算这些节点的最近邻。

4. HNSW(Hierarchical Navigate Small World)

   将图以类似跳表的形式组织，但是无论是 NSW 还是 HNSW 都会涉及大量磁盘随机 I/O，性能受限。

5. IVF(Inverted File)

   

   使用 Kmeans 将向量分为多个 cluster。并根据 cluster 的标识建立对向量的倒排索引。由于索引存储在一起，可以被顺序读写。

   在查询的时候，除了判断距离查询向量最近的质心对应的集群，还需要判断临近的集群。因为集群的质心可能距离查询向量比较远，但是边缘的点可能比较近。