Approximate Nearest Neighbor Search

Follow this topic Ask about this topic

Approximate nearest neighbor search finds vectors similar to a query without comparing it against every item, making large-scale embedding retrieval practical. Common approaches include graph indexes such as HNSW and DiskANN, inverted-file indexes with product quantization, locality-sensitive hashing, and learned routing; many compress vectors or rerank a shortlist to save time and memory. Methods are compared using recall@k, query speed, memory, and index-building cost on embedding benchmarks and workloads such as billion-vector, filtered, and streaming search. A central challenge is balancing these costs as data changes, while ensuring that exact-neighbor overlap reflects useful semantic retrieval.

Latest papers

43 papers3 papers in the last four weeks, down 50% on the four weeks before. 0.0% of all new papers.

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data
Apr 8, 2026Mingyu Yang, Wentao Li, Wei WangHybrid Retrieval Graph-Based Retrieval
HKUST (GZ) & HKUST China · University of Leicester United Kingdom
An In-Depth Study of Filter-Agnostic Vector Search on a PostgreSQL Database System: [Experiments and Analysis]
Mar 24, 2026Duo Lu, Helena Caminal, Manos Chatzakis +4Approximate Nearest Neighbor Search Graph-Based Retrieval
Brown University, USA · Google, USA · Université Paris Cité, LIPADE, France +2
GEM: A Native Graph-based Index for Multi-Vector Retrieval
Mar 20, 2026Yao Tian, Zhoujin Tian, Xi Zhao +2Multi-Vector Retrieval Graph-Based Retrieval
The Hong Kong University of Science and Technology, Hong Kong, China · Hong Kong Generative AI Research & Development Center, Hong Kong, China
Efficient K-generalizable Learned Search
Mar 6, 2026Yifan Peng, Jiafei Fan, Xingda Wei +7Inference-Time Search Graph-Based Retrieval
Shanghai Jiao Tong University · Boston University · Alibaba Group
Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach
Mar 1, 2026Kejing Lu, Zhenpeng Pan, Jianbin Qin +2Approximate Nearest Neighbor Search Graph-Based Retrieval
University of Yamanashi · Beijing Institute of Technology, Zhuhai · Shenzhen University +2
Pancake: Hierarchical Memory System for Multi-Agent LLM Serving
Feb 25, 2026Zhengding Hu, Zaifeng Pan, Prabhleen Kaur +6Memory Management for LLM Agents Agent Memory Management
Computer Science and Engineering, University of California, San Diego
SubQuad: Near-Quadratic-Free Structure Inference with Distribution-Balanced Objectives in Adaptive Receptor framework
Feb 19, 2026Rong Fu, Zijian Zhang, Kun Liu +3Clustering Approximate Nearest Neighbor Search
Independent Researcher
Neighborhood Stability as a Measure of Nearest Neighbor Searchability
Feb 18, 2026Thomas Vecchiato, Sebastian BruchApproximate Nearest Neighbor Search Clustering
University of Copenhagen, Copenhagen, Denmark · Northeastern University, Boston, MA, USA
Rethinking ANN-based Retrieval: Multifaceted Learnable Index for Large-scale Recommendation System
Feb 18, 2026Jiang Zhang, Yubo Wang, Wei Chang +14Recommender Systems Approximate Nearest Neighbor Search
Meta Platforms, Inc.
Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
Oct 27, 2025Ved Danait, Srijan Das, Sujoy BhoreRandomized Sketching Kernel Density Estimation
Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. · Department of Computer Science & Engineering and Centre for Machine Intelligence & Data Science (CMINDS), Indian Institute of Technology Bombay, Mumbai, India.
Panorama: Fast-Track Nearest Neighbors
Oct 1, 2025Vansh Ramani, Alexis Schlomer, Akash Nayar +3Product Quantization Approximate Nearest Neighbor Search
IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi +1
CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search
Aug 4, 2025Xiaoya Li, Albert Wang, Guoyin Wang +2Learning-Augmented Algorithms Approximate Nearest Neighbor Search
DeepReinforce Team
The kernel of graph indices for vector search
Jun 25, 2025Mariano Tepper, Ted WillkeGraph-Based Retrieval Kernel Methods
IBM WatsonX

Apr 8, 2026J/K move · Enter open · S save

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data

Mingyu Yang, Wentao Li, Wei Wang

HKUST (GZ) & HKUST China · University of Leicester United Kingdom

Hybrid Retrieval Graph-Based Retrieval Approximate Nearest Neighbor Search

Open paper AskPDF arXiv

Hybrid queries combining high-dimensional vector similarity search with spatio-temporal filters are increasingly critical for modern retrieval-augmented generation (RAG) systems. Existing systems typically handle these workloads by nesting vector indices within low-dimensional spatial structures, such as R-trees. However, this decoupled architecture fragments the vector space, forcing the query engine to invoke multiple disjoint sub-indices per query. This fragmentation destroys graph routing connectivity, incurs severe traversal overhead, and struggles to optimize for complex spatial boundaries. In this paper, we propose CubeGraph, a novel indexing framework designed to natively integrate vector search with arbitrary spatial constraints. CubeGraph partitions the spatial domain using a hierarchical grid, maintaining modular vector graphs within each cell. During query execution, CubeGraph dynamically stitches together adjacent cube-level indices on the fly whenever their spatial cells intersect with the query filter. This dynamic graph integration restores global connectivity, enabling a unified, single-pass nearest-neighbor traversal that eliminates the overhead of fragmented sub-index invocations. Extensive evaluations on real-world datasets demonstrate that CubeGraph significantly outperforms state-of-the-art baselines, offering superior query execution performance, scalability, and flexibility for complex hybrid workloads.