相似性搜索就是根据某些特征,在大量的样本集中搜寻出与目标样本最相似的一个或多个样本。
相似性搜索问题无论是在学术界还是工业界,都是一个研究得比较多的问题。相似性搜索有两类方法:存在最近邻检索(Nearest Neighbor Search, NNS)和近似最近邻检索(Approximate Nearest Neighbor Search, ANNS)。NNS 最初是用目标向量和数据库向量逐条计算距离,结果最为精确。后来又产生了相关算法(比如 KD-tree),使得搜索效率大为提高,但在应对海量高维度数据时显得力不从心。ANNS 则是在可接受的精度条件下通过把向量分簇建立索引,大幅提高搜索效率,是大规模相似性搜索场景下所使用的主要方法。
因此,相似性搜索问题往往会转化成向量检索问题。
这里先给出向量检索的定义:向量检索是指通过某种数学量化模型,对向量构建一种时间和空间都比较高效的数据索引结构,使得我们能够实时地获取跟查询向量尽可能最相近的 K 个向量。从定义可以看到,要设计一种高效的向量检索引擎,应该满足 3 个基本条件,即: