CURE: an efficient clustering algorithm for large databases

Sudipto GuhaRajeev RastogiKyuseok Shim

article1998SIGMOD3,345 citations

Proposes CURE, a hierarchical clustering algorithm that accurately discovers arbitrary-shaped clusters of varying sizes and resists outliers by representing clusters with multiple shrunk points, while leveraging random sampling and partitioning to scale efficiently to massive datasets.

Listen

CURE is a new hierarchical clustering algorithm designed to overcome the limitations of earlier methods that either assume compact spherical clusters of roughly equal size or become unreliable when outliers are present. The work was motivated by the growing volume of corporate data in retail, finance, and telecommunications, where effective grouping is needed to reveal meaningful patterns yet existing tools such as BIRCH and minimum-spanning-tree approaches fail on elongated shapes, widely varying cluster sizes, or noisy data.

The authors therefore set out to create a method that can represent clusters of arbitrary geometry, dampen outlier effects, and still run efficiently on data sets of hundreds of thousands of points. Their solution combines a novel cluster representation—multiple well-scattered points per cluster that are then shrunk toward the cluster mean—with random sampling and a two-pass partitioning scheme that reduces the input size before the final clustering step. Experiments were performed on synthetic two-dimensional data sets containing up to 500 000 points, comparing CURE against BIRCH and MST under controlled variations of cluster shape, size, and noise level.

The principal findings are that CURE recovers the intended non-spherical and unequal-sized clusters where both competing algorithms split or merge them incorrectly; that shrinking the representative points by a moderate factor (roughly 0.2–0.7) makes the method far less sensitive to outliers than the all-points approach while still capturing elongated geometry; that random samples of only 2–3 percent of the original data suffice to preserve cluster structure with high probability; and that the combination of sampling and partitioning yields execution times substantially lower than BIRCH’s pre-clustering pass while maintaining or improving cluster quality.

These results imply that organizations can now apply clustering to large, irregularly shaped data collections without first forcing the data into spherical assumptions or manually removing outliers, thereby lowering the risk of missed patterns and reducing the compute cost of exploratory analysis.

For immediate use, practitioners should draw a random sample of a few thousand points, set the shrink factor between 0.2 and 0.7, retain at least ten representative points per cluster, and apply the two-phase outlier filter before labeling the remaining disk-resident data. When the desired number of clusters is known in advance, partitioning the sample into roughly three to five parts further accelerates the run without harming quality. Additional work is warranted to test the algorithm on high-dimensional and real-world data, to refine automatic selection of the shrink factor, and to integrate incremental updates for streaming sources.

The reported evidence rests primarily on synthetic two-dimensional sets and analytic bounds that assume minimum cluster sizes; therefore users should verify behavior on their own data distributions before relying on the method for critical decisions.

Bell Laboratories Stanford University clustering quality database systems geometry hierarchical clustering centroid-based algorithm outlier removal

Guha et al (1998).pdf

Paper: BIRCH: an efficient data clustering method for very large databases, Tian Zhang et al. (1996). Reading BIRCH first establishes the foundational concepts of scalable, tree-based clustering summaries that CURE builds upon and adapts for non-spherical data.
Paper: A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise, Martin Ester et al. (1996). DBSCAN provides the essential spatial density context and outlier challenges that motivated subsequent clustering algorithms like CURE.

Paper: OPTICS: ordering points to identify the clustering structure, Mihael Ankerst et al. (1999). OPTICS extends density-based clustering concepts to generate hierarchical orderings that overcome the parameter limitations inherent in earlier algorithms like CURE.
Paper: LOF: identifying density-based local outliers, Markus M. Breunig et al. (2000). LOF builds directly on spatial neighborhood and density concepts to address the detection of local outliers in datasets with varying densities.

Cover for 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.

Topics

clustering quality database systems geometry traditional clustering adaptive algorithms optimization problems hierarchical clustering methods

Keywords

hierarchical clustering centroid-based algorithm outlier removal spherical clusters MST algorithm large databases

