开始我的阅读论文之旅了，第一篇论文挑了综述来看，目前来看，这玩意比 6.824 课上读的论文要简单多了。。。至少我能看个大概。
# abs+intro
这篇文章对于 13 种基于图的 ANNS 算法进行研究，使用了 8 个真实世界的数据集和 12 个人工数据集。ANNS 就是 Approximate nearest neighbor search ，关于为啥要研究这玩意，作者给出理由，因为：NNS 在很多领域比如信息检索、数据挖掘、机器学习巴拉巴拉很有用，然后因为高维数据的 NNS 太难搞了，于是大伙就整出了 ANNS，牺牲一点精度换取更高的效率。
基于图的 ANNS 大致运行逻辑：
给定一个查询 q 和图索引。第一步，初始化一个 seed vertex 作为 result vertex r。第二步，比较这个节点自身以及它的邻居节点与 q 之间距离，如果 dis(q, n) < dis(r, q) ，那么说明邻居节点离 q 更近，于是我们用 n 来替换 r 。第三步，循环迭代，知道满足节点 r 与 q 的距离没法再减少了，也就是 。
# 基本算法
# Navigable Small World graph (NSW)
参考链接：https://blog.csdn.net/sinat_28704977/article/details/86605331
https://leovan.me/cn/2020/08/nearest-neighbor-search/
一句话总结：朴素插入 + 高速公路
有时间可以看看原文，我怀疑 tmp 是否真的有需要？
# Hierarchical Navigable Small World graphs (HNSW)
类似于跳表进行多层查询：
Fast Approximate Nearest Neighbor Graph (FANNG)
Neighborhood Graph and Tree (NGT)
我本来想一一看完这些算法的，但是感觉太浪费时间了，而且我不觉得我一次性就可以把这些算法理解透彻。。。一边看一边补这方面的知识吧，感觉太吃亏了。
# ANNS 大致流程
作者将 13 种 ANNS 算法拆散为 7 个不同的组件，并且对这些部分分别进行评价：
# C1：Initialization
作者根据构建索引的方式将 ANNS 算法划分为 3 种： Divide-and-conquer 、 Refinement 以及 Increment 。
分治法就是将数据集进行拆分，通过合并子图来得到最终的索引。优化法就是通过 Neighbor 初始化来初始化图，然后对初始化得到的图进行优化。而增长法就是通过不断插入节点，也就是把每一次的插入当做一次 ANNS 查询来对待。
# C2: Candidate neighbor acquisition
这一步我们需要抽取合适的候选邻居。对于分治法，由于它做了数据集的切分，所以直接用切分得到的子集 S_i \textbackslash {p} 作为候选邻居，而优化法和增长法则使用 ANNS 查询的方式来获得候选邻居，作者的原话
they consider 𝑝 as a query and execute ANNS on 𝐺𝑠𝑢𝑏 or 𝐺𝑖𝑛𝑖𝑡, and finally return the query result as candidate neighbors of 𝑝.
# C3: Neighbor selection
邻居的选择有点讲究，需要兼顾距离和空间分布。HNSW、FANNG、SPTAG 和 NSG 等算法通过考虑邻居之间的距离来实现邻居尽量分布。对于 ，如果满足 ，那么我们把节点 x 也加入到 p 的邻居节点集合中。（启发式选边）
还有一些算法通过设置角度阈值来强制实现邻居分散。
为什么要实现分散？我的理解是：如果邻居节点聚集一块也就是邻居节点都很类似，那么通过相似的邻居节点进行的查询通常会导向相同的目的地。
# C4: Seed preprocessing
Seed 的预处理也是比较重要的一环。对于 HNSW 来说，它构造的多层结构实际上就是实现了 seed 的预测力，每次我们都是去最上层的节点。NSG 和 Vamana 使用了近似质心当做 seed，NSSG 则是直接 randomly 选取。
而对于某些算法，它的 seed 是动态的。SPTAG、EFANNA、HCNNG 和 NGT 使用了额外的树，比如 KD 树、k-means 树、VP 树等，通过这些额外的索引来获得接近查询点 q 的 seed。
# C5: Connectivity
增长法天然具有强连通性，而优化法通过 DFS 来实现，分治法则是通过多次执行数据集的切分和子图的构建来保证连通性。
# C6: Seed acquisition
现有的 SOTA 算法都使用了 seed 预处理方法也就 C4，作者在文章后续也说了对节点的预处理并不会显著地增加构建索引的开销。
# C7: Routing
这里需要理解一个贪心算法也就是 BFS（Best First Search），论文是这样描述的：
其实这玩意就是 NSW 的查询。这种查询方式有两种缺点，1）容易陷入局部最佳。2）路由效率低。
解决问题一的方法可以是将距离比较变成搜索半径比较，或者从多个 seed 开始。
解决问题而的方法是用 guided search 虽然我不清楚这是什么东西。
# 实验
实验部分就是从这 7 个角度一一比较这 13 种算法的性能，说实话，我看了确实有收获，但是真的很难写出来，对这些东西没有啥实感。
关于这种 performance-recall 图：
刚开始我真的搞不懂，这种不同 recall 是怎么实现的，后来跟小萌哥聊了一会搞懂了。原来并不是我们在调节 recall，而是通过改变不同的参数获得不同 recall 下对应的查询时间。比如对于 HNSW 算法，我们知道 M 和 ef 均会导致影响查询的性能，如果 M 和 ef 增大，那么毫无疑问可以提高 recall，而这种 recall-performance 图就是通过改变算法的参数，这样就可以得到不同的 recall 已经这个 recall 下对应的查询时间。我们通过比较不同的曲线，哪个更靠右，越靠右说明算法的性能越好。
所以，并不是通过固定相同的 recall 比较查询时间，而是比较这个曲线图。
# 思考
作者用 L2 距离来做实验，但是没法考虑其他距离度量的方法？L1 的比较劣势在哪里？
有没有必要去看 hash、量化、树等方法？
什么消耗的内存最少？
