Approximate k-NN graph construction: A generic online approach

Nearest neighbor search and k-nearest neighbor graph construction are two fundamental issues that 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. I...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHAO, Wan-Lei, WANG, Hui, NGO, Chong-wah
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2022
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/7244
https://ink.library.smu.edu.sg/context/sis_research/article/8247/viewcontent/Approximate_k_NN_Graph_Construction.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-8247
record_format dspace
spelling sg-smu-ink.sis_research-82472022-09-02T06:17:52Z Approximate k-NN graph construction: A generic online approach ZHAO, Wan-Lei WANG, Hui NGO, Chong-wah Nearest neighbor search and k-nearest neighbor graph construction are two fundamental issues that 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 one hand, the approximate k-nearest neighbor graph construction is treated as a search task. Each sample along with its k-nearest neighbors is 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 for most of the existing solutions, is supported. This solution is feasible for various distance measures. Its effectiveness both as k-nearest neighbor construction and k-nearest neighbor search approaches is verified across different types of data in different scales, various dimensions, and under different metrics. 2022-01-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/7244 info:doi/10.1109/TMM.2021.3073811 https://ink.library.smu.edu.sg/context/sis_research/article/8247/viewcontent/Approximate_k_NN_Graph_Construction.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Measurement Quantization (signal) Indexing Task analysis Nearest neighbor methods Approximation algorithms Time complexity k-nearest neighbor graph nearest neighbor search high-dimensional NN-descent Databases and Information Systems
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Measurement
Quantization (signal)
Indexing
Task analysis
Nearest neighbor methods
Approximation algorithms
Time complexity
k-nearest neighbor graph
nearest neighbor search
high-dimensional
NN-descent
Databases and Information Systems
spellingShingle Measurement
Quantization (signal)
Indexing
Task analysis
Nearest neighbor methods
Approximation algorithms
Time complexity
k-nearest neighbor graph
nearest neighbor search
high-dimensional
NN-descent
Databases and Information Systems
ZHAO, Wan-Lei
WANG, Hui
NGO, Chong-wah
Approximate k-NN graph construction: A generic online approach
description Nearest neighbor search and k-nearest neighbor graph construction are two fundamental issues that 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 one hand, the approximate k-nearest neighbor graph construction is treated as a search task. Each sample along with its k-nearest neighbors is 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 for most of the existing solutions, is supported. This solution is feasible for various distance measures. Its effectiveness both as k-nearest neighbor construction and k-nearest neighbor search approaches is verified across different types of data in different scales, various dimensions, and under different metrics.
format text
author ZHAO, Wan-Lei
WANG, Hui
NGO, Chong-wah
author_facet ZHAO, Wan-Lei
WANG, Hui
NGO, Chong-wah
author_sort ZHAO, Wan-Lei
title Approximate k-NN graph construction: A generic online approach
title_short Approximate k-NN graph construction: A generic online approach
title_full Approximate k-NN graph construction: A generic online approach
title_fullStr Approximate k-NN graph construction: A generic online approach
title_full_unstemmed Approximate k-NN graph construction: A generic online approach
title_sort approximate k-nn graph construction: a generic online approach
publisher Institutional Knowledge at Singapore Management University
publishDate 2022
url https://ink.library.smu.edu.sg/sis_research/7244
https://ink.library.smu.edu.sg/context/sis_research/article/8247/viewcontent/Approximate_k_NN_Graph_Construction.pdf
_version_ 1770576289866973184