Title :
Cost-efficient implementation of k-NN algorithm on multi-core processors
Author :
Ahmadzadeh, Armin ; Mirzaei, Reza ; Madani, Hatef ; Shobeiri, Mohammad ; Sadeghi, Mohammadreza ; Gavahi, Mohsen ; Jafari, Kianoush ; Aznaveh, Mohsen Mahmoudi ; Gorgin, Saeid
Author_Institution :
Sch. of Comput. Sci., Inst. for Res. in Fundamental Sci. (IPM), Tehran, Iran
Abstract :
k-nearest neighbor´s algorithm plays a significant role in the processing time of many applications in a variety of fields such as pattern recognition, data mining and machine learning. In this paper, we present an accurate parallel method for implementing k-NN algorithm in multi-core platforms. Based on the problem definition we used Mahalanobis distance and developed mathematic techniques and deployed best programming experiences to accelerate contest reference implementation. Our method makes exhaustive use of CPU and minimizes memory access. This method is the winner of cost-adjust-performance of MEMOCODE contest design 2014 and is 616× faster than the reference implementation of the contest.
Keywords :
minimisation; multiprocessing systems; storage management; CPU; MEMOCODE contest design 2014; Mahalanobis distance; cost-adjust-performance; data mining; k-NN algorithm; k-nearest neighbor algorithm; machine learning; memory access minimization; multicore processors; pattern recognition; Algorithm design and analysis; Covariance matrices; Equations; Memory management; Multicore processing; Optimization; Vectors; Cost-efficent; Mahalanobis distance; Multi-core processors; k-NN algorithm;
Conference_Titel :
Formal Methods and Models for Codesign (MEMOCODE), 2014 Twelfth ACM/IEEE International Conference on
Conference_Location :
Lausanne
DOI :
10.1109/MEMCOD.2014.6961863
