ANNOY & HNSW

发布时间：2023-06-15 11:47:25

ANNOY我们之前已经介绍了IVF的ANN检索算法，核心思路就是对全局的向量做聚类，然后在搜索的过程中只对特定的聚类簇中包含的特征向量

ANNOY

我们之前已经介绍了IVF的ANN检索算法，核心思路就是对全局的向量做聚类，然后在搜索的过程中只对特定的聚类簇中包含的特征向量做检索，ANNOY，全名Approximate Nearest Neighbors Oh Yeah，也是使用类似的思路，不过和IVF相比，采用类似二叉树的方式进行检索，整个算法表达上更加朴素清晰，具体可以参考以下这篇链接，实在是笔者看到过的对ANNOY解释的最为清晰的一篇文章，笔者在此仅做以上介绍和对比，就不造重复的轮子了。

Annoy搜索算法(Approximate Nearest Neighbors Oh Yeah)

SW

HNSW（Hierarchical Navigable Small Worlds）是一种基于图的ANN搜索算法，谈到HNSW，我们就不得不从从SW说起，一种通俗的分类方式，将图分为三种：

正则图（Regular Graph）：指各顶点的度均相同的无向简单图
随机图（Random Graph）：指各顶点随机进行连接的无向简单图
小世界（Small World）

这里我们先忽略小世界的定义，关注正则图与随机图之间的区别，我们使用以下代码来模拟正则图和随机图

# Consider the scenario of 99 verticesnnum_vertex = 99nn# predefined reg_degree as 4nreg_degree = 4nn# generate a regular graphndef Gen_Reg_Graph(num_vertex, reg_degree):n tmp_dict_reg = {}n inf_big = 999nn for i in range(num_vertex):n tmp = []n for j in range(reg_degree // 2):n tmp.append((i + j + 1)% num_vertex)n tmp.append((i - j - 1)% num_vertex)n tmp_dict_reg[i] = tmpn n reg_graph = np.ones((num_vertex, num_vertex)) * inf_bign for i in range(num_vertex):n for j in tmp_dict_reg[i]:n reg_graph[i][j] = 1n # keep diaganol as 0n reg_graph[i][i] = 0n return reg_graphnnreg_graph = Gen_Reg_Graph(num_vertex, reg_degree)nprint(reg_graph)nn# generate a random graphndef Gen_Rnd_Graph(num_vertex):n tmp_dict_reg = {}n inf_big = 999n rnd_graph = np.ones((num_vertex, num_vertex)) * inf_bign # randomly set two vertices connectedn for i in range(num_vertex):n for j in range(num_vertex):n if random.randint(1,20) % 17 == 0:n rnd_graph[i][j] = 1n rnd_graph[j][i] = 1n # keep diaganol as 0n rnd_graph[i][i] = 0n return rnd_graphnnrnd_graph = Gen_Rnd_Graph(num_vertex)nprint(rnd_graph)nn# Dijkstrandef dijkstra(start, graph):n passed = [start]n nopass = [x for x in range(graph.shape[0]) if x != start]n dis = graph[start]n n while len(nopass):n idx = nopass[0]n for i in nopass:n if dis[i] < dis[idx]: idx = inn nopass.remove(idx)n passed.append(idx)nn for i in nopass:n if dis[idx] + graph[idx][i] < dis[i]: dis[i] = dis[idx] + graph[idx][i]n return disnndis_reg = dijkstra(0, reg_graph)nprint("Distance in regular graph {}".format(dis_reg))ndis_rnd = dijkstra(0, rnd_graph)nprint("Distance in random graph {}".format(dis_rnd))

我们首先通过以上代码生成了一个正则图和一个随机图，并通过dijkstra（随手扒了一个dijktra的python实现）来观察其中一个点到其他点的距离，最终得到以下输出（这里的distance值可以理解为从一个顶点到另一个顶点的“跳跃次数”）

