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