Elkin, Yury and Kurlin, Vitaliy 
ORCID: 0000-0001-5328-5351
(2021)
A new near-linear time algorithm for k-nearest neighbor search using a
compressed cover tree.
[Preprint]
|
Text
2111.15478v2.pdf - Submitted version Download (826kB) | 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 \in 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: | Preprint |
|---|---|
| Additional Information: | Accepted to ICML 2023 |
| Uncontrolled Keywords: | cs.CG, cs.CG, cs.DS |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 24 Jan 2022 08:23 |
| Last Modified: | 15 Mar 2024 12:38 |
| DOI: | 10.48550/arxiv.2111.15478 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3147440 |
Dimensions
Dimensions
