Graph-based indices for high-dimensional vectors have become the mainstream solution for large-scale approximate nearest neighbor search (ANNS) due to their high efficiency. The search process over graph-based indices typically consists of two phases: the first phase rapidly navigates from an entry point to a region near the query vector, while the second phase searches for the k nearest vectors within the localized region. However, due to the need to store a large number of adjacency relationships, graph-based indices often incur high memory overhead. In practice, this leads to storing the index in external memory, where vector and graph data are loaded on demand during ANNS. This results in frequent I/O operations, which have become the primary bottleneck, accounting for over 90% of total query time. Existing systems exploit the fact that entry points and their nearby neighbors are frequently accessed, and adopt static caching strategies that preload these points and their multi-hop neighbors into memory to reduce I/O during the first phase. However, we find that the second phase contributes the majority of I/O cost, as it involves accessing a large number of graph vertices related to the query vector to ensure high recall. Since the accessed vertices in this phase vary dynamically with each query, static caching strategies fail to capture them effectively and thus become nearly ineffective. To address this issue, a hybrid caching strategy termed GoVector is proposed, which integrates both static and dynamic components. Specifically, (1) the static cache preloads the entry point and its frequently accessed neighbors, while (2) the dynamic cache adaptively stores high-locality vertices encountered during the second phase of the search. Furthermore, to align with the similarity-driven search behavior of the second phase, a vector-similarity-aware disk layout strategy is proposed, which reorganizes the storage order of vertices to cluster similar vectors into the same or adjacent disk pages, thus enhancing data locality. This dual-optimization approach significantly improves cache hit rates and effectively reduces overall I/O overhead. Experimental results on multiple public datasets demonstrate that, under 90% recall, GoVector achieves an average of 46% fewer I/O operations, 1. 73 times higher query throughput, and 42% lower latency compared to state-of-the-art disk-based graph indexing ANNS systems.
Yijie et al. (Thu,) studied this question.