K-nearest Neighbor Search by Random Projection Forests

2018-12-31 · Donghui Yan, Yingjie Wang, Jin Wang, Honggang Wang, Zhenpeng Li

K-nearest neighbor (kNN) search has wide applications in many areas, including data mining, machine learning, statistics and many applied domains. Inspired by the success of ensemble methods and the flexibility of tree-based methodology, we propose random projection forests (rpForests), for kNN search. rpForests finds kNNs by aggregating results from an ensemble of random projection trees with each constructed recursively through a series of carefully chosen random projections. rpForests achieves a remarkable accuracy in terms of fast decay in the missing rate of kNNs and that of discrepancy in the kNN distances. rpForests has a very low computational complexity. The ensemble nature of rpForests makes it easily run in parallel on multicore or clustered computers; the running time is expected to be nearly inversely proportional to the number of cores or machines. We give theoretical insights by showing the exponential decay of the probability that neighboring points would be separated by ensemble random projection trees when the ensemble size increases. Our theory can be used to refine the choice of random projections in the growth of trees, and experiments show that the effect is remarkable.

📄 PDF Abstract BibTeX arXiv:1812.11689

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

Exponential Decay Exponential Decay is a learning rate schedule where we decay the learning rate with more iterations using an exponential function: $$ \text{lr} =…

Improved nearest neighbor search using auxiliary information and priority functions

2018-07-01 · ICML 2018 7 · Omid Keivani, Kaushik Sinha

Nearest neighbor search using random projection trees has recently been shown to achieve superior performance, in terms of better accuracy while retrieving less number of data points, compared to locality sensitive …

The Effect of Points Dispersion on the k-nn Search in Random Projection Forests

2022-08-01 · IEEE Access 2022 8 · Mashaan Alshammari, John Stavrakakis, Adel F. Ahmed, Masahiro Takatsuka

Partitioning trees are efficient data structures for k -nearest neighbor search. Machine learning libraries commonly use a special type of partitioning trees called kd -trees to perform k -nn search. Unfortunately, kd -t…

Quantization

The Effect of Points Dispersion on the $k$-nn Search in Random Projection Forests

2023-02-25 · Mashaan Alshammari, John Stavrakakis, Adel F. Ahmed, Masahiro Takatsuka

Partitioning trees are efficient data structures for $k$-nearest neighbor search. Machine learning libraries commonly use a special type of partitioning trees called $k$d-trees to perform $k$-nn search. Unfortunately, $k…

Instance Search Quantization Vector Quantization (k-means problem)

When do random forests fail?

2018-12-01 · NeurIPS 2018 12 · Cheng Tang, Damien Garreau, Ulrike Von Luxburg

Random forests are learning algorithms that build large collections of random trees and make predictions by averaging the individual tree predictions. In this paper, we consider various tree constructions and examine how…

An algorithm for L1 nearest neighbor search via monotonic embedding

2016-12-01 · NeurIPS 2016 12 · Xinan Wang, Sanjoy Dasgupta

Fast algorithms for nearest neighbor (NN) search have in large part focused on L2 distance. Here we develop an approach for L1 distance that begins with an explicit and exact embedding of the points into L2. We show how …