Given a vector dataset$\mathcal{X}$, a query vector$\vec{x}_{q}$, graph-based Approximate Nearest Neighbor Search (ANNS) aims to build a proximity graph (PG) as an index of$\mathcal{X}$and approximately return vectors with minimum distances to$\vec{x}_{q}$by searching over the PG index. It has been widely recognized that graph-based ANNS is effective and efficient, however, it suffers from the large-scale$\mathcal{X}$because of the entire PG is too large to fit into the memory. To solve this, Product Quantization (PQ) integrated graph-based ANNS is proposed to reduce the memory usage, by replacing a large PG with original vectors by the one with smaller compact codes of quantized vectors. Existing PQ methods do not consider the important routing features of PG, thus resulting in low-quality quantized vectors that significantly affect the ANNS's effectiveness. In this paper, we present an end-to-end Routing-guided learned Product Quantization (RPQ) for graph-based ANNS, which easily can be adaptive to existing popular PGs. Specifically, RPQ consists of (1) a differentiable quantizer used to make the standard discrete PQ differentiable to suit for back-propagation of end-to-end learning, (2) a sampling-based feature extractor used to extract neighborhood and routing features of a PG by using the quantized vectors, and (3) a multi-feature joint training module with two types of feature-aware losses to continuously optimize the differentiable quantizer. As a result, the inherent features of a specific PG would be embedded into the learned PQ, thus generating high-quality quantized vectors that facilitate the graph-based ANNS's effectiveness and efficiency. Moreover, we integrate our RPQ with the state-of-the-art DiskANN and existing PGs to improve their performance. Comprehensive experimental studies on real-world large-scale datasets (scale from 1M to 1B) demonstrate RPQ's superiority.

This paper introduces an efficient and robust framework for hybrid query (HQ) processing, which combines approximate nearest neighbor search (ANNS) with attribute constraint. HQ aims to find objects that are similar to a feature vector and match some structured attributes. Existing methods handle ANNS and attribute filtering separately, leading to inefficiency and inaccuracy. Our framework, called native hybrid query (NHQ), builds a composite index based on proximity graph (PG) and applies joint pruning for HQ. We can easily adapt existing PGs to this framework for efficient HQ processing. We also propose two new navigable PGs (NPGs) with optimized edge selection and routing, which improve the overall ANNS performance. We implement five HQ methods based on the proposed NPGs and existing PGs in NHQ, and show that they outperform the state-of-the-art methods on 10 real-world datasets (up to 315$\times$ faster with the same accuracy).

Approximate nearest neighbor search (ANNS) constitutes an important operation in a multitude of applications, including recommendation systems, information retrieval, and pattern recognition. In the past decade, graph-based ANNS algorithms have been the leading paradigm in this domain, with dozens of graph-based ANNS algorithms proposed. Such algorithms aim to provide effective, efficient solutions for retrieving the nearest neighbors for a given query. Nevertheless, these efforts focus on developing and optimizing algorithms with different approaches, so there is a real need for a comprehensive survey about the approaches' relative performance, strengths, and pitfalls. Thus here we provide a thorough comparative analysis and experimental evaluation of 13 representative graph-based ANNS algorithms via a new taxonomy and fine-grained pipeline. We compared each algorithm in a uniform test environment on eight real-world datasets and 12 synthetic datasets with varying sizes and characteristics. Our study yields novel discoveries, offerings several useful principles to improve algorithms, thus designing an optimized method that outperforms the state-of-the-art algorithms. This effort also helped us pinpoint algorithms' working portions, along with rule-of-thumb recommendations about promising research directions and suitable algorithms for practitioners in different fields.