Distance in regular graph [ 0. 1. 1. 2. 2. 3. 3. 4. 4. 5. 5. 6. 6. 7. 7.n 8. 8. 9. 9. 10. 10. 11. 11. 12. 12. 13. 13. 14. 14. 15.n 15. 16. 16. 17. 17. 18. 18. 19. 19. 20. 20. 21. 21. 22. 22.n 23. 23. 24. 24. 25. 25. 24. 24. 23. 23. 22. 22. 21. 21. 20.n 20. 19. 19. 18. 18. 17. 17. 16. 16. 15. 15. 14. 14. 13. 13.n 12. 12. 11. 11. 10. 10. 9. 9. 8. 8. 7. 7. 6. 6. 5.n 5. 4. 4. 3. 3. 2. 2. 1. 1.]nDistance in random graph [ 0. 3. 1. 2. 3. 2. 2. 3. 3. 2. 1. 1. 2. 1. 1. 2. 3. 3.n 3. 3. 2. 2. 3. 3. 1. 2. 2. 2. 2. 2. 3. 2. 2. 2. 2. 1.n 2. 2. 2. 2. 2. 3. 2. 2. 3. 2. 3. 1. 2. 2. 3. 2. 2. 2.n 3. 3. 3. 2. 2. 2. 2. 2. 3. 2. 2. 2. 3. 2. 2. 3. 2. 2.n 3. 3. 2. 3. 2. 2. 2. 3. 2. 3. 2. 3. 2. 2. 2. 2. 2. 3.n 1. 2. 3. 3. 3. 2. 3. 3. 3.]

不难看出，在正则图中，从一个点到另一个点的搜索次数在特定情况下要远远高于随机图（当然这和我们在随机图中设计的连通的概率也有关系），通常情况下，正则图中的顶点的路径更长，但是同时更聚合，也就是空间中距离相近的两个点是互相连接的。而随机图中的顶点尽管路径更短，但是几乎是完全不聚合的，也就是很难保证在空间中相邻的两个点在图中是相连接的，故而很难在实际的向量检索、ANN等场景中使用随机图。

而Small World则基于两者之间，在原本的正则图中类似“击鼓传花”的这个搜索的过程中，偶然的可以在两个相去甚远的点中来个“长传”，这可以极大的加速了整个检索的步骤。

# predefined reg_degree as 4nreg_degree = 4nndef Gen_Reg_Graph(num_vertex, reg_degree):n tmp_dict_reg = {}n inf_big = 999nn for i in range(num_vertex):n tmp = []n for j in range(reg_degree // 2):n tmp.append((i + j + 1)% num_vertex)n tmp.append((i - j - 1)% num_vertex)n tmp_dict_reg[i] = tmpn n sw_graph = np.ones((num_vertex, num_vertex)) * inf_bign for i in range(num_vertex):n for j in tmp_dict_reg[i]:n sw_graph[i][j] = 1n # keep diaganol as 0n sw_graph[i][i] = 0n n # randomly set 2 express wayn for i in range(2):n x = random.randint(0,99)n y = random.randint(0,99)n sw_graph[x][y] = 1n sw_graph[y][x] = 1n return sw_graphnnsw_graph = Gen_Reg_Graph(num_vertex, reg_degree)nprint(sw_graph)ndis_sw = dijkstra(0, sw_graph)nprint("Distance in random graph {}".format(dis_sw))

输出为

Distance in small world graph [ 0. 1. 1. 2. 2. 3. 3. 4. 4. 5. 5. 6. 6. 7. 7.n 8. 8. 9. 9. 10. 10. 11. 11. 12. 12. 13. 13. 14. 14. 15.n 15. 16. 16. 17. 17. 16. 16. 15. 15. 14. 14. 13. 14. 14. 15.n 15. 16. 16. 17. 16. 16. 15. 15. 14. 14. 13. 13. 12. 12. 11.n 11. 10. 10. 9. 10. 10. 11. 11. 12. 12. 13. 13. 14. 13. 13.n 12. 12. 11. 11. 10. 10. 9. 9. 8. 8. 7. 7. 6. 6. 5.n 5. 4. 4. 3. 3. 2. 2. 1. 1.]

