Show all publications

Gpu K-Dimensional Nearest Neighbor Search for Parallel Euclidean Minimum Spanning Tree Problem

Download Bibliography in Open DocumentDownload Bibliography in HTMLDownload BibTeXDownload RISDownload Bibliographical Ontology (RDF)
In Submitted to journal, 2019.
We propose new data parallel approaches working on graphics processing unit (GPU) CUDA platform to build hierarchical minimum spanning forest (MSF) or tree (MST) for applications whose input only contains N points that are uniformly or boundedly distributed in Euclidean K-dimensional space (EMSF/EMST). Characteristic of these proposed algorithms follows ``data parallelism, decentralized control and constant local memory occupied by each GPU thread". Instead of using K-d tree search, we propose a nearest neighbor search algorithm, called K-d search, working based on dividing the Euclidean K-dimensional space into congruent and non- overlapping cells where size of points in each cell is bounded. We further combine the uniqueness property in Euclidean space with this K-d search approach. This combination achieves sequential O(N) time complexity to find bi-chromatic closest pair between two color point sets, and O(N)/N time when working in concurrent read/write parallel model. The data parallel approach also exploits parallelism of each sub-step to build EMST in Borůvka's framework, for example CUDA kernels on a distributed dynamic linked list data structure for GPU parallel tree traversal operation, GPU parallel union-find implementation. Experimental results are conducted on both 2D and 3D benchmarks with up to $10^7$ points on personal laptop, and show that our algorithm runs faster than current fastest dual-tree Mlpack EMST library.
Nearest neighbor search in Euclidean K-dimension space, K-d search, GPU parallel breadth-first search, GPU tree traversal, GPU parallel union-find
Publication Category:
International journal with reading committee
Copyright 2010-2019 © Laboratoire Connaissance et Intelligence Artificielle Distribuées - Université Bourgogne Franche-Comté - Privacy policy