Approximate K-nn Graph Construction: A Generic Online Approach

Abstract

Nearest neighbor search and k-nearest neighbor graph construction are two fundamental issues arise from many disciplines such as multimedia information retrieval, data-mining and machine learning. They become more and more imminent given the big data emerge in various fields in recent years. In this paper, a simple but effective solution both for approximate k-nearest neighbor search and approximate k-nearest neighbor graph construction is presented. These two issues are addressed jointly in our solution. On the one hand, the approximate k-nearest neighbor graph construction is treated as a search task. Each sample along with its k-nearest neighbors are joined into the k-nearest neighbor graph by performing the nearest neighbor search sequentially on the graph under construction. On the other hand, the built k-nearest neighbor graph is used to support k-nearest neighbor search. Since the graph is built online, the dynamic update on the graph, which is not possible from most of the exis

Stats

• citations29
• S2 citations—
• github stars0
• HF likes0
• heat score11.08
• arxiv keyzhao2018approximate

Related papers

• EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00
• On The Merge Of K-nn Graph (2019)5.24
• Relative Nn-descent: A Fast Index Construction For Graph-based Approximate Nearest Neighbor Search (2023)8.09
• Revisiting \(k\)-nearest Neighbor Graph Construction On High-dimensional Data : Experiments And Analyses (2021)0.00
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
• Revisiting The Index Construction Of Proximity Graph-based Approximate Nearest Neighbor Search (2024)7.16
• Approximate Nearest Neighbour Search On Dynamic Datasets: An Investigation (2024)0.00
• FINGER: Fast Inference For Graph-based Approximate Nearest Neighbor Search (2022)10.74