1 Introduction
1.1 Traditional Clustering Algorithms - Drawbacks
1.2 Our Contributions
2 Related Work
3 Hierarchical Clustering Algorithm
3.1 Intuition and Overview
3.2 Clustering Algorithm
3.3 Time and Space Complexity
4 Enhancements for Large Data Sets
4.1 Random Sampling
4.2 Partitioning for Speedup
4.3 Labeling Data on Disk
4.4 Handling Outliers
5 Experimental Results
5.1 Algorithms
5.2 Data sets
5.3 Quality of Clustering
5.4 Sensitivity to Parameters
5.5 Comparison of Execution time to BIRCH
5.6 Scale-up Experiments
6 Concluding Remarks
Acknowledgments
References

Knowls

Knowl 1 — CURE Cluster Representation and Inter-Cluster Distance Measure
model/method
In the CURE (Clustering Using REpresentatives) algorithm, each cluster $u$ is represented by a set $u.\text{rep}$ containing a constant number $c$ of well-scattered points that are shrunk toward the cluster centroid $u.\text{mean}$ by a shrink factor $\alpha \in [0, 1]$ .

Given a point $p$ chosen from the cluster, its shrunk representative position $p'$ is computed as: $p' = p + \alpha (u.\text{mean} - p) = (1 - \alpha)p + \alpha u.\text{mean}$

The distance between two clusters $u$ and $v$ is defined as the minimum distance between any pair of their respective representative points: $\text{dist}(u, v) = \min_{p \in u.\text{rep}, q \in v.\text{rep}} \text{dist}(p, q)$ where $\text{dist}(p, q)$ is an $L_p$ metric (such as Euclidean $L_2$ or Manhattan $L_1$ ) or a non-metric similarity measure.

This representation bridges the gap between centroid-based clustering (which corresponds to $\alpha = 1$ , where clusters are represented by a single spherical center) and all-points / single-link clustering (which corresponds to $\alpha = 0$ with large $c$ ). By using multiple scattered points, CURE captures arbitrary non-spherical cluster geometries. By shrinking points toward the mean, CURE reduces the influence of isolated outliers located far from the cluster center.
Knowl 2 — CURE Hierarchical Clustering Algorithm
algorithm
CURE performs agglomerative hierarchical clustering using a min-heap $Q$ and a spatial $k$ -d tree $T$ . The heap stores one entry per active cluster $u$ , keyed by the distance $\text{dist}(u, u.\text{closest})$ , where $u.\text{closest}$ is the active cluster nearest to $u$ . The $k$ -d tree $T$ indexes all representative points of all currently active clusters to enable efficient nearest-neighbor searches in multidimensional space.
Input: Set of input points $S$ containing $n$ points in $d$ -dimensional space, target number of clusters $k$ , number of representatives $c$ , shrink factor $\alpha$
Output: A set of $k$ clusters
$T \leftarrow \text{build_kd_tree}(S)$
$Q \leftarrow \text{build_heap}(S)$
while $\text{size}(Q) > k$ do
     $u \leftarrow \text{extract_min}(Q)$
     $v \leftarrow u.\text{closest}$
     $\text{delete}(Q, v)$
     $w \leftarrow \text{merge}(u, v)$
     $\text{delete_rep}(T, u)$
     $\text{delete_rep}(T, v)$
     $\text{insert_rep}(T, w)$
     $w.\text{closest} \leftarrow \text{an arbitrary cluster in } Q$
    for each $x \in Q$ do
        if $\text{dist}(w, x) < \text{dist}(w, w.\text{closest})$ then
             $w.\text{closest} \leftarrow x$
        end if
        if $x.\text{closest} = u \text{ or } x.\text{closest} = v$ then
            if $\text{dist}(x, x.\text{closest}) < \text{dist}(x, w)$ then
                 $x.\text{closest} \leftarrow \text{closest_cluster}(T, x, \text{dist}(x, w))$
            else
                 $x.\text{closest} \leftarrow w$
            end if
             $\text{relocate}(Q, x)$
        else if $\text{dist}(x, x.\text{closest}) > \text{dist}(x, w)$ then
             $x.\text{closest} \leftarrow w$
             $\text{relocate}(Q, x)$
        end if
    end for
     $\text{insert}(Q, w)$
