Article | Proceedings of SIGRAD 2014, Visual Computing, June 12-13, 2014, Göteborg, Sweden | Accelerated Computation of Minimum Enclosing Balls by GPU Parallelization and Distance Filtering Link�ping University Electronic Press Conference Proceedings
Göm menyn

Title:
Accelerated Computation of Minimum Enclosing Balls by GPU Parallelization and Distance Filtering
Author:
Linus Källberg: Mälardalen University, Sweden Thomas Larsson: Mälardalen University, Sweden
Download:
Full text (pdf)
Year:
2014
Conference:
Proceedings of SIGRAD 2014, Visual Computing, June 12-13, 2014, Göteborg, Sweden
Issue:
106
Article no.:
008
Pages:
57-65
No. of pages:
9
Publication type:
Abstract and Fulltext
Published:
2014-10-30
ISBN:
978-91-7519-212-3
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press, Linköpings universitet


Export in BibTex, RIS or text

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.

Proceedings of SIGRAD 2014, Visual Computing, June 12-13, 2014, Göteborg, Sweden

Author:
Linus Källberg, Thomas Larsson
Title:
Accelerated Computation of Minimum Enclosing Balls by GPU Parallelization and Distance Filtering
References:

[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

Proceedings of SIGRAD 2014, Visual Computing, June 12-13, 2014, Göteborg, Sweden

Author:
Linus Källberg, Thomas Larsson
Title:
Accelerated Computation of Minimum Enclosing Balls by GPU Parallelization and Distance Filtering
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment


Responsible for this page: Peter Berkesand
Last updated: 2018-9-11