Get our free extension to see links to code for papers anywhere online!Free add-on: code for papers everywhere!Free add-on: See code for papers anywhere!

Add to Chrome

Add to Firefox

Add to Edge

Lirong Xue

Achieving the time of $1$-NN, but the accuracy of $k$-NN

Dec 22, 2017
Lirong Xue, Samory Kpotufe

Figure 1 for Achieving the time of $1$-NN, but the accuracy of $k$-NN

Figure 2 for Achieving the time of $1$-NN, but the accuracy of $k$-NN

Figure 3 for Achieving the time of $1$-NN, but the accuracy of $k$-NN

Figure 4 for Achieving the time of $1$-NN, but the accuracy of $k$-NN

We propose a simple approach which, given distributed computing resources, can nearly achieve the accuracy of $k$-NN prediction, while matching (or improving) the faster prediction time of $1$-NN. The approach consists of aggregating denoised $1$-NN predictors over a small number of distributed subsamples. We show, both theoretically and experimentally, that small subsample sizes suffice to attain similar performance as $k$-NN, without sacrificing the computational efficiency of $1$-NN.

Via

Access Paper or Ask Questions