kNN-Borůvka-GPU: A Fast and Scalable MST Construction from kNN Graphs on GPU

Computation of the minimum spanning tree (MST) is a common task in numerous fields of research, such as pattern recognition, computer vision, network design (telephone, electrical, hydraulic, cable TV, computer, road networks etc.), VLSI layout, to name a few. However, for a large-scale dataset when the graphs are complete, classical MST computation algorithms become unsuitable on general purpose computers. Interestingly, in such a case the

k

-nearest neighbor (

k

NN) structure can provide an efficient solution to this problem. Only a few attempts were found in the literature that focus on solving the problem using the

k

NNs. This paper briefs the state-of-the-art strategies for the MST problem and a fast and scalable solution combining the classical Borůvka’s MST algorithm and the

k

NN graph structure. The proposed algorithm is implemented for CUDA enabled GPUs

k

NN-Borůvka-GPU), but the basic approach is simple and adaptable to other available architectures. Speed-ups of 30-40 times compared with CPU implementation was observed for several large-scale synthetic and real world data sets.