局部敏感哈希(Locality Sensitive Hashing)也是一种使用近似最近邻搜索的索引技术。它的特点是快速,同时仍然提供一个近似、非穷举的结果。LSH 使用一组哈希函数将相似向量映射到“桶”中,从而使相似向量具有相同的哈希值。这样,就可以通过比较哈希值来判断向量之间的相似度。
通常,我们设计的哈希算法都是力求减少哈希碰撞的次数,因为哈希函数的搜索时间复杂度是 O(1),但是,如果存在哈希碰撞,即两个不同的关键字被映射到同一个桶中,那么就需要使用链表等数据结构来解决冲突。在这种情况下,搜索的时间复杂度通常是 O(n),其中n是链表的长度。所以为了提高哈希函数的搜索的效率,通常会将哈希函数的碰撞概率尽可能的小。
但是在向量搜索中,我们的目的是为了找到相似的向量,所以可以专门设计一种哈希函数,使得哈希碰撞的概率尽可能高,并且位置越近或者越相似的向量越容易碰撞,这样相似的向量就会被映射到同一个桶中。
等搜索特定向量时,为了找到给定查询向量的最近邻居,使用相同的哈希函数将类似向量“分桶”到哈希表中。查询向量被散列到特定表中,然后与该表中的其他向量进行比较以找到最接近的匹配项。这种方法比搜索整个数据集要快得多,因为每个哈希表桶中的向量远少于整个空间中的向量数。
那么这个哈希函数应该如何设计呢?为了大家更好理解,我们先从二维坐标系解释,如下所图示,在二维坐标系中可以通过随机生成一条直线,将二维坐标系划分为两个区域,这样就可以通过判断向量是否在直线的同一边来判断它们是否相似。例如下图通过随机生成 4 条直线,这样就可以通过 4 个二进制数来表示一个向量的位置,例如 A 和 B 表示向量在同一个区域。
(, 下载次数: 0)
上传
点击文件名下载附件
lsh1
这个原理很简单,如果两个向量的距离很近,那么它们在直线的同一边的概率就会很高,例如直线穿过 AC 的概率就远大于直线穿过 AB 的概率。所以 AB 在同一侧的概率就远大于 AC 在同一侧的概率。
当搜索一个向量时,将这个向量再次进行哈希函数计算,得到相同桶中的向量,然后再通过暴力搜索的方式,找到最接近的向量。如下图如果再搜索一个向量经过了哈希函数,得到了 0110 的值,就会直接找到和它同一个桶中相似的向量 D。从而大大减少了搜索的时间。
(, 下载次数: 0)
上传
点击文件名下载附件
lsh
关于更多 LSH 算法的细节,可以参考这篇博客。
Random Projection for LSH 随机投影
同样,随机投影也是一种近似方法,并且投影质量取决于投影矩阵。通常情况下,随机性越大的投影矩阵,其映射质量就越好。但是生成真正随机的投影矩阵可能会计算成本很高,特别是对于大型数据集来说。关于更多 RP for LSH 算法的细节,可以参考这篇博客。
相似性测量 (Similarity Measurement)
在实际的业务场景中,往往不需要在整个向量数据库中进行相似性搜索,而是通过部分的业务字段进行过滤再进行查询。所以存储在数据库的向量往往还需要包含元数据,例如用户 ID、文档 ID 等信息。这样就可以在搜索的时候,根据元数据来过滤搜索结果,从而得到最终的结果。
为此,向量数据库通常维护两个索引:一个是向量索引,另一个是元数据索引。然后,在进行相似性搜索本身之前或之后执行元数据过滤,但无论哪种情况下,都存在导致查询过程变慢的困难。
除此之外,访问控制设计的是否充足,例如当组织和业务快速发展时,是否能够快速的添加新的用户和权限控制,是否能够快速的添加新的节点,审计日志是否完善等等,都是需要考虑的因素。
另外,数据库的监控和备份也是一个重要的因素,当数据出现故障时,能够快速的定位问题和恢复数据,是一个成熟的向量数据库必须要考虑的因素。
API & SDK
对比上面的因素选择,API & SDK 可能是往往被忽略的因素,但是在实际的业务场景中,API & SDK 往往是开发者最关心的因素。因为 API & SDK 的设计直接影响了开发者的开发效率和使用体验。一个优秀良好的 API & SDK 设计,往往能够适应需求的不同变化,向量数据库是一个新的领域,在如今大部分人不太清楚这方面需求的当下,这一点容易被人忽视。
传统数据的扩展