Toward autonomic grids: analyzing the job flow with affinity streaming

ABSTRACT

The Affinity Propagation (AP) clustering algorithm proposed by Frey and Dueck (2007) provides an understandable, nearly optimal summary of a dataset, albeit with quadratic computational complexity. This paper, motivated by Autonomic Computing, extends AP to the data streaming framework. Firstly a hierarchical strategy is used to reduce the complexity to O(N^1+ε); the distortion loss incurred is analyzed in relation with the dimension of the data items. Secondly, a coupling with a change detection test is used to cope with non-stationary data distribution, and rebuild the model as needed. The presented approach StrAP is applied to the stream of jobs submitted to the EGEE Grid, providing an understandable description of the job flow and enabling the system administrator to spot online some sources of failures.

REFERENCES

• 1: F. Bergeaud , S. Mallat, Matching pursuit of images, Proceedings of the 1995 International Conference on Image Processing (Vol. 1)-Volume 1, p.53, October 23-26, 1995
• 2: F. Cao, M. Ester, W. Qian, and A. Zhou. Density-based clustering over an evolving data stream with noise. In SIAM Conference on Data Mining (SDM), pages 326--337, 2006.
• 3: G. Cormode, S. Muthukrishnan, and W. Zhuang. Conquering the divide: Continuous clustering of distributed data streams. In ICDE, pages 1036--1045, 2007.
• 4: M. Ester. A density-based algorithm for discovering clusters in large spatial databases with noise: the uniqueness of a good optimum for k-means. In SIGKDD, pages 226--231, 1996.
• 5: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth, From data mining to knowledge discovery: an overview, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 6: B. Frey and D. Dueck. Clustering by passing messages between data points. Science, 315:972--976, 2007.
• 7: João Gama , Ricardo Rocha , Pedro Medas, Accurate decision trees for mining high-speed data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956813]
• 8: João Gama , Pedro Pereira Rodrigues, Stream-Based Electricity Load Forecast, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_45]
• 9: Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003 [doi>10.1109/TKDE.2003.1198387]
• 10: Z. Harchaoui, F. Bach, and E. Moulines. Kernel change-point analysis. In NIPS, 2008.
• 11: D. Hinkley. Inference about the change-point from cumulative sum tests. Biometrika, 58:509--523, 1971.
• 12: Dan Judd , Philip K. McKinley , Anil K. Jain, Large-Scale Parallel Data Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.8, p.871-876, August 1998 [doi>10.1109/34.709614]
• 13: Michele Leone , Sumedha , Martin Weigt, Clustering by soft-constraint affinity propagation, Bioinformatics, v.23 n.20, p.2708-2715, September 2007 [doi>10.1093/bioinformatics/btm414]
• 14: Marina Meilă, The uniqueness of a good optimum for K-means, Proceedings of the 23rd international conference on Machine learning, p.625-632, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143923]
• 15: S. Muthukrishnan , Eric van den Berg , Yihua Wu, Sequential Change Detection on Data Streams, Proceedings of the Seventh IEEE International Conference on Data Mining Workshops, p.551-550, October 28-31, 2007 [doi>10.1109/ICDMW.2007.89]
• 16: E. Page. Continuous inspection schemes. Biometrika, 41:100--115, 1954.
• 17: Noam Palatin , Arie Leizarowitz , Assaf Schuster , Ran Wolff, Mining for misconfigured machines in grid systems, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150488]
• 18: Carl Edward Rasmussen , Christopher K. I. Williams, Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning), The MIT Press, 2005
• 19: I. Rish, M. Brodie, and S. M. et al. Adaptive diagnosis in distributed systems. IEEE Trans. on Neural Networks, 16:1088--1109, 2005.
• 20: G. Schwarz. Estimating the dimension of a model. The Annals of Statistics, 6:461--464, 1978.
• 21: Julien Villemonteix , Emmanuel Vazquez , Maryan Sidorkiewicz , Eric Walter, Global optimization of expensive-to-evaluate functions: an empirical comparison of two sampling criteria, Journal of Global Optimization, v.43 n.2-3, p.373-389, March 2009 [doi>10.1007/s10898-008-9313-y]
• 22: Xiangliang Zhang , Cyril Furtlehner , Michèle Sebag, Data Streaming with Affinity Propagation, Proceedings of the European conference on Machine Learning and Knowledge Discovery in Databases - Part II, September 15-19, 2008, Antwerp, Belgium [doi>10.1007/978-3-540-87481-2_41]
• 23: J. Andreeva, B. Gaidioz, J. Herrala, and et al. Dashboard for the LHC experiments. Journal of Physics: Conference Series, vol. 119, 2008.
• 24: Real Time Monitor: http://gridportal.hep.ph.ic.ac.uk/rtm/.
• 25: X. Zhang, C. Furtlehner, and M. Sebag. INRIA research report in progress.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures; Algorithms

General Terms:
Algorithms, Experimentation

Keywords:
affinity propagation, autonomic computing, online clustering