NSW

我们回到上面正则图的概念，根据给定的顶点（在实际的检索场景中，常常表现为多个特征向量），我们总是可以通过德劳内三角形的分割方式，将不同的顶点进行联通，然后在图中随机创建Expressway mechanism（上面说的“长传”的学名），也就是建立比较遥远的两个点间的连接。但是这种方法在实际场景中是行不通的，德劳内三角形分割的时间复杂度为，其中d是顶点的维度，在高维的场景中时间复杂度迅速膨胀到极高的规模（鉴于是非多项式时间的，所以大概也可以算是NP问题？）。

而论文中解决这个问题的方式却实打实的简单到令人发指，整个NSW图构建的算法步骤可以用伪代码描述如下

V: set of verticesnG: inital state of NSW graphnnfor v_i in V:n V.pop(v_i) # 这一步建议随机在V中选择v_i特征向量n for v_j in G.find_topk_NN(v_i):n G.connect(v_i, v_j)

对，随机选择V中的一个顶点，找到已建立的NSW图中的topk最近邻（NN），将其连接，重复这个过程直到V中的所有的点都已经被便利。

为什么按照上面这个过程就可以得到一个很好的NSW图呢？回想下上面提到的SW具有两个特征，SW具有正则图中的局部聚合的特性，但是同时也有随机图中的Expressway mechanism，而我们随机添加顶点的过程中，在算法的早期，因为图中的点数量较少，所以很容易建立两个遥远的点之间的Expressway，而在算法的后期，因为图中的点数量已经多起来，对于全局的数据空间具有一定的代表性，那么添加的新的点在选取topk的时候，基本上都会选择到其具备相邻的点，那么就保证了SW图中的局部聚合的特性。

跳表

想要更好的理解HNSW，就首先需要理解跳表的原理，跳表是可以理解为一种特殊的链表(下图from百度百科)

可以看到，跳表其实也使用了我们上文中所说的这种Express Mechanism机制，只不过跳表上的Express Mechanism建立在一维空间之中（类似于数轴），同时由多层链表进一步加速链表上特定元素的搜索过程。

对于一个元素的检索过程，比如检索数字3，首先在顶层的链表中执行比对，在第一层中发现3比head要大，但是比4要小，那么我们就向下进入第二层链表中检索，以此类推。

HNSW

而HNSW就是在普通的NSW之上，结合跳表的思路来进一步优化检索的性能（在高层中进行搜索比在底部局部执行搜索的速度要快得多得多）

我们在检索的过程中，分为两个不同的阶段，分别是建立HNSW图以及在HNSW图中进行检索

建立HNSW图：INSERT

HNSW图的建立可以粗略的被伪代码描述如下（详细描述请移步论文）

vi: vectex to be insertednep: enter point at first layernhighest_layer: fewest verticesnlowest_layer: all verticesnn# specify a layer to insert vininserted_layer = random_ln_gen(vi)nn# go down to the layer vi is inserted, without building new connections (search process)nfor layer in [highest_layaer:inserted_layer]:n NN = Search_Layer(ep, layer, vi)n ep = Select_New_Ep_From_NN(vi, NN)nn# going down to layer0, building new connections at each layernfor layer in [inserted_layer:lowest_layer]:n NN = Search_Layer(ep, layer, vi)n NiceNN = Select_Neighbors(NN) #对于理解HNSW的过程而言，事实上不需要理解Select_Neighbors也可以n Update_Connections(NiceNN, vi)

执行HNSW中的检索：SEARCH

执行HNSW中的检索可以粗略的被伪代码描述如下（详细描述请移步论文）

vi: vertex to be searchednep: enter point at first layernn# go down to the layer vi is inserted, without building new connectionsnfor layer in [highest_layaer:lowest_layer]:n NN = Search_Layer(ep, layer, vi)n ep = Select_New_Ep_From_NN(vi, NN)nnFinal_Search(NN)