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

• URL: http://arxiv.org/abs/2509.25487v2
• Date: Sat, 04 Oct 2025 22:28:46 GMT
• Title: Scalable Disk-Based Approximate Nearest Neighbor Search with Page-Aligned Graph
• Authors: Dingyi Kang, Dongming Jiang, Hanshen Yang, Hang Liu, Bingzhe Li,
• Abstract summary: We propose PageANN, a disk-based approximate nearest neighbor search (ANNS) framework for high performance and scalability.<n>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.
• Score: 3.994346326254537
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• AlayaLaser: Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search [23.738568440013584]
  AlayaLaser is an efficient on-disk graph-based index system for large-scale high-dimensional vector similarity search.<n>AlayaLaser surpasses existing on-disk graph-based index systems but also matches or even exceeds the performance of in-memory index systems.
  arXiv  Detail & Related papers  (2026-02-26T18:48:29Z)
• Aeon: High-Performance Neuro-Symbolic Memory Management for Long-Horizon LLM Agents [0.0]
  Large Language Models (LLMs) are constrained by the quadratic computational cost of self-attention and the "Lost in the Middle" phenomenon.<n>We propose Aeon, a Neuro-Symbolic Cognitive Operating System that redefines memory not as a static store, but as a managed OS resource.
  arXiv  Detail & Related papers  (2026-01-14T15:23:22Z)
• B+ANN: A Fast Billion-Scale Disk-based Nearest-Neighbor Index [3.4720326275852]
  We present a novel disk-based ANN index, B+ANN, to address issues of the HNSW algorithm.<n>It partitions input data into blocks containing semantically similar items, then builds an B+ tree variant to store blocks both in-memory and on disks.<n>It improves both quality (Recall value), and execution performance (Queries per second/QPS) over HNSW.
  arXiv  Detail & Related papers  (2025-11-19T15:50:28Z)
• MemSearcher: Training LLMs to Reason, Search and Manage Memory via End-to-End Reinforcement Learning [73.27233666920618]
  We propose MemSearcher, an agent workflow that iteratively maintains a compact memory and combines the current turn with it.<n>At each turn, MemSearcher fuses the user's question with the memory to generate reasoning traces, perform search actions, and update memory to retain only information essential for solving the task.<n>We introduce multi-context GRPO, an end-to-end RL framework that jointly optimize reasoning, search strategies, and memory management of MemSearcher Agents.
  arXiv  Detail & Related papers  (2025-11-04T18:27:39Z)
• Hierarchical Memory for High-Efficiency Long-Term Reasoning in LLM Agents [19.04968632268433]
  We propose a hierarchical memory architecture for Large Language Model Agents (LLM Agents)<n>Each memory vector is embedded with a positional index encoding pointing to its semantically related sub-memories in the next layer.<n>During the reasoning phase, an index-based routing mechanism enables efficient, layer-by-layer retrieval without performing exhaustive similarity computations.
  arXiv  Detail & Related papers  (2025-07-23T12:45:44Z)
• LEANN: A Low-Storage Vector Index [70.13770593890655]
  LEANN is a storage-efficient approximate nearest neighbor search index optimized for resource-constrained personal devices.<n>Our evaluation shows that LEANN reduces index size to under 5% of the original raw data, achieving up to 50 times smaller storage than standard indexes.
  arXiv  Detail & Related papers  (2025-06-09T22:43:30Z)
• From Single to Multi-Granularity: Toward Long-Term Memory Association and Selection of Conversational Agents [79.87304940020256]
  Large Language Models (LLMs) have been widely adopted in conversational agents.<n>MemGAS is a framework that enhances memory consolidation by constructing multi-granularity association, adaptive selection, and retrieval.<n> Experiments on four long-term memory benchmarks demonstrate that MemGAS outperforms state-of-the-art methods on both question answer and retrieval tasks.
  arXiv  Detail & Related papers  (2025-05-26T06:13:07Z)
• On Storage Neural Network Augmented Approximate Nearest Neighbor Search [1.3654846342364308]
  It is necessary to search for the most similar vectors to a given query vector from the data stored in storage devices, not from that in memory.<n>In this paper, we propose a method to predict the correct clusters by means of a neural network.<n>Compared to state-of-the-art SPANN and an exhaustive method using k-means clustering and linear search, the proposed method achieves 90% recall on SIFT1M with 80% and 58% less data fetched from storage, respectively.
  arXiv  Detail & Related papers  (2025-01-23T06:56:18Z)
• Characterizing the Dilemma of Performance and Index Size in Billion-Scale Vector Search and Breaking It with Second-Tier Memory [14.432536669959218]
  Vector searches on large-scale datasets are critical to modern online services like web search and RAG. We characterize the trade-off of performance and index size in existing SSD-based graph and cluster indexes. We show that vector indexes can achieve optimal performance with orders of magnitude smaller index amplification on a variety of second-tier memory devices.
  arXiv  Detail & Related papers  (2024-05-06T08:38:14Z)
• AiSAQ: All-in-Storage ANNS with Product Quantization for DRAM-free Information Retrieval [1.099532646524593]
  We propose All-in-Storage ANNS with Product Quantization (AiSAQ), which offloads compressed vectors to the SSD index.<n>Our method achieves $sim$10 MB memory usage in query search with billion-scale datasets without critical latency degradation.
  arXiv  Detail & Related papers  (2024-04-09T04:20:27Z)
• Communication-Efficient Graph Neural Networks with Probabilistic Neighborhood Expansion Analysis and Caching [59.8522166385372]
  Training and inference with graph neural networks (GNNs) on massive graphs has been actively studied since the inception of GNNs. This paper is concerned with minibatch training and inference with GNNs that employ node-wise sampling in distributed settings. We present SALIENT++, which extends the prior state-of-the-art SALIENT system to work with partitioned feature data.
  arXiv  Detail & Related papers  (2023-05-04T21:04:01Z)
• NumS: Scalable Array Programming for the Cloud [82.827921577004]
  We present NumS, an array programming library which optimize NumPy-like expressions on task-based distributed systems. This is achieved through a novel scheduler called Load Simulated Hierarchical Scheduling (LSHS) We show that LSHS enhances performance on Ray by decreasing network load by a factor of 2x, requiring 4x less memory, and reducing execution time by 10x on the logistic regression problem.
  arXiv  Detail & Related papers  (2022-06-28T20:13:40Z)
• Generalizing Few-Shot NAS with Gradient Matching [165.5690495295074]
  One-Shot methods train one supernet to approximate the performance of every architecture in the search space via weight-sharing. Few-Shot NAS reduces the level of weight-sharing by splitting the One-Shot supernet into multiple separated sub-supernets. It significantly outperforms its Few-Shot counterparts while surpassing previous comparable methods in terms of the accuracy of derived architectures.
  arXiv  Detail & Related papers  (2022-03-29T03:06:16Z)
• ROME: Robustifying Memory-Efficient NAS via Topology Disentanglement and Gradient Accumulation [106.04777600352743]
  Differentiable architecture search (DARTS) is largely hindered by its substantial memory cost since the entire supernet resides in the memory. The single-path DARTS comes in, which only chooses a single-path submodel at each step. While being memory-friendly, it also comes with low computational costs. We propose a new algorithm called RObustifying Memory-Efficient NAS (ROME) to give a cure.
  arXiv  Detail & Related papers  (2020-11-23T06:34:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.