A New Near-linear Time Algorithm For k-Nearest Neighbor Search Using a Compressed Cover Tree

Elkin, Y and Kurlin, V ORCID: 0000-0001-5328-5351 (2023) A New Near-linear Time Algorithm For k-Nearest Neighbor Search Using a Compressed Cover Tree. In: International Conference on Machine Learning.

Text ICML2023Knn_final.pdf - Author Accepted Manuscript Download (842kB) | Preview

Abstract

Given a reference set R of n points and a query set Q of m points in a metric space, this paper studies an important problem of finding k-nearest neighbors of every point q ∈ Q in the set R in a near-linear time. In the paper at ICML 2006, Beygelzimer, Kakade, and Langford introduced a cover tree on R and attempted to prove that this tree can be built in O(n log n) time while the nearest neighbor search can be done in O(n log m) time with a hidden dimensionality factor. This paper fills a substantial gap in the past proofs of time complexity by defining a simpler compressed cover tree on the reference set R. The first new algorithm constructs a compressed cover tree in O(n log n) time. The second new algorithm finds all k-nearest neighbors of all points from Q using a compressed cover tree in time O(m(k + log n) log k) with a hidden dimensionality factor depending on point distributions of the given sets R, Q but not on their sizes.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	06 Jun 2023 09:46
Last Modified:	22 Nov 2023 10:29
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3170841