A Learning-to-rank Formulation Of Clustering-based Approximate Nearest Neighbor Search

Abstract

A critical piece of the modern information retrieval puzzle is approximate nearest neighbor search. Its objective is to return a set of \(k\) data points that are closest to a query point, with its accuracy measured by the proportion of exact nearest neighbors captured in the returned set. One popular approach to this question is clustering: The indexing algorithm partitions data points into non-overlapping subsets and represents each partition by a point such as its centroid. The query processing algorithm first identifies the nearest clusters -- a process known as routing -- then performs a nearest neighbor search over those clusters only. In this work, we make a simple observation: The routing function solves a ranking problem. Its quality can therefore be assessed with a ranking metric, making the function amenable to learning-to-rank. Interestingly, ground-truth is often freely available: Given a query distribution in a top-\(k\) configuration, the ground-truth is the set of clust

Stats

• citations3
• S2 citations—
• github stars0
• HF likes0
• heat score4.52
• arxiv keyvecchiato2024a

Related papers

• Learning To Index For Nearest Neighbor Search (2018)10.35
• Optimistic Query Routing In Clustering-based Approximate Maximum Inner Product Search (2024)0.00
• Associative Memories To Accelerate Approximate Nearest Neighbor Search (2016)6.34
• A Multilabel Classification Framework For Approximate Nearest Neighbor Search (2019)0.00
• Towards Non-parametric Learning To Rank (2018)0.00
• Lorann: Low-rank Matrix Factorization For Approximate Nearest Neighbor Search (2024)2.26
• Refining A \(k\)-nearest Neighbor Graph For A Computationally Efficient Spectral Clustering (2023)12.25
• Adaptive Estimation For Approximate K-nearest-neighbor Computations (2019)0.00