High Performance Clustering of Social Images in a Map- Collective Programming Model

Large-scale iterative computations are common in many important data mining and machine learning algorithms. In most of these applications, individual iterations can be specified as MapReduce computations, leading to the Iterative MapReduce programming model for efficient execution of data-intensive iterative computations interoperably between HPC and cloud environments. The initial work of Iterative MapReduce model [1] focuses on optimization of data flow and reducing data transfer between MapReduce iterations by caching invariant data in the local memory of compute nodes. We observe that a systematic approach to collective communication is essential in many iterative algorithms but is missing in the current model. Thus we generalize the iterative MapReduce concept to Map-Collective noting that large collectives are a distinctive feature of data intensive and data mining applications. This abstract shows the value of Map-Collective model applied to large scale social image clustering problems where 10-100 million images represented as points in a high dimensional (up to 2048) vector space are needed to be divided into 1-10 million clusters. Major Results: 1) Data mining dominated by collectives with large size 512 MB messages require new technology. 2) New broadcast collective is four times faster than best Java MPI and gives 20 % better performance than fastest C/C++ MPI methods and a factor of 5 improvement over non-optimized (for topology) pipeline-based method over 150 nodes. 3) Local aggregation in Map stage reduces the size of 20 TB intermediate data by at least 90%. 4) Our new algorithm scales much better than Spark[2] 5) These communication improvement will be combined with triangle inequality improvements [3] (Elkan’s algorithm [4] extended for large problem size) 6) Different optimizations for Azure give Twisister4Azure[5] better performance than curren