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

arXiv: https://arxiv.org/abs/2310.00402 · HTML: https://mlsanity.com/paper/2310.00402/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2023.

## Built on by (most cited first, 7 of 7)

- [Personal LLM Agents: Insights and Survey about the Capability, Efficiency and Security](https://mlsanity.com/paper/2401.05459/) (2024)
- [Quake: Adaptive Indexing for Vector Search](https://mlsanity.com/paper/2506.03437/) (2025)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [Scalable Disk-Based Approximate Nearest Neighbor Search with Page-Aligned Graph](https://mlsanity.com/paper/2509.25487/) (2025)
- [Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.04713/) (2024)
- [Text2VectorSQL: Towards a Unified Interface for Vector Search and SQL Queries](https://mlsanity.com/paper/2506.23071/) (2025)
- [Passing the Baton: High Throughput Distributed Disk-Based Vector Search with BatANN](https://mlsanity.com/paper/2512.09331/) (2025)

## Abstract (arXiv)

Given a vector dataset X and a query vector vecxq, graph-based Approximate Nearest Neighbor Search (ANNS) aims to build a graph index G and approximately return vectors with minimum distances to vecxq by searching over G. The main drawback of graph-based ANNS is that a graph index would be too large to fit into the memory especially for a large-scale X. To solve this, a Product Quantization (PQ)-based hybrid method called DiskANN is proposed to store a low-dimensional PQ index in memory and retain a graph index in SSD, thus reducing memory overhead while ensuring a high search accuracy. However, it suffers from two I/O issues that significantly affect the overall efficiency: (1) long routing path from an entry vertex to the query's neighborhood that results in large number of I/O requests and (2) redundant I/O requests during the routing process. We propose an optimized DiskANN++ to overcome above issues. Specifically, for the first issue, we present a query-sensitive entry vertex selection strategy to replace DiskANN's static graph-central entry vertex by a dynamically determined entry vertex that is close to the query. For the second I/O issue, we present an isomorphic mapping on DiskANN's graph index to optimize the SSD layout and propose an asynchronously optimized Pagesearch based on the optimized SSD layout as an alternative to DiskANN's beamsearch. Comprehensive experimental studies on eight real-world datasets demonstrate our DiskANN++'s superiority on efficiency. We achieve a notable 1.5 X to 2.2 X improvement on QPS compared to DiskANN, given the same accuracy constraint.