On The Merge Of K-nn Graph

Abstract

k-nearest neighbor graph is a fundamental data structure in many disciplines such as information retrieval, data-mining, pattern recognition, and machine learning, etc. In the literature, considerable research has been focusing on how to efficiently build an approximate k-nearest neighbor graph (k-NN graph) for a fixed dataset. Unfortunately, a closely related issue of how to merge two existing k-NN graphs has been overlooked. In this paper, we address the issue of k-NN graph merging in two different scenarios. In the first scenario, a symmetric merge algorithm is proposed to combine two approximate k-NN graphs. The algorithm facilitates large-scale processing by the efficient merging of k-NN graphs that are produced in parallel. In the second scenario, a joint merge algorithm is proposed to expand an existing k-NN graph with a raw dataset. The algorithm enables the incremental construction of a hierarchical approximate k-NN graph. Superior performance is attained when leveraging the h

Stats

• citations4
• S2 citations—
• github stars0
• HF likes0
• heat score5.24
• arxiv keyzhao2019on

Related papers

• Approximate K-nn Graph Construction: A Generic Online Approach (2018)11.08
• EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00
• Revisiting \(k\)-nearest Neighbor Graph Construction On High-dimensional Data : Experiments And Analyses (2021)0.00
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
• Minimax Optimal Algorithms With Fixed-\(k\)-nearest Neighbors (2022)0.00
• On Convergence Of Nearest Neighbor Classifiers Over Feature Transformations (2020)0.00
• Graph-based Nearest Neighbor Search: From Practice To Theory (2019)0.00