Faster Approximation of Minimum Enclosing Balls by Distance Filtering and GPU Parallelization

REFERENCES

• [Abdelfattah et al. 13] Ahmad Abdelfattah, David Keyes, and Hatem Ltaief. “Systematic Approach in Optimizing Numerical Memory-Bound Kernels on GPU. ” In Euro-Par 2012: Parallel Processing Workshops, Lecture Notes in Computer Science, 7640, pp. 207–216. Berlin, Heidelberg: Springer, 2013.
   Google Scholar
• [Bădoiu and Clarkson 03] Mihai Bădoiu and Kenneth L. Clarkson. “Smaller Core-Sets for Balls. ” In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 801–802, 2003.
   Google Scholar
• [Bell and Hoberock 12] Nathan Bell and Jared Hoberock. “Thrust: A Productivity-Oriented Library for CUDA. ” In GPU Computing Gems Jade Edition, edited by Wen-mei W. Hwu, pp. 359–371. Morgan Kaufmann Publishers Inc., 2012.
   Google Scholar
• [Berman and Shapiro 98] A. Berman and L.G. Shapiro. “Selecting Good Keys for Triangle-Inequality-Based Pruning Algorithms. ” In IEEE International Workshop on Content-Based Access of Image and Video Database, pp. 12–19. IEEE, 1998.
   Google Scholar
• [Braunmüller et al. 01] B. Braunmüller, M. Ester, H.-P. Kriegel, and J. Sander. “Multiple Similarity Queries: A Basic DBMS Operation for Mining in Metric Databases.” IEEE Transactions on Knowledge and Data Engineering 13:1 (2001), 79–95.
   Web of Science ®Google Scholar
• [Burkhard and Keller 73] W. A. Burkhard and R. M. Keller. “Some Approaches to Best-Match File Searching.” Communications of the ACM 16:4 (1973), 230–236.
   Web of Science ®Google Scholar
• [Ciaccia et al. 97] Paolo Ciaccia, Marco Patella, and Pavel Zezula. “M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. ” In Proceedings of the 23rd International Conference on Very Large Data Bases, pp. 426–435. San Francisco, CA: Morgan Kaufmann, 1997.
   Google Scholar
• [Davidson and Owens 12] Andrew Davidson and John Owens. “Toward Techniques for Auto-tuning GPU Algorithms. ” In Applied Parallel and Scientific Computing, Lecture Notes in Computer Science, 7134, pp. 110–119. Berlin, Heidelberg: Springer, 2012.
   Google Scholar
• [Gärtner 99] Bernd Gärtner. “Fast and Robust Smallest Enclosing Balls. ” In Proceedings of the 7th Annual European Symposium on Algorithms, pp. 325–338. Springer-Verlag, 1999.
   Google Scholar
• [Gupta et al. 12] Kshitij Gupta, Jeff Stuart, and John D. Owens. “A Study of Persistent Threads Style GPU Programming for GPGPU Workloads. ” In Proceedings of Innovative Parallel Computing, InPar ’12, 2012.
   Google Scholar
• [Hjaltason and Samet 03] Gisli R. Hjaltason and Hanan Samet. “Index-Driven Similarity Search in Metric Spaces.” ACM Transactions on Database Systems 28:4 (2003), 517–580.
   Web of Science ®Google Scholar
• [Källberg and Larsson 14] Linus Källberg and Thomas Larsson. “Improved Pruning of Large Data Sets for the Minimum Enclosing Ball Problem.” Graphical Models 76:6 (2014), 609–619.
   Google Scholar
• [Kumar et al. 03] Piyush Kumar, Joseph S. B. Mitchell, and E. Alper Yıldırım. “Approximate Minimum Enclosing Balls in High Dimensions Using Core-Sets.” Journal of Experimental Algorithmics 8: 1 (2003).
   Google Scholar
• [Larsson and Källberg 13] Thomas Larsson and Linus Källberg. “Fast and Robust Approximation of Smallest Enclosing Balls in Arbitrary Dimensions.” Computer Graphics Forum 32:5 (2013), 93–101.
   Web of Science ®Google Scholar
• [Nath et al. 11] Rajib Nath, Stanimire Tomov, Tingxing “Tim” Dong, and Jack Dongarra. “Optimizing Symmetric Dense Matrix-Vector Multiplication on GPUs. ” In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 6:1–6:10. New York: ACM, 2011.
   Google Scholar
• [Nielsen and Nock 09] Frank Nielsen and Richard Nock. “Approximating Smallest Enclosing Balls with Applications to Machine Learning.” International Journal of Computational Geometry & Applications 19:5 (2009).
   Web of Science ®Google Scholar
• [Preparata and Shamos 85]Franco P. Preparata and Michael I. Shamos. Computational Geometry: An Introduction. New York: Springer-Verlag, 1985.
   Google Scholar
• [Sørensen 12] Hans Henrik Brandenborg Sørensen. “High-Performance Matrix-Vector Multiplication on the GPU. ” In Euro-Par 2011: Parallel Processing Workshops, Lecture Notes in Computer Science, 7155, pp. 377–386. Berlin, Heidelberg: Springer 2012.
   Google Scholar
• [Tsang et al. 07] Ivor W. Tsang, Andras Kocsor, and James T. Kwok. “Simpler Core Vector Machines with Enclosing Balls. ” In Proceedings of the 24th International Conference on Machine Learning, pp. 911–918. New York: ACM, 2007.
   Google Scholar
• [Volkov 10] Vasily Volkov. “Better Performance at Lower Occupancy.” Presented at the GPU Technology Conference (GTC), 2010.
   Google Scholar
• [Yıldırım 08] E. Alper Yıldırım. “Two Algorithms for the Minimum Enclosing Ball Problem.” SIAM Journal on Optimization 19:3 (2008), 1368–1391.
   Web of Science ®Google Scholar