A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913252206706688 |
|---|---|
| author | Elkin, Yury Kurlin, Vitaliy |
| author_facet | Elkin, Yury Kurlin, Vitaliy |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_15478 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree Elkin, Yury Kurlin, Vitaliy Computational Geometry Data Structures and Algorithms 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. |
| title | A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2111.15478 |