end while
return $Q$
The algorithm requires $O(n)$ space. The worst-case time complexity is $O(n^2 \log n)$ , which reduces to $O(n^2)$ for low-dimensional data (e.g., $d = 2$ ).
Knowl 3 — Constant-Time Representative Selection in Cluster Merging
algorithm
When two clusters $u$ and $v$ are merged into a new cluster $w = u \cup v$ , identifying $c$ well-scattered points across all points of $w$ naively takes $O(|w|)$ time. CURE optimizes this by selecting the $c$ new representatives exclusively from the $2c$ original scattered points of $u$ and $v$ (obtained by unshrinking $u.\text{rep}$ and $v.\text{rep}$ by $\alpha$ ). This reduces the time complexity of the merge step to $O(1)$ .
Input: Clusters $u$ and $v$ to be merged, number of representatives $c$ , shrink factor $\alpha$
Output: Merged cluster $w$
$w \leftarrow u \cup v$
$w.\text{mean} \leftarrow \frac{|u| \cdot u.\text{mean} + |v| \cdot v.\text{mean}}{|u| + |v|}$
$\text{candidates} \leftarrow \text{unshrink}(u.\text{rep}, \alpha) \cup \text{unshrink}(v.\text{rep}, \alpha)$
$\text{tmpSet} \leftarrow \emptyset$
for $i \leftarrow 1$ to $c$ do
     $\text{maxDist} \leftarrow 0$
     $\text{maxPoint} \leftarrow \text{null}$
    for each point $p \in \text{candidates}$ do
        if $i = 1$ then
             $\text{minDist} \leftarrow \text{dist}(p, w.\text{mean})$
        else
             $\text{minDist} \leftarrow \min_{q \in \text{tmpSet}} \text{dist}(p, q)$
        end if
        if $\text{minDist} \ge \text{maxDist}$ then
             $\text{maxDist} \leftarrow \text{minDist}$
             $\text{maxPoint} \leftarrow p$
        end if
    end for
     $\text{tmpSet} \leftarrow \text{tmpSet} \cup \{\text{maxPoint}\}$
end for
$w.\text{rep} \leftarrow \emptyset$
for each point $p \in \text{tmpSet}$ do
     $w.\text{rep} \leftarrow w.\text{rep} \cup \{p + \alpha \cdot (w.\text{mean} - p)\}$
end for
return $w$
Knowl 4 — Chernoff Bound for Minimum Sample Size in Random Sampling
theoretical result
Let $N$ be the total number of data points in a database, and let $u$ be a cluster containing $|u|$ points. If a random sample of size $s$ is drawn uniformly without replacement, and $s$ satisfies:

$s \ge f N + \frac{N}{|u|} \log\left(\frac{1}{\delta}\right) + \frac{N}{|u|} \sqrt{\left(\log\left(\frac{1}{\delta}\right)\right)^2 + 2 f |u| \log\left(\frac{1}{\delta}\right)}$

where $f \in [0, 1]$ is the minimum fraction of points of cluster $u$ required in the sample and $\delta \in (0, 1]$ , then the probability that the sample contains fewer than $f |u|$ points belonging to cluster $u$ is strictly less than $\delta$ .

If $|u_{\min}|$ is the size of the smallest cluster of interest, substituting $|u_{\min}|$ for $|u|$ yields a minimum sample size $s_{\min}$ . For a data set with $k$ clusters each of size at least $|u_{\min}|$ , drawing a sample of size $s_{\min}$ ensures that the probability of failing to capture at least $f|u|$ points from any of the $k$ clusters is at most $k\delta$ .
Knowl 5 — Two-Pass Partitioning Scheme for Large-Scale Speedup
model/method
To cluster large samples of size $s$ that are computationally heavy under quadratic hierarchical clustering, CURE partitions the sample of size $s$ into $p$ disjoint partitions, each of size $s/p$ .
1. Pass 1 (Partition Preclustering): CURE runs its hierarchical clustering on each partition individually until the number of clusters in each partition is reduced to $\frac{s}{p \cdot q}$ for a constant $q > 1$ (e.g., $q = 3$ ). During this pass, individual points are merged into partial subclusters within their partition, without spanning cluster boundaries provided $\frac{s}{p \cdot q} \ge 2k$ to $3k$ .
2. Pass 2 (Global Clustering): The resulting $\frac{s}{q}$ total partial clusters from all $p$ partitions are gathered and clustered in a second hierarchical pass until the target number of clusters $k$ is reached. In this pass, each partial cluster is represented solely by its representative points, keeping the memory footprint small.
Partitioning reduces the asymptotic clustering time complexity from $O(s^2 \log s)$ to: $O\left(\frac{s^2}{p} \left(\frac{q-1}{q}\right) \log\left(\frac{s}{p}\right) + \frac{s^2}{q^2} \log\left(\frac{s}{q}\right)\right)$ This yields a theoretical speedup factor of approximately $\frac{q-1}{pq} + \frac{1}{q^2}$ relative to unpartitioned clustering.
Knowl 6 — Two-Phase Outlier Elimination Mechanism
model/method
Because outliers are isolated and sparsely distributed, clusters of outliers grow much more slowly during agglomerative clustering than genuine clusters. CURE leverages this property to eliminate outliers in two phases:
1. Phase 1 (Intermediate Pruning): Agglomerative clustering proceeds until the total number of remaining clusters drops below a specified fraction of the initial cluster count (a fraction of approximately $1/3$ works well across data sets). At this trigger point, any cluster with very few points (e.g., 1 or 2 points) is classified as an outlier cluster and discarded.
2. Phase 2 (Late-Stage Pruning): When the number of remaining clusters approaches the desired target count $k$ , remaining small clusters (e.g., containing $\le 5$ points) are identified and removed as outliers.
Phase 1 removes isolated individual outliers early, while Phase 2 eliminates small outlier cliques that formed by chance sampling of nearby noise points.
Knowl 7 — Disk Labeling via Multiple Nearest Representatives
model/method
After CURE discovers the final $k$ clusters on a representative sample in main memory, the remaining data points residing on disk are assigned cluster labels in a single scan.

