PANNS: Enhancing Graph-based Approximate Nearest Neighbor Search through Recency-aware Construction and Parameterized Search

Abstract

Approximate Nearest-Neighbor Search (ANNS) has become the standard querying method in vector databases, especially with the recent surge in large-scale, high-dimensional data driven by LLM-based applications. Recently, graph-based ANNS has shown improved throughput by constructing a graph from the dataset, with edges representing the distances between data points, and using best-first or beam search algorithms for query evaluation.

This work highlights that key aspects of the design space for both graph construction and search in graph-based ANNS remain under-explored. Specifically, the construction phase often neglects the potential temporal correlation between input queries and their results, while the search phase lacks a thorough exploration of beam search parameterization. To address these gaps, we present PANNS, a system that embeds temporal information in the proximity graph construction to capture query-result correlations. Moreover, it introduces a fully parameterized beam search algorithm, enabling extensive performance optimization. PANNS achieves up to a 3.7× improvement in query throughput over state-of-the-art graph-based ANNS methods, while maintaining equivalent recall levels. Furthermore, it reduces graph size by up to 30% without degrading query quality.