Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Mining informative patterns from very large, dynamically changing databases poses numerous interesting challenges. Data summarizations (e.g., data bubbles) have been proposed to compress very large static databases into representative points suitable for subsequent effective hierarchical cluster analysis. In many real world applications, however, the databases dynamically change due to frequent insertions and deletions, possibly changing the data distribution and clustering structure over time. Completely reapplying both the data summarization and the clustering algorithm to detect the changes in the clustering structure and update the uncovered data patterns following such deletions and insertions is prohibitively expensive for large fast changing databases. In this paper, we propose a new scheme to maintain data bubbles incrementally. By using incremental data bubbles, a high-quality hierarchical clustering is quickly available at any point in time. In our scheme, a quality measure for incremental data bubbles is used to identify data bubbles that do not compress well their underlying data points after certain insertions and deletions. Only these data bubbles are re-built using efficient split and merge operations. An extensive experimental evaluation shows that the incremental data bubbles provide significantly faster data summarization than completely re-building the data bubbles after a certain number of insertions and deletions, and are effective in preserving (and in some cases even improving) the quality of the data summarization.

REFERENCES

• 1: Aggarwal, C. C., Han, J., Wang, J., Yu. P. S. A Framework for Clustering Evolving Data Streams. In VLDB'03, 81--92, 2003.
• 2: Mihael Ankerst , Markus M. Breunig , Hans-Peter Kriegel , Jörg Sander, OPTICS: ordering points to identify the clustering structure, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.49-60, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: Efficiently Supporting Multiple Similarity Queries for Mining in Metric Databases, Proceedings of the 16th International Conference on Data Engineering, p.256, February 28-March 03, 2000
• 4: Daniel Barbará, Requirements for clustering data streams, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002 [doi>10.1145/507515.507519]
• 5: Markus M. Breunig , Hans-Peter Kriegel , Peer Kröger , Jörg Sander, Data bubbles: quality preserving performance boosting for hierarchical clustering, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.79-90, May 21-24, 2001, Santa Barbara, California, United States
• 6: Moses Charikar , Chandra Chekuri , Tomás Feder , Rajeev Motwani, Incremental clustering and dynamic information retrieval, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.626-635, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258657]
• 7: Chien-Yu Chen , Shien-Ching Hwang , Yen-Jen Oyang, An Incremental Hierarchical Data Clustering Algorithm Based on Gravity Theory, Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, p.237-250, May 06-08, 2002
• 8: Elkan, C. Using the Triangle Inequality to Accelerate k-means. In ICML'03, 2003.
• 9: Ester, M., Kriegel, H-P., Sander, J., Xu, X. A Density Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD'96, 226--231, 1996.
• 10: Martin Ester , Hans-Peter Kriegel , Jörg Sander , Michael Wimmer , Xiaowei Xu, Incremental Clustering for Mining in a Data Warehousing Environment, Proceedings of the 24rd International Conference on Very Large Data Bases, p.323-333, August 24-27, 1998
• 11: Roberto F. Santos Filho , Agma J. M. Traina , Caetano Traina, Jr. , Christos Faloutsos, Similarity Search without Tears: The OMNI Family of All-purpose Access Methods, Proceedings of the 17th International Conference on Data Engineering, p.623-630, April 02-06, 2001
• 12: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining data streams under block evolution, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002 [doi>10.1145/507515.507517]
• 13: Bjornar Larsen , Chinatsu Aone, Fast and effective text mining using linear-time document clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.16-22, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312186]
• 14: MacQueen, J. Some Methods for Classification and Analysis of Multivariate Observations. In 5th Berkeley Symp. Math. Statist. Prob., 281--297, 1967.
• 15: Streaming-Data Algorithms for High-Quality Clustering, Proceedings of the 18th International Conference on Data Engineering, p.685, February 26-March 01, 2002
• 16: Sander, J., Qin, X., Lu. Z., Niu, N. Kovarsky, A. Automated Extraction of Clusters from Hierarchical Clustering Representations. PAKDD'03.
• 17: Sibson, R. SLINK: An Optimally Efficient Algorithm for the Single-link Cluster Method. The Computer Journal, 16(1):30--34, 1973.
• 18: Triola, M. F., Goodman, W. M., Law, R. Elementary Statistics First Canadian Edition, Addison-Wesley, Don Mills, Ontario, 1999.
• 19: Dwi H. Widyantoro , Thomas R. Ioerger , John Yen, An Incremental Approach to Building a Cluster Hierarchy, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.705, December 09-12, 2002
• 20: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Keywords:
clustering, data summarization, incremental data bubbles