The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
CURE: an efficient clustering algorithm for large databases
Abstract
Clustering, in data mining, is useful for discovering groups and identifying interesting distributions in the underlying data. Traditional clustering algorithms either favor clusters with spherical shapes and similar sizes, or are very fragile in the presence of outliers. We propose a new clustering algorithm called CURE that is more robust to outliers, and identifies clusters having non-spherical shapes and wide variances in size. CURE achieves this by representing each cluster by a certain fixed number of points that are generated by selecting well scattered points from the cluster and then shrinking them toward the center of the cluster by a specified fraction. Having more than one representative point per cluster allows CURE to adjust well to the geometry of non-spherical shapes and the shrinking helps to dampen the effects of outliers. To handle large databases, CURE employs a combination of random sampling and partitioning. A random sample drawn from the data set is first partitioned and each partition is partially clustered. The partial clusters are then clustered in a second pass to yield the desired clusters. Our experimental results confirm that the quality of clusters produced by CURE is much better than those found by existing algorithms. Furthermore, they demonstrate that random sampling and partitioning enable CURE to not only outperform existing algorithms but also to scale well for large databases without sacrificing clustering quality.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
Algorithms for Clustering Data
Sarle, W. S. (1990) · Technometrics · doi:10.1080/00401706.1990.10484648 · Cited by 7,865
Algorithms for clustering data
Flury, B. (1989) · Journal of Statistical Planning and Inference · doi:10.1016/0378-3758(89)90033-5 · Cited by 6,432
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
The R*-tree: an efficient and robust access method for points and rectangles
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990) · Proceedings of the 1990 ACM SIGMOD international conference on Management of data · doi:10.1145/93597.98741 · Cited by 4,161
BIRCH: an efficient data clustering method for very large databases
Zhang, T., Ramakrishnan, R., & Livny, M. (1996) · Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96 · doi:10.1145/233269.233324 · Cited by 3,935
An Algorithm for Finding Best Matches in Logarithmic Expected Time
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977) · ACM Transactions on Mathematical Software · doi:10.1145/355744.355745 · Cited by 2,813
The design and analysis of spatial data structures
Samet, H. (1989) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,380
Efficient and Effective Clustering Methods for Spatial Data Mining
Ng, R. T., & Han, J. (1994) · Cited by 1,778
Random sampling with a reservoir
Vitter, J. S. (1985) · ACM Transactions on Mathematical Software · doi:10.1145/3147.3165 · Cited by 1,758
Cited by
Data mining: concepts and techniques
(2012) · Choice Reviews Online · doi:10.5860/choice.49-3305 · Cited by 28,531
Data clustering: 50 years beyond K-means
Jain, A. K. (2010) · Pattern Recognition Letters · doi:10.1016/j.patrec.2009.09.011 · Cited by 9,368
Survey of Clustering Algorithms
Xu, R., & WunschII, D. (2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2005.845141 · Cited by 6,197
Ankerst, M. (1999) · doi:10.1145/304181.304187 · Cited by 3,982
A Survey of Clustering Data Mining Techniques
Berkhin, P. (2006) · Grouping Multidimensional Data · doi:10.1007/3-540-28349-8_2 · Cited by 2,804
On Clustering Validation Techniques
Halkidi, M., Batistakis, Y., & Vazirgiannis, M. (2001) · Journal of Intelligent Information Systems · doi:10.1023/a:1012801612483 · Cited by 2,646
Clustering of time series data—a survey
Warren Liao, T. (2005) · Pattern Recognition · doi:10.1016/j.patcog.2005.01.025 · Cited by 2,401
Rajaraman, A., & Ullman, J. D. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139058452 · Cited by 2,262
A Comprehensive Survey of Clustering Algorithms
Xu, D., & Tian, Y. (2015) · Annals of Data Science · doi:10.1007/s40745-015-0040-1 · Cited by 1,939
“CURE, suitable for large-scale clustering, takes random sampling technique to cluster sample separately and integrates the results finally.”
BackgroundMethodInfluentialEfficient algorithms for mining outliers from large data sets
Ramaswamy, S., Rastogi, R., & Shim, K. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335437 · Cited by 1,860
Self-citationTime-series clustering – A decade review
Aghabozorgi, S., Seyed Shirkhorshidi, A., & Ying Wah, T. (2015) · Information Systems · doi:10.1016/j.is.2015.04.007 · Cited by 1,826
A Framework for Clustering Evolving Data Streams
Aggarwal, C. C., Yu, P. S., Han, J., & Wang, J. (2003) · Proceedings 2003 VLDB Conference · doi:10.1016/b978-012722442-8/50016-1 · Cited by 1,808
ST-DBSCAN: An algorithm for clustering spatial–temporal data
Birant, D., & Kut, A. (2007) · Data & Knowledge Engineering · doi:10.1016/j.datak.2006.01.013 · Cited by 1,430
A review of clustering techniques and developments
Saxena, A., Prasad, M., Gupta, A., Bharill, N., Patel, O. P., Tiwari, A., Er, M. J., Ding, W., & Lin, C.-T. (2017) · Neurocomputing · doi:10.1016/j.neucom.2017.06.053 · Cited by 1,357
OPTICS: ordering points to identify the clustering structure
Ankerst, M., Breunig, M. M., Kriegel, H.-P., & Sander, J. (1999) · Proceedings of the 1999 ACM SIGMOD international conference on Management of data · doi:10.1145/304182.304187 · Cited by 1,335
CLARANS: a method for clustering objects for spatial data mining
Ng, R. T., & Han, J. (2002) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2002.1033770 · Cited by 1,202
Combining multiple clusterings using evidence accumulation
Fred, A. L. N., & Jain, A. K. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.113 · Cited by 1,195
Efficient algorithms for mining outliers from large data sets
Ramaswamy, S., Rastogi, R., & Shim, K. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335437 · Cited by 1,171
“Examples of these large patterns include association rules[AMS 95], classification[RS98] and clustering[ZRL96, NH94, EKX95, GRS98 ].”
BackgroundMethodSelf-citationA Survey of Clustering Algorithms for Big Data: Taxonomy and Empirical Analysis
Fahad, A., Alshatri, N., Tari, Z., Alamri, A., Khalil, I., Zomaya, A. Y., Foufou, S., & Bouras, A. (2014) · IEEE Transactions on Emerging Topics in Computing · doi:10.1109/tetc.2014.2330519 · Cited by 1,042
Outlier detection for high dimensional data
Aggarwal, C. C., & Yu, P. S. (2001) · Proceedings of the 2001 ACM SIGMOD international conference on Management of data · doi:10.1145/375663.375668 · Cited by 1,029
Density-Based Clustering over an Evolving Data Stream with Noise
Cao, F., Estert, M., Qian, W., & Zhou, A. (2006) · Proceedings of the 2006 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972764.29 · Cited by 1,016
Rokach, L., & Maimon, O. (2006) · Data Mining and Knowledge Discovery Handbook · doi:10.1007/0-387-25465-x_15 · Cited by 906
Fast algorithms for projected clustering
Aggarwal, C. C., Wolf, J. L., Yu, P. S., Procopiuc, C., & Park, J. S. (1999) · ACM SIGMOD Record · doi:10.1145/304181.304188 · Cited by 900
Clustering data streams: theory and practice
Guha, S., Meyerson, A., Mishra, N., Motwani, R., & O'Callaghan, L. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1198387 · Cited by 882
Self-citationMachine learning in wireless sensor networks: Algorithms, strategies, and applications
Alsheikh, M. A., Lin, S., Niyato, D., & Tan, H.-P. (2014) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2014.2320099 · Cited by 965
Shao, J., Tanner, S. W., Thompson, N., & Cheatham, T. E. (2007) · Journal of Chemical Theory and Computation · doi:10.1021/ct700119m · Cited by 832
State-of-the-art in privacy preserving data mining
Verykios, V. S., Bertino, E., Fovino, I. N., Provenza, L. P., Saygin, Y., & Theodoridis, Y. (2004) · ACM SIGMOD Record · doi:10.1145/974121.974131 · Cited by 816
State of the Art in Defect Detection Based on Machine Vision
Ren, Z., Fang, F., Yan, N., & Wu, Y. (2022) · International Journal of Precision Engineering and Manufacturing-Green Technology · doi:10.1007/s40684-021-00343-6 · Cited by 799
Sinthanayothin, C., Boyce, J. F., Cook, H. L., & Williamson, T. H. (1999) · British Journal of Ophthalmology · doi:10.1136/bjo.83.8.902 · Cited by 778
A k-mean clustering algorithm for mixed numeric and categorical data
Ahmad, A., & Dey, L. (2007) · Data & Knowledge Engineering · doi:10.1016/j.datak.2007.03.016 · Cited by 718
Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data
Ertöz, L., Steinbach, M., & Kumar, V. (2003) · Proceedings of the 2003 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972733.5 · Cited by 703
Bahmani, B., Moseley, B., Vattani, A., Kumar, R., & Vassilvitskii, S. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2180912.2180915 · Cited by 628
Hierarchical Clustering Algorithms for Document Datasets
Zhao, Y., Karypis, G., & Fayyad, U. (2005) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-005-0361-3 · Cited by 627
Guha, S., Mishra, N., Motwani, R., & O'Callaghan, L. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892124 · Cited by 623
Self-citationEmpirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering
Zhao, Y., & Karypis, G. (2004) · Machine Learning · doi:10.1023/b:mach.0000027785.44527.d6 · Cited by 611
DBSCAN: Past, present and future
Rehman, S. U., Asghar, S., Fong, S., & Sarasvady, S. (2014) · The Fifth International Conference on the Applications of Digital Information and Web Technologies (ICADIWT 2014) · doi:10.1109/icadiwt.2014.6814687 · Cited by 606
Why so many clustering algorithms: a position paper
Estivill-Castro, V. (2002) · ACM SIGKDD Explorations Newsletter · doi:10.1145/568574.568575 · Cited by 600
iDistance: An adaptive B + -tree based indexing method for nearest neighbor search
Jagadish, H. V., Ooi, B. C., Tan, K.-L., Yu, C., & Zhang, R. (2005) · ACM Transactions on Database Systems · doi:10.1145/1071610.1071612 · Cited by 595
Discovering word senses from text
Pantel, P., & Lin, D. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775138 · Cited by 591
A Survey of Text Clustering Algorithms
Aggarwal, C. C., & Zhai, C. (2012) · Mining Text Data · doi:10.1007/978-1-4614-3223-4_4 · Cited by 581
Information retrieval on the web
Kobayashi, M., & Takeda, K. (2000) · ACM Computing Surveys · doi:10.1145/358923.358934 · Cited by 562
Evaluation of hierarchical clustering algorithms for document datasets
Zhao, Y., & Karypis, G. (2002) · Proceedings of the eleventh international conference on Information and knowledge management · doi:10.1145/584792.584877 · Cited by 558
Enhancing Effectiveness of Outlier Detections for Low Density Patterns
Tang, J., Chen, Z., Fu, A. W.-C., & Cheung, D. W. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47887-6_53 · Cited by 552
Entropy-based subspace clustering for mining numerical data
Cheng, C.-H., Fu, A. W., & Zhang, Y. (1999) · Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/312129.312199 · Cited by 543
Finding generalized projected clusters in high dimensional spaces
Aggarwal, C. C., & Yu, P. S. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335383 · Cited by 530
A survey of anomaly detection techniques in financial domain
Ahmed, M., Mahmood, A. N., & Islam, M. R. (2016) · Future Generation Computer Systems · doi:10.1016/j.future.2015.01.001 · Cited by 528
Progress in Outlier Detection Techniques: A Survey
Wang, H., Bah, M. J., & Hammad, M. (2019) · IEEE Access · doi:10.1109/access.2019.2932769 · Cited by 523
A Framework for Projected Clustering of High Dimensional Data Streams
Aggarwal, C. C., Han, J., Wang, J., & Yu, P. S. (2004) · Proceedings 2004 VLDB Conference · doi:10.1016/b978-012088469-8.50075-9 · Cited by 519
Data mining in clinical big data: the frequently used databases, steps, and methodological models
Wu, W.-T., Li, Y.-J., Feng, A.-Z., Li, L., Huang, T., Xu, A.-D., & Lyu, J. (2021) · Military Medical Research · doi:10.1186/s40779-021-00338-z · Cited by 505
Fast algorithms for projected clustering
Aggarwal, C. C., Wolf, J. L., Yu, P. S., Procopiuc, C., & Park, J. S. (1999) · Proceedings of the 1999 ACM SIGMOD international conference on Management of data · doi:10.1145/304182.304188 · Cited by 484
Applications of artificial intelligence for disaster management
Sun, W., Bocchini, P., & Davison, B. D. (2020) · Natural Hazards · doi:10.1007/s11069-020-04124-3 · Cited by 491
Clustering validity checking methods: part II
Halkidi, M., Batistakis, Y., & Vazirgiannis, M. (2002) · ACM SIGMOD Record · doi:10.1145/601858.601862 · Cited by 466
A novel intrusion detection system based on hierarchical clustering and support vector machines
Horng, S.-J., Su, M.-Y., Chen, Y.-H., Kao, T.-W., Chen, R.-J., Lai, J.-L., & Perkasa, C. D. (2011) · Expert Systems with Applications · doi:10.1016/j.eswa.2010.06.066 · Cited by 460
Efficient agglomerative hierarchical clustering
Bouguettaya, A., Yu, Q., Liu, X., Zhou, X., & Song, A. (2015) · Expert Systems with Applications · doi:10.1016/j.eswa.2014.09.054 · Cited by 442
Outlier detection for high dimensional data
Aggarwal, C. C., & Yu, P. S. (2001) · ACM SIGMOD Record · doi:10.1145/376284.375668 · Cited by 442
Shared-nearest-neighbor-based clustering by fast search and find of density peaks
Liu, R., Wang, H., & Yu, X. (2018) · Information Sciences · doi:10.1016/j.ins.2018.03.031 · Cited by 429
Clustering validity assessment: finding the optimal partitioning of a data set
Halkidi, M., & Vazirgiannis, M. (2002) · Proceedings 2001 IEEE International Conference on Data Mining · doi:10.1109/icdm.2001.989517 · Cited by 426
On Discovering Moving Clusters in Spatio-temporal Data
Kalnis, P., Mamoulis, N., & Bakiras, S. (2005) · Lecture Notes in Computer Science · doi:10.1007/11535331_21 · Cited by 420
Ranking Outliers Using Symmetric Neighborhood Relationship
Jin, W., Tung, A. K. H., Han, J., & Wang, W. (2006) · Lecture Notes in Computer Science · doi:10.1007/11731139_68 · Cited by 415
Low-complexity fuzzy relational clustering algorithms for Web mining
Krishnapuram, R., Joshi, A., Nasraoui, O., & Yi, L. (2001) · IEEE Transactions on Fuzzy Systems · doi:10.1109/91.940971 · Cited by 392
Data Clustering: 50 Years Beyond K-means
Jain, A. K. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-87479-9_3 · Cited by 373
Series in Machine Perception and Artificial Intelligence
(2012) · Series in machine perception and artificial intelligence · doi:10.1142/smpai · Cited by 365
Comprehensive survey on hierarchical clustering algorithms and the recent developments
Ran, X., Xi, Y., Lu, Y., Wang, X., & Lu, Z. (2023) · Artificial Intelligence Review · doi:10.1007/s10462-022-10366-3 · Cited by 361
Outlier detection using k-nearest neighbour graph
Hautamaki, V., Karkkainen, I., & Franti, P. (2004) · Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004. · doi:10.1109/icpr.2004.1334558 · Cited by 353
COOLCAT: an entropy-based algorithm for categorical clustering
Barbará, D., Li, Y., & Couto, J. (2002) · Proceedings of the eleventh international conference on Information and knowledge management · doi:10.1145/584792.584888 · Cited by 345
An efficient enhanced k-means clustering algorithm
Fahim, A. M., Salem, A. M., Torkey, F. A., & Ramadan, M. A. (2006) · Journal of Zhejiang University-SCIENCE A · doi:10.1631/jzus.2006.a1626 · Cited by 342
Finding interesting associations without support pruning
Cohen, E., Datar, M., Fujiwara, S., Gionis, A., Indyk, P., Motwani, R., Ullman, J. D., & Yang, C. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.908981 · Cited by 341
A Monte Carlo algorithm for fast projective clustering
Procopiuc, C. M., Jones, M., Agarwal, P. K., & Murali, T. M. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564739 · Cited by 340
Automatic Subspace Clustering of High Dimensional Data
Agrawal, R., Gehrke, J., Gunopulos, D., & Raghavan, P. (2005) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-005-1396-1 · Cited by 335
Mining top-n local outliers in large databases
Jin, W., Tung, A. K. H., & Han, J. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502554 · Cited by 328
A new cluster validity measure and its application to image compression
Chou, C.-H., Su, M.-C., & Lai, E. (2004) · Pattern Analysis and Applications · doi:10.1007/s10044-004-0218-1 · Cited by 326
A survey on data stream clustering and classification
Nguyen, H.-L., Woon, Y.-K., & Ng, W.-K. (2015) · Knowledge and Information Systems · doi:10.1007/s10115-014-0808-1 · Cited by 321
An incremental network for on-line unsupervised classification and topology learning
Furao, S., & Hasegawa, O. (2006) · Neural Networks · doi:10.1016/j.neunet.2005.04.006 · Cited by 315
A fast DBSCAN clustering algorithm by accelerating neighbor searching using Groups method
Mahesh Kumar, K., & Rama Mohan Reddy, A. (2016) · Pattern Recognition · doi:10.1016/j.patcog.2016.03.008 · Cited by 308
Quality Scheme Assessment in the Clustering Process
Halkidi, M., Vazirgiannis, M., & Batistakis, Y. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45372-5_26 · Cited by 305
Finding generalized projected clusters in high dimensional spaces
Aggarwal, C. C., & Yu, P. S. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335383 · Cited by 295
Classifying large data sets using SVMs with hierarchical clusters
Yu, H., Yang, J., & Han, J. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956786 · Cited by 273
A survey of density based clustering algorithms
Bhattacharjee, P., & Mitra, P. (2021) · Frontiers of Computer Science · doi:10.1007/s11704-019-9059-3 · Cited by 271
Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?
Houle, M. E., Kriegel, H.-P., Kröger, P., Schubert, E., & Zimek, A. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13818-8_34 · Cited by 268
Clustering Approach Based on Mini Batch Kmeans for Intrusion Detection System Over Big Data
Peng, K., Leung, V. C. M., & Huang, Q. (2018) · IEEE Access · doi:10.1109/access.2018.2810267 · Cited by 268
Leveraging big data analytics in healthcare enhancement: trends, challenges and opportunities
Rehman, A., Naz, S., & Razzak, I. (2022) · Multimedia Systems · doi:10.1007/s00530-020-00736-8 · Cited by 264
Hierarchical Clustering of Time-Series Data Streams
Rodrigues, P. P., Gama, J., & Pedroso, J. P. (2008) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.190727 · Cited by 260
A survey of Clustering Algorithms
Rokach, L. (2009) · Data Mining and Knowledge Discovery Handbook · doi:10.1007/978-0-387-09823-4_14 · Cited by 245
Making AI Forget You: Data Deletion in Machine Learning
Ginart, A., Guan, M. Y., Valiant, G., & Zou, J. (2019) · arXiv · doi:10.48550/arxiv.1907.05012 · Cited by 175
Large-Scale Image Clustering Based on Camera Fingerprints
Lin, X., & Li, C.-T. (2016) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2016.2636086 · Cited by 46
Metadata
- Authors
- Guha, S., Rastogi, R., & Shim, K.
- Venue
- Proceedings of the 1998 ACM SIGMOD international conference on Management of data
- Publisher
- ACM
- Published
- 1998-06
- Pages
- 73-84
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2131687179
- Cited by
- 1,907
- References
- 14
- FWCI
- 30.18
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.