Revisiting \(k\)-nearest Neighbor Graph Construction On High-dimensional Data : Experiments And Analyses

Abstract

The \(k\)-nearest neighbor graph (KNNG) on high-dimensional data is a data structure widely used in many applications such as similarity search, dimension reduction and clustering. Due to its increasing popularity, several methods under the same framework have been proposed in the past decade. This framework contains two steps, i.e. building an initial KNNG (denoted as \texttt\{INIT\}) and then refining it by neighborhood propagation (denoted as \texttt\{NBPG\}). However, there remain several questions to be answered. First, it lacks a comprehensive experimental comparison among representative solutions in the literature. Second, some recently proposed indexing structures, e.g., SW and HNSW, have not been used or tested for building an initial KNNG. Third, the relationship between the data property and the effectiveness of \texttt\{NBPG\} is still not clear. To address these issues, we comprehensively compare the representative approaches on real-world high-dimensional data sets to pro

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyyingfan2021revisiting

Related papers

• Revisiting The Index Construction Of Proximity Graph-based Approximate Nearest Neighbor Search (2024)7.16
• Approximate K-nn Graph Construction: A Generic Online Approach (2018)11.08
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00
• On The Merge Of K-nn Graph (2019)5.24
• Hd-index: Pushing The Scalability-accuracy Boundary For Approximate Knn Search In High-dimensional Spaces (2018)14.02
• Navigable Graphs For High-dimensional Nearest Neighbor Search: Constructions And Limits (2024)4.52
• Optimization Of Indexing Based On K-nearest Neighbor Graph For Proximity Search In High-dimensional Data (2018)0.00
• Leveraging Reinforcement Learning For Evaluating Robustness Of KNN Search Algorithms (2021)0.00