Learning Cluster Representatives for Approximate Nearest Neighbor Search
Developing increasingly efficient and accurate algorithms for approximate nearest neighbor search is a paramount goal in modern information retrieval. A primary approach to addressing this question is clustering, which involves partitioning the dataset into distinct groups, with each group characterized by a representative data point. By this method, retrieving the top-k data points for a query requires identifying the most relevant clusters based on their representatives -- a routing step -- and then conducting a nearest neighbor search within these clusters only, drastically reducing the search space. The objective of this thesis is not only to provide a comprehensive explanation of clustering-based approximate nearest neighbor search but also to introduce and delve into every aspect of our novel state-of-the-art method, which originated from a natural observation: The routing function solves a ranking problem, making the function amenable to learning-to-rank. The development of this intuition and applying it to maximum inner product search has led us to demonstrate that learning cluster representatives using a simple linear function significantly boosts the accuracy of clustering-based approximate nearest neighbor search.
Code (1)
Tasks
ClusteringInformation RetrievalLearning-To-RankSimilar Papers 제목 키워드 기반
Refining a -nearest neighbor graph for a computationally efficient spectral clustering
Spectral clustering became a popular choice for data clustering for its ability of uncovering clusters of different shapes. However, it is not always preferable over other clustering methods due to its computational dema…
ClusteringComputational EfficiencyGraph ClusteringGraph Embedding+3Refining a $k$-nearest neighbor graph for a computationally efficient spectral clustering
Spectral clustering became a popular choice for data clustering for its ability of uncovering clusters of different shapes. However, it is not always preferable over other clustering methods due to its computational dema…
ClusteringComputational EfficiencyGraph ClusteringGraph Embedding+3Neighborhood Stability as a Measure of Nearest Neighbor Searchability
Clustering-based Approximate Nearest Neighbor Search (ANNS) organizes a set of points into partitions, and searches only a few of them to find the nearest neighbors of a query. Despite its popularity, there are virtually…
A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Search
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…
ClusteringInformation RetrievalLearning-To-RankScalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search
For very large values of $k$, we consider methods for fast $k$-means clustering of massive datasets with $10^7\sim10^9$ points in high-dimensions ($d\geq100$). All current practical methods for this problem have runtimes…