Show all publications

Spiral Search Method to Gpu Parallel Euclidean Minimum Spanning Tree Problem

Open DOI PageDownload Bibliography in Open DocumentDownload Bibliography in HTMLDownload BibTeXDownload RISDownload Bibliographical Ontology (RDF)
In Proc. of International Learning and intelligent OptimizationN Conference, Kalamata, Greece, LION 2018, LNCS 11353, 2018.
DOI: 10.1007/978-3-030-05348-2_2.
We present both sequential and data parallel approaches to build hierarchical minimum spanning forest (MSF) or tree (MST) in Euclidean space (EMSF/EMST) for applications whose input N points are uniformly or boundedly distributed in the Euclidean space. Each iteration of the sequential approach takes O(N) time complexity through combining Borůvka's algorithm with an improved component-based neighborhood search algorithm, namely sliced spiral search, that is a newly proposed improvement of Bentley's spiral search for finding a component graph's closest outgoing point on 2D plane. We also propose a k-d search technique to extend this kind of search into 3D space. The data parallel approach includes a newly proposed two direction breadth-first search (BFS) implementation on graphics processing unit (GPU) platform, which is aimed for selecting a spanning tree's minimum outgoing weight. The GPU parallel approaches assign N threads with one thread associated to one input point, one thread occupies O(1) local memory and the whole algorithm occupies O(N) global memory. Experiments are conducted on point set in the plane of both uniformly distributed data sets and TSPLIB database. We evaluate computation time of the proposed approaches on more than 40 benchmarks with size N growing up to 10^5 points.
Parallel Euclidean Minimum Spanning Tree, spiral search, Minimum Spanning forest, GPU data clustering
Publication Category:
International conference with proceedings
Copyright 2010-2019 © Laboratoire Connaissance et Intelligence Artificielle Distribuées - Université Bourgogne Franche-Comté - Privacy policy