转载请注明出处

我们从最最最简单的场景开始，假设在一个二维平面上，现有N个点，如下图所示

现在给你一个点，求K个最近的点（欧式距离），如下图所示

肉眼很容易可以看出，以query点为中心画个圆，慢慢往外扩展，直到包含K个点，然后这K个点就是最近的点。
看起来很容易，但这得给算法实现个眼睛啊！

二、暴力解法

这里需要遍历所有的N个点跟query点分别求个距离，然后找出K个最相近的点。
咱们专注于这个算法本身，假设距离计算的复杂度为1，那么暴力解法的复杂度为：N + NlogK

假设N很大，在没有考虑距离计算的复杂度前提下，其实这复杂度已经很高了。那如果是单机，估计实现不了在线实时计算了，有没有办法解决呢？

三、分布式解法

把点随机分布到不同机器上，然后求解的时候每台机器都算个top K出来，再合并。如下图所示：

其实这样整体复杂度并没有变化，只是利用机器资源换取时间，理论上只要机器够多，耗时还是能降低很多的。

如果没有很多机器资源，可以考虑下更优的解法。

四、分布式解法优化——IVF

既然都已经把N个点划分成A(3)个区域了，划分方法能否考虑下距离？比如最简单的按距离划分，如图所示：

这时我们在检索的时候，只需要在最近的B(>A=3)个区域暴力检索就行了。
如果A=3，B=1，那么复杂度就是： (N+NlogK)/3，这个复杂度是有很大的降低的，但是会有一个缺点，精度有所降低。如果上图所示，划分后的结果，会导致一个点出错～

实际构建区域步骤

1. 对所有点集合抽样一份小的集合。
2. 利用聚类算法（一般是Kmean）得出A个聚类中心点。
3. 把所有点都按距离分配到每个聚类中心，得到A个点集合。

实际检索步骤

1. 在A个聚类中心点中，暴力找出B个最近的聚类中心点
2. 只在B个聚类中心点所属点集中，暴力检索最近的top K个点

实际复杂度

(N + NlogK)B/A + A
A为聚类中心个数，B为检索查询的聚类中心数

虽然这种方法已经大大降低了复杂度，但还有更有的方式吗？

五、图论算法——NSW

其实就是把N个点按一定规则连边，构成一个有向图，如下图所示：

蓝色点为点集，黑色边为有向边，具体如何构造这个有向边后边再说，先说下检索流程

如下图所示：

1. 给出一个query点，如上图 红色点

2. 初始化一个点集访问记录存储

3. 初始化两个优先队列，一个存储结果候选集，只存K个元素，一个存储遍历候选集

4. 随机找一个点，当作进场开始点（如上图右下角红点，entry point）

5. entry point 加入遍历候选集，如果它并不是标记为删除的，把它放入结果候选集；

6. 从遍历候选集中取出距离query点最近的点，遍历与它所有关联的点，检查是否已经访问过

   • 如果它已经访问过，直接跳过
   • 如果没有访问过加入遍历候选集，如果关联点并不是标记为删除的，把它放入结果候选集。

7. 重复第6步骤，直到遍历候选集中距离query最近的点，都比结果候选集距离query最远的点距离query大，并且结果候选集已经足够K个点就结束。

新增构建步骤

1. 给出一个待新增的点 A
2. 在图中检索出top k个点，k = ef_construction
3. 从点A 连接其中M_个点，这M_个点从 top k里面选择，后面简称M_个点里面当前遍历的点为点B
4. 遍历每条新增连边，检查是否有相应的反向连边，也就是从点B到点A的连边
   • 如果有就跳过
   • 如果没有就给反向边连上
     • 如果点B的连边没有超过M_， 直接连上就行
     • 如果点B的连边超过了M_， 需要重新选择M_个点，保证点B只有外出M_条边

简单的说，其实就是找出top k近邻，然后连边。重点问题在于，如果 K > M_，怎么选择更加合适的邻居呢？

最简单的方式：按距离排序，选择跟新增点最近的那些。这样有可能形成孤岛，导致整个图并不是连通图，有没有更好的方式呢？

优质邻居选择方式

如下图所示：

1. 给出一个query点（黄色），top K结果候选集（红色）

2. 初始化一个结果候选集的优先队列，一个优质邻居列表

3. 从结果候选集取出一个点，判断该点与query的距离，是不是比该点与优质邻居的距离都大

   • 如果是，加入优质邻居列表
   • 如果不是，丢弃

其实就是把连边的点尽量分散。

更新点构建步骤

1. 初始化两个set 集合A、B
2. 集合A存更新点的所有邻居，集合B存更新点的 所有邻居 & 所有邻居的邻居
3. 给集合A里面的所有点，从集合B里面重新选择合适的邻居
4. 重新跑一遍新增点的流程，见上面的新增

六、图论算法优化——HNSW

其实它就是 Skip list + NSW，我们先回顾下跳表的结构吧。

这是一种很常见的数据结构，这里就不详细描述了。

真正的HNSW结构

如上图所示，其实HNSW 就是 Skip List + NSW。
跳表也是分层的，但是真正的跳表每一层是一条有序列表。
然而在HNSW中，也是跟跳表一样分层，这里每一层就是一个NSW有向图。

加上跳表思想后，nsw的操作只有一个不同的点。检索进场点是上一层的得到的最近的点，当然最上面一层还是随机点进场。

这种算法复杂度理论上是logN的，当然也只是理论上哈，而且又一定的精度损失～

实际场景上

• 如果内存够大能撑住NSW所需的内存，可以考虑直接上HNSW
• 如果内存不够，可以考虑IVF + HNSW 或者 直接随机分布 + HNSW