Name
Abstract | ||
|---|---|---|
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 (kNN) 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 kNNs. 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 kNN graph structure. The proposed algorithm is implemented for CUDA enabled GPUs kNN-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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-31125-3_6 | ICCSA (1) |
Keywords | DocType | Volume |
classical Bor,efficient solution,large-scale synthetic,general purpose computer,kNN graph structure,computer vision,MST algorithm,large-scale dataset,scalable MST construction,classical MST computation,MST problem | Conference | 7333 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
13 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ahmed Shamsul Arefin | 1 | 4 | 2.17 |
| Carlos Riveros | 2 | 6 | 1.81 |
| Regina Berretta | 3 | 49 | 11.60 |
| Pablo Moscato | 4 | 334 | 37.27 |