hnsw 学习笔记

hnsw: 一个简单而高效的搜索算法，学习笔记

论文原文: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, 其中第三章 motivation 写得格外不错，讲得非常清楚。

Hnsw 基于 Nsw 方法而来，这里不追溯，尝试简单讲解一下这个算法的特点。

任何一个 ANN 算法，核心都是在超大规模数据情景下，同时保证精度/速度和内存资源占用。召回速度 (logN) 是算法基本要求(要不就暴力搜索)。和传统的 kd-Tree 方法类似，两者本质的思想都是在查找过程中，如果 anchor 点为 A，当得到搜索点 B 和 dist(A, B) 之后，对于 B 附近的点 C，如果 B 和 C 距离不太远，那么 C 和 A 的距离，并不会比 B 到 A 的距离近太多。翻译成数学语言就是 abs(dist(A, C) - dist(A, B)) < dist(B, C)，这是由距离本身的性质（三角不等式）决定的。有时候自定义一些奇怪的距离，但不符合距离的定义，使用 KNN/ANN 进行搜索，肯能在算法原理层面会有点小问题。

NSW 算法的核心想法，对于 anchor A，从 B 开始搜索。依次遍历 B 的临近点，去临近点列表中寻找更近点，找到则更新，直到收敛。选取合适的临接边数目，可以使得算法非常快，但可能会存在的问题是，容易落到最小局部点。

Hnsw 方法，和 Nsw 相比，核心改动是分层结构(Hierarchical)，类似传统数据结构中的跳表。对图结构进行分层，0层包含所有点，上层节点数依次减少，每层点数目遵循指数衰减概率分布。上层点在下层依旧存在。搜索时候从上层依次向下搜索。上层点相当于 nsw 高速路。和 nsw 类似，构建图时，插入点的随机性保证了上层高速路的存在。

简单写一下几个基础子算法

子算法

SEARCH-LAYER(q, ep, ef, lc)

给定anchor point，和搜索入口点 ep，在指定层（lc）搜索最近点。算法实现和 nsw 基本相同。因为每层点数随指数衰减，除了 0层以外，其他层速度都会非常快。实际使用时，ep从最高层开始，逐层向下，直到 0 层。

代码中，维护一个 visit queue，来避免访问重复元素。

:), ef stands for ensure factor.

SELECT-NEIGHBORS-HEURISTIC(q, C, M, lc, extendCandidates, keepPrunedConnections)

构建图时，启发时获得当前点的相邻点。一个 vanilla 的思路是，选取当前点的所有最近点作为相邻点，即论文中的 SELECT-NEIGHBORS-SIMPLE(q, C, M) 算法。但这样做可能会存在一个问题是，可能会导致搜索时落入局部最优解。例如下图

绿点可能所有的最近临点都出于左下方都簇内，显然如果能和远方都 e2 相邻（即nsw中的高速路），搜索效果会更好。实际上，因为插入点的随机性，如果e2 和绿点是先插入的两个点，也会形成之间的相邻边，但毕竟不太保险。

论文里提出了启发式加相邻边的方法: M是每个点相邻点数目，选择绿点（A）最近的ef个点(ef > M)，距离从小到大依次验证，如果当前点 B 距离 A点小于B 距离 A 的所有相邻点，那么 B 点也是相邻点。这意味着，每个点的相邻点，不会聚集在一个小簇中。例如，对于绿点左下这一簇点，可能只会连接少数几个点，其他点到绿点相邻点的距离会更近。很容易看出，对于一个二维平面空间，大概最多就只能找到6/7个相邻点。因此，当M大一点时，绿点大概率可以找到 e2 作为相邻点（只要 e2 位于 ef 候选内）。

INSERT(hnsw, q, M, Mmax, efConstruction, mL)

插入点/构建图算法，所有点依次插入，对于每个点 q

按照指定分布，q 落入相应层内。
找到 q 的最近点，作为入口点 ep
使用 SELECT-NEIGHBORS-HEURISTIC 方法（使用2中获得的入口点 ep），获得该点的对应相邻点集合
更新该点的对应边，以及更新该点相邻点对应的边

K-NN-SEARCH(hnsw, q, K, ef)

搜索 topk 结果，和 SEARCH-LAYER 很像，只不过此时选取 topk，而非 top1。维护一个候选队列来存储所有结果。实际代码中，其他层的ef 是和构建时的ef相同，但 searchKnn 时的 ef_0 可以手动指定，且不小于 topk，来保证召回所有结果。

代码层面的一些要点和注意事项

代码实现: https://github.com/nmslib/hnswlib

hpp / header-only 的代码架构，多个 cpp file include 同一份 hpp 代码时，会被多次编译。当这些文件被同一入口文件链接时会出问题。可以使用命名空间 or pimpl-mode 进行规避。

快速计算距离，计算距离是整个代码调用次数最多/瓶颈最严重的代码块，任何微小的优化都是必要的。作者采用 ssh/avx 进行来对应优化。注意循环展开的写法。

 #if defined(USE_SSE)
 static float L2SqrSIMD4Ext(const void *pVect1v, const void *pVect2v,
                            const void *qty_ptr) {
   float PORTABLE_ALIGN32 TmpRes[8];
   float *pVect1 = (float *)pVect1v;
   float *pVect2 = (float *)pVect2v;
   size_t qty = *((size_t *)qty_ptr);
    
   size_t qty4 = qty >> 2;
    
   const float *pEnd1 = pVect1 + (qty4 << 2);
    
   __m128 diff, v1, v2;
   __m128 sum = _mm_set1_ps(0);
    
   while (pVect1 < pEnd1) {
     v1 = _mm_loadu_ps(pVect1);
     pVect1 += 4;
     v2 = _mm_loadu_ps(pVect2);
     pVect2 += 4;
     diff = _mm_sub_ps(v1, v2);
     sum = _mm_add_ps(sum, _mm_mul_ps(diff, diff));
   }
   _mm_store_ps(TmpRes, sum);
   return TmpRes[0] + TmpRes[1] + TmpRes[2] + TmpRes[3];
 }#endif

增删改查，删和改的实现。增和查已经在论文中详细的介绍。删除结点，作者采用了 mask-delete-node的方法，并没有改变整个图结构。改结点的实现也在代码中完成。
prefetch 使用。代码里将可能要频繁读取的数据，提前load到cpu缓存里(当然要开ssh优化)。
```
 _mm_prefetch(getDataByInternalId(*datal), _MM_HINT_T0);
```
多线程读取，在 cpp 内并没有更多细节，但是在 pybind 内进行里优化。代码在: https://github.com/nmslib/hnswlib/blob/master/python_bindings/bindings.cpp#L50

以及，update/repair 部分是使用多线程处理，格外注意多线程访问同一数据时的 lock。

一个疑问: 建图的时候，add point 是否是线程安全的，可以多线程加点吗？看issue 好像之前是可以的，后来取消了？？这里可能还需要更多细节？？

先写这么多了，搜索小白慢慢学习ing

Liufeng's Blogs

hnsw 学习笔记

子算法

代码层面的一些要点和注意事项

Search

Table of Contents