DiskANN++: Efficient Page-based Search over Isomorphic Mapped Graph Index using Query-sensitivity Entry Vertex

给定一个向量数据集$\mathcal{X}$和一个查询向量$\vec{x}_q$，基于图的近似最近邻搜索（ANNS）旨在构建图索引$G$，并通过在$G$上搜索来近似返回与$\vec{x}_q$距离最小的向量。基于图的ANNS的主要缺点是，对于大规模的$\mathcal{X}$来说，图索引太大了，无法放入内存中。为了解决这个问题，提出了一种基于Product Quantization（PQ）的混合方法DiskANN，将低维PQ索引存储在内存中，并在SSD中保留图索引，从而减少内存开销，同时确保高搜索准确度。然而，它存在两个I/O问题，严重影响了整体效率：（1）从入口顶点到查询邻域的路由路径过长，导致大量的I/O请求；（2）在路由过程中存在冗余的I/O请求。我们提出了一个优化的DiskANN++来解决上述问题。具体而言，对于第一个问题，我们提出了一种查询敏感的入口顶点选择策略，用动态确定的接近查询的入口顶点替换DiskANN的静态图中心入口顶点。对于第二个I/O问题，我们对DiskANN的图索引进行同构映射，优化SSD布局，并提出了一种基于优化SSD布局的异步优化Pagesearch作为DiskANN beamsearch的替代方法。在八个真实数据集上进行的全面实验研究表明，我们的DiskANN++在效率上具有卓越的优势。在相同的准确性约束下，与DiskANN相比，我们实现了明显的1.5倍到2.2倍的QPS提高。

优化基于图的近似最近邻搜索的磁盘访问效率

论文提出了DiskANN++，通过动态选择入口顶点和异步优化页面搜索来优化基于图的近似最近邻搜索的磁盘访问效率

DiskANN++通过动态选择入口顶点和异步优化页面搜索，显著提高了查询每秒的性能，相比于DiskANN，查询性能提高了1.5倍到2.2倍

近期的相关研究包括ANNS的其他优化算法，如HNSW和SPTAG