A method for clustering transient data streams

ABSTRACT

This paper describes a novel method for clustering single and multi-dimensional data streams. With incremental computation of the incoming data, our method determines if the cluster formation should change from an initial cluster formation. Four main types of cluster evolutions are studied: cluster appearance, cluster disappearance, cluster splitting, and cluster merging. We present experimental results of our algorithms both in terms of scalability and cluster quality, compared with recent work in this area.

REFERENCES

• 1: Charu C. Aggarwal , Jiawei Han , Jianyong Wang , Philip S. Yu, A framework for projected clustering of high dimensional data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.852-863, August 31-September 03, 2004, Toronto, Canada
• 2: 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]
• 3: Pedro Pereira Rodrigues , João Gama , Joao Pedroso, Hierarchical Clustering of Time-Series Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.20 n.5, p.615-627, May 2008 [doi>10.1109/TKDE.2007.190727]
• 4: Komkrit Udommanetanakit , Thanawin Rakthanmanon , Kitsana Waiyamai, E-Stream: Evolution-Based Technique for Stream Clustering, Proceedings of the 3rd international conference on Advanced Data Mining and Applications, August 06-08, 2007, Harbin, China [doi>10.1007/978-3-540-73871-8_58]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

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

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
Gaussian distribution, clustering, data streams