# Scalable Disk-Based Approximate Nearest Neighbor Search with Page-Aligned Graph

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 51 references that are in the map.
- First posted on arXiv 29 Sep 2025.

## Builds on (most cited first, 22 of 22)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Atlas: Few-shot Learning with Retrieval Augmented Language Models](https://mlsanity.com/paper/2208.03299/) (2022)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [In-Context Retrieval-Augmented Language Models](https://mlsanity.com/paper/2302.00083/) (2023)
- [Embedding-based Retrieval in Facebook Search](https://mlsanity.com/paper/2006.11632/) (2020)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Learning Customized Visual Models with Retrieval-Augmented Knowledge](https://mlsanity.com/paper/2301.07094/) (2023)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [SPFresh: Incremental In-Place Update for Billion-Scale Vector Search](https://mlsanity.com/paper/2410.14452/) (2024)
- [Visual Search at Alibaba](https://mlsanity.com/paper/2102.04674/) (2021)
- [Uni-Retriever: Towards Learning The Unified Embedding Based Retriever in Bing Sponsored Search](https://mlsanity.com/paper/2202.06212/) (2022)
- [Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment](https://mlsanity.com/paper/2401.02116/) (2024)
- [The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform](https://mlsanity.com/paper/1908.07389/) (2019)
- [DiskANN++: Efficient Page-based Search over Isomorphic Mapped Graph Index using Query-sensitivity Entry Vertex](https://mlsanity.com/paper/2310.00402/) (2023)
- [Machine learning approach for text and document mining](https://mlsanity.com/paper/1406.1580/) (2014)
- [MicroNN: An On-device Disk-resident Updatable Vector Database](https://mlsanity.com/paper/2504.05573/) (2025)
- [Starling: A Scalable Query Engine on Cloud Function Services](https://mlsanity.com/paper/1911.11727/) (2019)
- [LSM-VEC: A Large-Scale Disk-Based System for Dynamic Vector Search](https://mlsanity.com/paper/2505.17152/) (2025)
- [Pyramid: A General Framework for Distributed Similarity Search](https://mlsanity.com/paper/1906.10602/) (2019)
- [Towards Efficient and Scalable Distributed Vector Search with RDMA](https://mlsanity.com/paper/2507.06653/) (2025)

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

- [Cloud-Native Vector Search: A Comprehensive Performance Analysis](https://mlsanity.com/paper/2511.14748/) (2025)
- [Passing the Baton: High Throughput Distributed Disk-Based Vector Search with BatANN](https://mlsanity.com/paper/2512.09331/) (2025)

## Abstract (arXiv)

Approximate Nearest Neighbor Search (ANNS), as the core of vector databases (VectorDBs), has become widely used in modern AI and ML systems, powering applications from information retrieval to bio-informatics. While graph-based ANNS methods achieve high query efficiency, their scalability is constrained by the available host memory. Recent disk-based ANNS approaches mitigate memory usage by offloading data to Solid-State Drives (SSDs). However, they still suffer from issues such as long I/O traversal path, misalignment with storage I/O granularity, and high in-memory indexing overhead, leading to significant I/O latency and ultimately limiting scalability for large-scale vector search. In this paper, we propose PageANN, a disk-based approximate nearest neighbor search (ANNS) framework designed for high performance and scalability. PageANN introduces a page-node graph structure that aligns logical graph nodes with physical SSD pages, thereby shortening I/O traversal paths and reducing I/O operations. Specifically, similar vectors are clustered into page nodes, and a co-designed disk data layout leverages this structure with a merging technique to store only representative vectors and topology information, avoiding unnecessary reads. To further improve efficiency, we design a memory management strategy that combines lightweight indexing with coordinated memory-disk data allocation, maximizing host memory utilization while minimizing query latency and storage overhead. Experimental results show that PageANN significantly outperforms state-of-the-art (SOTA) disk-based ANNS methods, achieving 1.85x-10.83x higher throughput and 51.7%-91.9% lower latency across different datasets and memory budgets, while maintaining comparable high recall accuracy.