Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection

Nearest neighbor graphs are widely used in data mining and machine learning. A brute-force method to compute the exact kNN graph takes Θ(dn2) time for n data points in the d dimensional Euclidean s...