The Visualization of Large Graphs Accelerated by the Parallel Nearest Neighbors Algorithm
Vojtěch Uher, Petr Gajdoš, Václav Snåšel · 2016
The search of k-nearest neighbors (K-NN) is a very common task. The K-NN is utilized in many algorithms and scientific areas like clustering, classification, machine learning, N-body simulation, triangulation, image processing and/or video processing. However, the naive implementation of the K-NN is very slow. There are many novel algorithms for the K-NN search, but they are usually based on the hierarchical clustering. The parallelization of those algorithms is a little bit tricky task. This paper primarily presents a novel parallel method for searching the k-nearest neighbors. An appropriate clustering of a sparse space based on the regular grid and the parallel search of the K-NN using the precomputed clusters are introduced. The whole method is designed for the parallel GPU computation and it is implemented on the CUDA architecture. The presented K-NN is utilized to speed up a force-directed graph layout algorithm, which can visually demonstrate the suitability of found neighbors, because they affect the layout quality. The graphs are widely used in social network analysis, computer networks or large information systems like photographic databases or multimedia databases to visualize relationships between elements. The achieved results and performance tests are presented as well.