DiskANN, A Disk-based ANNS Solution with High Recall and High QPS on Billion-scale Dataset

This post introduces and explains DiskANN, a disk-based ANNS solution inspired by the NeurIPS 2019 paper. It details the motivations for such a solution, highlighting the limitations of memory-resident graph-based indexing for large datasets. The post describes the Vamana algorithm, a novel graph-based approach with a flexible trimming strategy, and how DiskANN adapts it for SSD-resident indexing. Key optimizations like caching hotspots and beam search are explained to reduce disk I/O. The post also includes experimental comparisons of Vamana with NSG and HNSW, and outlines the experimental setup for DiskANN.