Parallel k nearest neighbor graph construction using tree-based data structures

Abstract

Construction of a nearest neighbor graph is often a neces- sary step in many machine learning applications. However, constructing such a graph is computationally expensive, es- pecially when the data is high dimensional. Python's open source machine learning library Scikit-learn uses k-d trees and ball trees to implement nearest neighbor graph construc- tion. However, this implementation is ine cient for large datasets. In this work, we focus on exploiting these under- lying tree-based data structures to optimize parallel execu- tion of the nearest neighbor algorithm. We present parallel implementations of nearest neighbor graph construction us- ing such tree structures, with parallelism provided by the OpenMP and the Galois framework. We empirically show that our parallel and exact approach is e cient as well as scalable, compared to the Scikit-learn implementation. We present the rst implementation of k-d trees and ball trees using Galois. Our results show that k-d trees are faster when the number of dimensions is small (2d N); ball trees on the other hand scale well with the number of dimensions. Our implementation of ball trees in Galois has almost linear speedup on a number of datasets irrespective of the size and dimensionality of the data.