Non-uniform data distribution for communication-efficient parallel clustering

Lists

Tools

Goodall, T., Pettinger, D. and Di Fatta, G. (2013) Non-uniform data distribution for communication-efficient parallel clustering. Journal of Computational Science, 4 (6). pp. 489-495. ISSN 1877-7503

Full text not archived in this repository.

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1016/j.jocs.2013.01.007

Abstract/Summary

Global communicationrequirements andloadimbalanceof someparalleldataminingalgorithms arethe major obstacles to exploitthe computational power of large-scale systems. This work investigates how non-uniform data distributions can be exploited to remove the global communication requirement and to reduce the communication costin parallel data mining algorithms and, in particular, in the k-means algorithm for cluster analysis. In the straightforward parallel formulation of the k-means algorithm, data and computation loads are uniformly distributed over the processing nodes. This approach has excellent load balancing characteristics that may suggest it could scale up to large and extreme-scale parallel computing systems. However, at each iteration step the algorithm requires a global reduction operationwhichhinders thescalabilityoftheapproach.Thisworkstudiesadifferentparallelformulation of the algorithm where the requirement of global communication is removed, while maintaining the same deterministic nature ofthe centralised algorithm. The proposed approach exploits a non-uniform data distribution which can be either found in real-world distributed applications or can be induced by means ofmulti-dimensional binary searchtrees. The approachcanalso be extended to accommodate an approximation error which allows a further reduction ofthe communication costs. The effectiveness of the exact and approximate methods has been tested in a parallel computing system with 64 processors and in simulations with 1024 processing element

Item Type:	Article
Refereed:	Yes
Divisions:	Science > School of Mathematical, Physical and Computational Sciences > Department of Computer Science
ID Code:	32253
Uncontrolled Keywords:	Parallel data mining; Clustering; k-Means; Group communication; Extreme-scale computing
Publisher:	Elsevier

Altmetric

Deposit Details

References

[1] J.B. MacQueen, Some methods for classiﬁcation and analysis of multivariate observations,in: L.M.L.Cam,J.Neyman(Eds.),ProceedingsoftheFifthBerkeley Symposium on Mathematical Statistics and Probability, vol. 1, University of California Press, 1967, pp. 281–297. [2] S.P.Lloyd,Least squaresquantizationinPCM,IEEETransactionsonInformation Theory IT-28 (2)(1982) 129–137. [3] A.K. Jain, M.N. Murty, P.J. Flynn, Data clustering: a review, ACM Computing Surveys 31 (3)(1999) 264–323. [4] A.K.Jain,Dataclustering:50yearsbeyondk-means,PatternRecognitionLetters 31 (8)(2010) 651–666. [5] S. Fouchal, M. Ahat, S.B. Amor, I. Lavallée, M. Bui, Competitive clustering algorithms based on ultrametric properties, Journal of Computational Science, doi:10.1016/j.jocs.2011.11.004. [6] F. Gullo, G. Ponti, A. Tagarelli, G. Tradigo, P. Veltri, A time series approach for clustering mass spectrometry data, Journal of Computational Science 3 (5) (2012) 344–355. [7] S. Samsi, A.K. Krishnamurthy, M.N. Gurcan, An efﬁcient computational frameworkfor theanalysisofwholeslideimages:applicationtofollicular lymphoma immunohistochemistry, Journal of Computational Science 3 (5)(2012) 269–279. [8] A.W. Moore, Efﬁcient memory based learning for robot control, PhD Thesis. [9] K. Alsabti, S. Ranka, V. Singh, An efﬁcient K-Means clustering algorithm, in: Proceedings of FirstWorkshop on High Performance Data Mining, 1998. [10] D. Pelleg, A. Moore, Accelerating exact K-Means algorithms with geometric reasoning, in: Proceedings of Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1999, pp. 277–281. [11] T. Kanungo, D.M. Mount, N.S. Netanyahu, C.D. Piatko, R. Silverman, A.Y. Wu, An efﬁcient K-Means clustering algorithm: analysis and implementation, IEEE Transactions [12] D.Pettinger,G.DiFatta,Spacepartitioningfor scalablek-means,in:2010Ninth InternationalConferenceonMachineLearningandApplications(ICMLA),2010, pp. 319–324. [13] I.S. Dhillon, D.S. Modha, A data-clustering algorithm on distributed memory multiprocessors, Large-Scale Parallel Data Mining, LNAI, vol. 1759, 2002, pp. 245–260. [14] D.Pettinger,G.DiFatta,ScalabilityofefﬁcientparallelK-Means,in:Proceedings ofthe Fifth IEEE International Conference on e-Science,Workshop on Computational e-Science, 2009, pp. 96–101. [15] G. Di Fatta, D. Pettinger, Dynamic load balancing in parallel KD-Tree K-Means, in: Proceedings of the International IEEE Conference on Scalable Computing and Communications (ScalCom), 2010, pp. 2478–2485. [16] D.Aloise,A.Deshpande,P.Hansen,P.Popat,Np-hardnessofEuclideansum-ofsquares clustering, Machine Learning 75 (2009) 245–248. [17] D.Judd,P.K.McKinley,A.K.Jain,Large-scaleparalleldataclustering,IEEETransactions on Pattern Analysis and Machine Intelligence 20 (8)(1998) 871–876. [18] D. Foti, D. Lipari, C. Pizzuti, D. Talia, Scalable parallel clustering for data mining on multicomputers, in: Proceedings ofthe 15th IPDPS 2000Workshops on Parallel and Distributed Processing, 2000, pp. 390–398. [19] MPI Forum, MPI: A Message-Passing Interface Standard, Version 2.2, mpi22- report.pdf, September 2009. http://www.mpi-forum.org/docs/mpi-2.2/ [20] J.L. Bentley, Multidimensional binary search trees used for associative searching, Communications ofthe ACM 18 (9)(1975) 509–517. [21] I.Al-furaih, S.Aluru, S.Goil, S.Ranka,Parallel constructionofmultidimensional binary search trees, IEEE Transactions on Parallel and Distributed Systems 11 (2)(2000) 136–148. [22] X. Yang, Z.Wang, J.Xue, Y. Zhou, The reliability wallfor exascale supercomputing, IEEE Transactions on Computers 61 (6)(2012) 767–779. [23] R.DePrisco,A.Fekete,N.Lynch,A.Shvartsman,Adynamicview-orientedgroup communication service, in: Proceedings ofthe SeventeenthAnnualACMSymposiumonPrinciplesofDistributedComputing,PODC’98,ACM,NewYork,NY, USA, 1998, pp. 227–236. [24] A. Schiper, Dynamic group communication, Distributed Computing 18 (2006) 359–374. [25] J.B. Kruskal, M. Wish, Multidimensional Scaling, Sage University Paper Series on Quantitative Applications in the Social Sciences, Sage Publications, 07-011, Beverly Hills and London, 1978. [26] M. Baker, B. Carpenter, A. Shaﬁ, MPJ Express: towards thread safe Java HPC, in: Proceedings of the IEEE International Conference on Cluster Computing, 2006. [27] A.Montresor,M.Jelasity, PeerSim:Ascalable P2P simulator,in: Proceedings of the Ninth International Conference on Peer-to-Peer (P2P’09), 2009.

University Staff: Request a correction | Centaur Editors: Update this record

University of Reading

CentAUR: Central Archive at the University of Reading

Accessibility navigation

Non-uniform data distribution for communication-efficient parallel clustering

Abstract/Summary

Page navigation

See also

Footer navigation