Accelerated Computation of Minimum Enclosing Balls by GPU Parallelization and Distance Filtering
Malardalen University, Sweden
SIGRAD, 2014
@article{kallberg2014accelerated,
title={Accelerated Computation of Minimum Enclosing Balls by GPU Parallelization and Distance Filtering},
author={Obaid, M and Sj{"o}lie, D and Sintorn, E and Fjeld, M},
year={2014}
}
Minimum enclosing balls are used extensively to speed up multidimensional data processing in, e.g., machine learning, spatial databases, and computer graphics. We present a case study of several acceleration techniques that are applicable in enclosing ball algorithms based on repeated farthest-point queries. Parallel GPU solutions using CUDA are developed for both low- and high-dimensional cases. Furthermore, two different distance filtering heuristics are proposed aiming at reducing the cost of the farthest-point queries as much as possible by exploiting lower and upper distance bounds. Empirical tests show encouraging results. Compared to a sequential CPU version of the algorithm, the GPU parallelization runs up to 11 times faster. When applying the distance filtering techniques, further speedups are observed.
July 1, 2014 by hgpu
