diskann 是我看的第一篇关于 disk 上的 ANNS 算法，收获确实很大。有时间确实得好好读一读 diskann 的实现源码。
# 作者的动机
作者其实很简单，之前大部分 ANNS 算法都是基于内存来构建索引。如果把索引放到 disk，即使是 SSD，那么查询的延迟也会大幅度提升。所以需要提出一种基于 SSD 的 ANNS 算法，这种算法必须尽可能的降低 disk 的随机存取次数。
这里我感觉挺吃力的，有必要补全这块 io 相关的知识。
基于 SSD 索引方法必须实现 1）降低 SSD 随机访问的次数。2）round trip 的 request 数应该低于 10，最好 5。
# 作者的贡献
- DiskANN 能够只是用 64GB RAM 就 serve 1 亿的数据集，并且每个向量的维度超过的 100。95%+ 的 1-recall@1 的延迟低于 5 millisecond。
- Vanama 算法能够生成比 NSG 和 HNSW 更少的索引。（存疑
- 使用 Vanama 方法的纯内存方案，也可以达到和 NSG 和 HNSW 相似的性能（能不相似吗？你们都是类 RNG 图）
- 拆分然后 merge 的构建索引的效果和一次性读入效果差不多。
- 使用向量压缩的方法，这样压缩的向量可以读入内存中。
# Vanama 算法拆解
# 贪心检索
这个真的看腻了，就那一套。
# 邻居选择算法
你们能不能不要天天嗯编算法名啊，没活可以咬打火机。这就是一个 RNG 算法不过就是加上了一个 α 参数，这个参数起到了 relax 的作用。就这么简单。。。呵呵还长篇大论的，差点被你们唬到。
# 索引构建算法
Vanama 算法很简单，随机化一个 R 度的有向图 G，这里需要注意一个 medoid 的概念，最近接近所有节点的点：
每次查询都是从 s 开始查起，FANNG 论文也说从中心开始查比随机查的效果更好。然后用 RobustPrune 来做邻居选择。
其实这个算法完全可以就是 HNSW 的微小修改版。只是换了一种描述方式，砍掉了多层索引，然后加了一个 relax 的参数 α。
注意算法需要跑两次，一次 α=1，第二次 α>=1。
# DiskANN
DiskANN 的实现很简单:
The high-level idea is simple: run Vamana on a dataset P and store the resulting graph on an SSD.
这里有两个问题需要解决，1）如何用一亿个点进行构图。2）如果使用贪心算法对查询节点和候选列表节点进行比较。
第一个问题的解决办法，就是先使用 kmeans 把这一亿个点分为 k 个 cluster（k 取 40），然后每个点就是 assign 到 l-closest centers（l=2）。然后每次导入内存一个 cluster 并且，总共有 个数据点。最后我们把得到的图索引 merge 到一块，简单地把他们相连就行了。
解决第二个问题的方法就是使用压缩向量。使用 Product Quantization 的方法，将压线进行压缩。
构图用全精度数据，查询用压缩后的数据。
# DiskANN Index Layout
压缩后的数据全部存放到内存中，然后全精度数据和邻居索引就存放到 R 中。如果邻居个数小于 R，那么就 padding 0，保证我们可以直接使用索引号得到 offset。
