目录
简介
相似性搜索的概念是在n维空间中通过比较数据之间的相似性，寻找与输入点最接近的目标点。
解决方案
为了解决该问题，最常用解决方案就是对数据集使用索引技术。通过事先对数据集进行索引，从而达到高效搜索n维空间数据的目的。在相似性搜索中，数据索引的方案可以分为三大类，分别是哈希索引、树索引以及图索引。
哈希索引
一种常用的索引方法是局部敏感哈希(Locality Sensitive Hashing，LSH)算法。LSH的方法通常更适合于范围搜索，而非近邻搜索。
下面是LSH函数h的条件：
1. 如果 d(x,y)<=d1，则 P(h(x)=h(y))>=p1
2. 如果 d(x,y)>=d2，则 P(h(x)=h(y))<=p2
树索引
常见树索引方案：R树、kd树。
常见开源库：FLANN（Fast library for approximate nearest neighbors）。
图索引
图索引的方法是通过近邻图寻找最近的节点。最近邻图(NNG)中的每一个点通过距离计算被连接到最接近的点上。由于需要对所有节点计算最邻近点，通常KNNG在构建的时候随着节点数量的上升会非常耗时。但在实际运用中，采用一种ANNG的方案可以大大优化构建过程。2015年基于ANNG发布的NGT的开源项目，也已经被应用在多项实际业务上了。