Publication Type

Journal Article

Version

publishedVersion

Publication Date

12-2022

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 hierarchy for NN search of various data types, dimensionality, and distance measures.

Keywords

k-nearest neighbor graph, nearest neighbor search, high-dimensional, k-NN graph merge

Discipline

Artificial Intelligence and Robotics | Databases and Information Systems

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

IEEE Transactions on Big Data

Volume

8

Issue

6

First Page

1496

Last Page

1510

ISSN

2332-7790

Identifier

10.1109/TBDATA.2021.3101517

Publisher

Institute of Electrical and Electronics Engineers

Comments

Cited by: 3

Additional URL

https://doi.org/10.1109/TBDATA.2021.3101517

Download

Share

COinS