On the Merge of k-NN Graph
Wan‐Lei Zhao, Hui Wang, Peng-Cheng Lin, Chong‐Wah Ngo · IEEE Transactions on Big Data · 2021
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 approximatek-nearest neighbor graph (k-NN graph) for a fixed dataset. Unfortunately, a closely related issue of how to merge two existingk-NN graphs has been overlooked. In this paper, we address the issue ofk-NN graph merging in two different scenarios. In the first scenario, a symmetric merge algorithm is proposed to combine two approximatek-NN graphs. The algorithm facilitates large-scale processing by the efficient merging ofk-NN graphs that are produced in parallel. In the second scenario, a joint merge algorithm is proposed to expand an existingk-NN graph with a raw dataset. The algorithm enables the incremental construction of a hierarchical approximatek-NN graph. Superior performance is attained when leveraging the hierarchy for NN search of various data types, dimensionality, and distance measures.