Each data point $x$ on disk is assigned to the cluster $C_i$ ( $i \in \{1, \dots, k\}$ ) that contains the representative point closest to $x$ : $\text{label}(x) = \arg\min_{i \in \{1, \dots, k\}} \left( \min_{p \in C_i.\text{rep}} \text{dist}(x, p) \right)$

Unlike centroid-based labeling schemes that assign points based strictly on distance to a single cluster centroid (which implicitly assumes spherical Voronoi decision boundaries and splits non-spherical shapes), using multiple scattered representative points allows CURE to correctly partition non-spherical, elongated, and varying-sized clusters across the entire disk-resident database.
Knowl 8 — Parameter Sensitivity and Clustering Quality of CURE
empirical result
On two-dimensional synthetic benchmark data containing complex geometries (one large circle, two small circles, two elongated ellipsoids connected by a chain of outliers, and random background noise):
- Shrink Factor $\alpha$ : Values of $\alpha \in [0.2, 0.7]$ consistently identify all true clusters correctly. When $\alpha \le 0.1$ , the scattered points shrink insufficiently, causing CURE to degenerate to single-link/MST behavior and erroneously merge the two ellipsoids across the outlier chain. When $\alpha \ge 0.8$ , representative points concentrate at cluster centroids, causing CURE to degenerate to centroid-based clustering (e.g., BIRCH), which splits the large circle and merges the two small circles.
- Number of Representatives $c$ : Choosing $c \ge 10$ reliably captures non-spherical cluster boundaries. Choosing $c \le 5$ fails because representatives do not adequately cover cluster geometry, causing large clusters to be split.
- Sample Size $s$ : For a dataset of $N = 100{,}000$ points, a random sample of $s = 2500$ ( $2.5\%$ of data) is sufficient to accurately discover all cluster geometries, whereas sample sizes $s \le 2000$ produce poor clustering quality.
Knowl 9 — Scalability and Execution Time Comparison of CURE vs. BIRCH
empirical result
On a benchmark data set of 100 Gaussian clusters ( $k = 100$ ) where data size is scaled from $N = 100{,}000$ to $500{,}000$ points (tested on a Sun Ultra-2/200 with 512 MB RAM):
- Execution Time vs. Dataset Size: CURE's execution time remains nearly flat (increasing only slightly from $\approx 10$ seconds to $\approx 20$ seconds without partitioning) because its clustering operates on a fixed sample size ( $s = 2500$ ), incurring only negligible additional sampling time ( $< 2$ seconds). In contrast, BIRCH's execution time grows substantially with $N$ (from $\approx 30$ seconds at $100\text{k}$ to $\approx 80$ seconds at $500\text{k}$ ) because its CF-tree preclustering scans the entire database.
- Speedup via Partitioning: Increasing the number of partitions $p$ from 1 to 5 reduces CURE's execution time by more than $50\%$ across all tested dataset sizes while maintaining identical clustering quality.

