Parallel k-Nearest Neighbors Algorithm

Overview

C++ parallel implementation of the k-nearest neighbors algorithm using async c++ threads. The data are evenly split among n threads; each thread computes the k-nearest neighbors for its portion of the data.

Input

An input file test_big.txt containing 9271 3D points.

Output

For each input point, the indices of its k-nearest neighbors.

Build and run

To build use Makefile (C++11 needed)

make
make clean
./main <input_points.txt> <result.txt>

For instance,

./main ./input/test_big.txt ./out/out_big.txt

Benchmarks

Intel(R) Xeon(R) CPU 2.00GHz

For 9271 3D-points and k=5

Threads	Time, milisec
1	45979
2	24430
3	18370
4	14112
5	13207

License

MIT