Parallel k-Nearest Neighbor Algorithm

Overview

It is c++ parallel implementation of the k-nearest neighbor algorithm using async c++ threads. The data are evenly split between n threads that each thread computes the k-nearest neighbor for its part of data.

Input

A input file test_big.txt contains coordinates of 9271 3D-points in the world space.

Output

For each input point, find its k-nearest neighbors indexes.

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