Coverage note — None was omitted; all primary contributions—including the representative point model, hierarchical clustering algorithm, fast merge routine, Chernoff sampling bound, two-pass partitioning speedup, two-phase outlier elimination, disk labeling, and empirical evaluations—have been captured.

References

1.N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In Proc. of ACM SIGMOD, pages 322–331, Atlantic City, NJ, May 1990.
2.Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. The MIT Press, Massachusetts, 1990.
3.Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. A density-based algorithm for discovering clusters in large spatial database with noise. In Int’l Conference on Knowledge Discovery in Databases and Data Mining (KDD-96), Portland, Oregon, August 1996.
4.Martin Ester, Hans-Peter Kriegel, and Xiaowei Xu. A database interface for clustering in large spatial databases. In Int’l Conference on Knowledge Discovery in Databases and Data Mining (KDD-95), Montreal, Canada, August 1995.
5.Sudipto Guha, R. Rastogi, and K. Shim. CURE: A clustering algorithm for large databases. Technical report, Bell Laboratories, Murray Hill, 1997.
6.Anil K. Jain and Richard C. Dubes. Algorithms for Clustering Data. Prentice Hall, Englewood Cliffs, New Jersey, 1988.
7.R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
8.Raymond T. Ng and Jiawei Han. Efficient and effective clustering methods for spatial data mining. In Proc. of the VLDB Conference, Santiago, Chile, September 1994.
9.Clark F. Olson. Parallel algorithms for hierarchical clustering. Technical report, University of California at Berkeley, December 1993.
10.H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1989.
11.Hanan Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley Publishing Company, Inc., New York, 1990.
12.T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+ tree: a dynamic index for multi-dimensional objects. In Proc. 13th Int’l Conference on VLDB, pages 507–518, England, 1987.
13.Jeff Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software, 11(1):37–57, 1985.
14.Tian Zhang, Raghu Ramakrishnan, and Miron Livny. Birch: An efficient data clustering method for very large databases. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 103–114, Montreal, Canada, June 1996.

Citation

MLA

Guha, S., et al. “CURE”. Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 1998, pp. 73–84, https://doi.org/10.1145/276304.276312.

APA

Guha, S., Rastogi, R., & Shim, K. (1998). CURE. Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 73–84. https://doi.org/10.1145/276304.276312

Chicago

Guha, S., R. Rastogi, and K. Shim. 1998. “CURE”. Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 73–84. https://doi.org/10.1145/276304.276312.

Harvard

Guha, S., Rastogi, R. and Shim, K. (1998) “CURE”, Proceedings of the 1998 ACM SIGMOD international conference on Management of data. ACM, pp. 73–84. Available at: https://doi.org/10.1145/276304.276312.

Vancouver

1. Guha S, Rastogi R, Shim K (1998) CURE. In: Proceedings of the 1998 ACM SIGMOD international conference on Management of data. ACM, pp 73–84

BibTeX

@inproceedings{Guha_1998, series={SIGMOD/PODS98}, title={CURE: an efficient clustering algorithm for large databases}, url={http://dx.doi.org/10.1145/276304.276312}, DOI={10.1145/276304.276312}, booktitle={Proceedings of the 1998 ACM SIGMOD international conference on Management of data}, publisher={ACM}, author={Guha, Sudipto and Rastogi, Rajeev and Shim, Kyuseok}, year={1998}, month=June, pages={73–84}, collection={SIGMOD/PODS98} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

CURE: an efficient clustering algorithm for large databases

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — CURE Cluster Representation and Inter-Cluster Distance Measure

Knowl 2 — CURE Hierarchical Clustering Algorithm

Knowl 3 — Constant-Time Representative Selection in Cluster Merging

Knowl 4 — Chernoff Bound for Minimum Sample Size in Random Sampling

Knowl 5 — Two-Pass Partitioning Scheme for Large-Scale Speedup

Knowl 6 — Two-Phase Outlier Elimination Mechanism

Knowl 7 — Disk Labeling via Multiple Nearest Representatives

Knowl 8 — Parameter Sensitivity and Clustering Quality of CURE

Knowl 9 — Scalability and Execution Time Comparison of CURE vs. BIRCH

References

Citation

BibTeX

Access the Paper