Publicerad: 2014-10-30
ISBN: 978-91-7519-212-3
ISSN: 1650-3686 (tryckt), 1650-3740 (online)
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.
[BC03] BÂDOIU M., CLARKSON K. L.: Smaller core-sets for balls. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms (2003), pp. 801–802. 1, 2
[BEKS01] BRAUNMULLER B., ESTER M., KRIEGEL H.-P., SANDER J.: Multiple similarity queries: a basic DBMS operation for mining in metric databases. IEEE Transactions on Knowledge and Data Engineering 13, 1 (Jan 2001), 79–95. 4
[BH12] BELL N., HOBEROCK J.: Thrust: A productivityoriented library for CUDA. In GPU Computing Gems Jade Edition, Hwu W.-m. W., (Ed.). Morgan Kaufmann Publishers Inc., 2012, pp. 359–371. 2
[BK73] BURKHARD W. A., KELLER R. M.: Some approaches to best-match file searching. Communications of the ACM 16, 4 (Apr. 1973), 230–236. 4
[BS98] BERMAN A., SHAPIRO L.: Selecting good keys for triangle-inequality-based pruning algorithms. In IEEE International Workshop on Content-Based Access of Image and Video Database (Jan 1998), pp. 12–19. 4
[CPZ97] CIACCIA P., PATELLA M., ZEZULA P.: M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of the 23rd International Conference on Very Large Data Bases (1997), Morgan Kaufmann Publishers Inc., pp. 426–435. 9
[DDG*] DONGARRA J., DONG T., GATES M., HAIDAR A., TOMOV S., YAMAZAKI I.: MAGMA: a new generation of linear algebra library for GPU and multicore architectures. 2
[DO12] DAVIDSON A., OWENS J.: Toward techniques for autotuning GPU algorithms. In Applied Parallel and Scientific Computing, vol. 7134 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2012, pp. 110–119. 6
[Gär99] GÄRTNER B.: Fast and robust smallest enclosing balls. In Proceedings of the 7th Annual European Symposium on Algorithms (1999), Springer-Verlag, pp. 325–338. 2
[HS03] HJALTASON G. R., SAMET H.: Index-driven similarity search in metric spaces. ACM Transactions on Database Systems 28, 4 (Dec. 2003), 517–580. 4
[KL] KÄLLBERG L., LARSSON T.: Improved pruning of large data sets for the minimum enclosing ball problem. Graphical Models (to appear). 2, 9
[KMY03] KUMAR P., MITCHELL J. S. B., YILDIRIM E. A.: Approximate minimum enclosing balls in high dimensions using core-sets. Journal of Experimental Algorithmics 8 (2003). 1, 2
[LK13] LARSSON T., KÄLLBERG L.: Fast and robust approximation of smallest enclosing balls in arbitrary dimensions. Computer Graphics Forum 32, 5 (2013), 93–101. 1
[NN04] NIELSEN F., NOCK R.: Approximating smallest enclosing balls. In Proceedings of International Conference on Computational Science and Its Applications (ICCSA) (2004), vol. 3045 of Lecture Notes in Computer Science, Springer. 5
[PS85] PREPARATA F. P., SHAMOS M. I.: Computational Geometry: An Introduction. Springer-Verlag New York, Inc., 1985. 1
[Sør12] SØRENSEN H. H. B.: High-performance matrix-vector multiplication on the GPU. In Euro-Par 2011: Parallel Processing Workshops, vol. 7155 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2012, pp. 377–386. 6
[TKK07] TSANG I. W., KOCSOR A., KWOK J. T.: Simpler core vector machines with enclosing balls. In Proceedings of the 24th International Conference on Machine Learning (2007), ACM, pp. 911–918. 1
[Yil08] YILDIRIM E. A.: Two algorithms for the minimum enclosing ball problem. SIAM Journal on Optimization 19, 3 (Nov. 2008), 1368–1391. 1, 2
