| Autor: |
Alejandro Murua, Nicolas Wicker |
| Jazyk: |
angličtina |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
Austrian Journal of Statistics, Vol 49, Iss 2 (2020) |
| Druh dokumentu: |
article |
| ISSN: |
1026-597X |
| DOI: |
10.17713/ajs.v49i2.907 |
| Popis: |
We introduce a fast method to estimate the complete-data set of k-nearest-neighbors.This is equivalent to finding an estimate of the k-nearest-neighbor graph of the data. The method relies on random normal projections. The k-nearest-neighbors are estimated by sorting points in a number of random lines. For very large datasets, the method is quasi-linear in the data size. As an application, we show that the intrinsic dimension of a manifold can be reliably estimated from the estimated set of k-nearest-neighbors in time about two orders of magnitude faster than when using the exact set of k-nearest-neighbors. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
