通过页对齐图结构，大幅提升磁盘向量搜索的效率与可扩展性。
Scalable Disk-Based Approximate Nearest Neighbor Search with Page-Aligned Graph
- 用页对齐的图节点结构，缩短I/O访问路径，减少读取次数。
- 在不同内存预算下，吞吐量提升1.85至10.83倍，延迟降低51.7%~91.9%。
- 适合大规模向量数据库应用，尤其适用于内存受限场景。
近似最近邻搜索（ANNS）作为向量数据库的核心，广泛应用于现代AI与机器学习系统，涵盖信息检索到生物信息学等领域。尽管基于图的ANNS方法查询效率高，但其可扩展性受限于主机内存。近期的磁盘基ANNS方法通过将数据移至固态硬盘（SSD）缓解内存压力，但仍面临长I/O遍历路径、与存储I/O粒度不匹配及高内存索引开销等问题，导致显著的I/O延迟，限制了大规模向量搜索的可扩展性。本文提出PageANN，一种面向高性能和可扩展性的磁盘基近似最近邻搜索框架。PageANN引入页-节点图结构，使逻辑图节点与物理SSD页对齐，从而缩短I/O遍历路径并减少操作次数。具体而言，相似向量被聚类为页节点，并结合协同设计的磁盘数据布局与合并技术，仅存储代表性向量和拓扑信息，避免冗余读取。为进一步提升效率，设计了一种轻量级索引与协调式内存-磁盘数据分配相结合的内存管理策略，最大化主机内存利用率，同时最小化查询延迟与存储开销。实验表明，PageANN显著优于现有最先进（SOTA）的磁盘基ANNS方法，在不同数据集和内存预算下，吞吐量提升1.85至10.83倍，延迟降低51.7%~91.9%，同时保持相近的高召回率。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。