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)
Authors:
Details:
In Submitted to journal, 2019.
Abstract:
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.
Keywords:
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