betaFeedback

WorksComputer Science

Fast and Memory-Light Evaluation of Density-Based Clusterings with the DISCO Index in R

Abstract

DISCO is a recent internal cluster validity index for density-based clustering that, unlike earlier indices, also evaluates the quality of noise labels. The discoCVI package makes DISCO available in R. This article describes the design of the package and a typical workflow, in which DISCO is used to compare clusterings and to choose the parameters of HDBSCAN without ground truth, followed by the implementation introduced in version 0.2.0. DISCO is defined through density-connectivity distances between all pairs of points, so direct implementations store several n-by-n matrices. We show that every quantity DISCO needs can be read off the single-linkage merge tree of the mutual-reachability minimum spanning tree, so that the index can be computed exactly with memory that grows linearly with the number of points, while the running time remains quadratic as in the original definition. The implementation is tested against the previous version, agrees with the original Python implementation to within 3×10−133 \times 10^{-13}, and corrects the score of singleton clusters to match the published definition. In benchmarks, discoCVI is 23 to 138 times faster than its previous version for 500 to 4,000 points and 3 to 9 times faster than the Python reference for 500 to 8,000 points, using a fraction of the memory of both, and it scores 100,000 points in about 50 seconds with less than 200 MB of memory.

Introduction

Clustering without ground truth needs internal cluster validity indices (CVIs), which score a partition using only the data and the labels. They are used to compare the output of different algorithms and, above all, to choose the parameters of a clustering algorithm when no labelled data exist. For density-based algorithms such as DBSCAN ([9]) and HDBSCAN ([4]), which find clusters of arbitrary shape and label low-density points as noise, classical indices such as the silhouette coefficient ([20]) are a poor fit: they favour convex clusters and have no notion of noise. Density-based indices such as DBCV ([17]) address the first problem, and the recent DISCO index ([2]) also addresses the second: it scores every point labelled as noise according to whether it really lies in a sparse region far from all clusters.

Existing software. Several CRAN packages provide internal validity indices: cluster computes the silhouette coefficient, clusterCrit and fpc offer a wide range of classical indices (fpc also implements the density-based index CDby), and DBCVindex implements DBCV ([5]). None of them evaluates noise labels. The original DISCO implementation is written in Python and is not distributed as a package. discoCVI ([8]) makes DISCO available in R; its first release translated the reference implementation line by line.

The gap. DISCO is defined through the density-connectivity distance (dc-distance) [1] between every pair of points. Both the reference implementation and discoCVI 0.1.1 therefore build the full matrices of mutual-reachability distances and dc-distances. Time and memory grow quadratically with the number of points nn: version 0.1.1 needs about 19 seconds and 1.2 GB to score 4,000 points, and a few thousand points more exhaust a laptop. Because an index is usually evaluated for many candidate clusterings, this cost is multiplied by the size of the search, which matters for running time and also for the energy use of the analysis [22, 21, 14].

This article. We describe the design of discoCVI and a typical workflow, and then the implementation introduced in version 0.2.0, which computes DISCO exactly without any n×nn \times n matrix. We show that this is possible because the dc-distance between two points equals the height at which they are merged in the single-linkage tree of the mutual-reachability graph, so that all per-cluster sums and minima of dc-distances can be accumulated in one pass over that tree. We report tests against the previous version and against the original Python implementation, and a benchmark of time, memory and energy.

The DISCO index

We follow the notation of Beer et al. [2]. Let X={x1,…,xn}⊂RpX = \{x_1,\ldots,x_n\} \subset\mathbb{R}^p and let a clustering C={C1,…,CK}C = \{C_1,\ldots,C_K\} consist of disjoint clusters, with the remaining points N=X∖⋃iCiN = X \setminus\bigcup_i C_i labelled as noise; for a cluster point xx, C^x\widehat{C}_x denotes its cluster.

Distances. For a parameter μ\mu (min_points in the package, default 5), the core distance κ(x)\kappa(x) is the Euclidean distance from xx to its μ\mu-th nearest neighbour, where xx counts as its own first neighbour, as in the reference implementation; equivalently, it is the distance to the (μ−1)(\mu-1)-th nearest other point, and μ≥2\mu\ge2 is required. The mutual-reachability distance [4] is

dm(x,y)=max⁡{κ(x),κ(y),∥x−y∥},d_m(x,y) = \max\{\kappa(x),\kappa(y),\lVert x-y\rVert\},

and the dc-distance [1] is the minimax path distance in the complete graph weighted by dmd_m, that is, the smallest possible value of the largest edge on a path from xx to yy, with ddc(x,x)=0d_{dc}(x,x)=0. It equals the largest edge on the path between xx and yy in any minimum spanning tree (MST) of that graph [12]; in particular it does not depend on how ties between equal edge weights are broken when the MST is built.

DISCO score. DISCO is defined pointwise, and the score of a clustering is the mean of the pointwise scores,

ρ(X)=1n∑x∈Xρ(x),ρ(x)={ρcluster(x)if x∈Ci for some i,ρnoise(x)if x∈N.\rho(X)=\frac{1}{n}\sum_{x\in X}\rho(x), \qquad \rho(x)= \begin{cases} \rho_{\mathrm{cluster}}(x) & \text{if }x\in C_i\text{ for some }i,\\ \rho_{\mathrm{noise}}(x) & \text{if }x\in N. \end{cases}

Cluster points. With dˉdc(x,C)\bar{d}_{dc}(x,C) the mean dc-distance from xx to the points of CC, a cluster point receives

ρcluster(x)=min⁡Ci≠C^xdˉdc(x,Ci)−dˉdc(x,C^x)max⁡{dˉdc(x,Ci),dˉdc(x,C^x)}.\rho_{\mathrm{cluster}}(x)=\min_{C_i\ne\widehat{C}_x} \frac{\bar{d}_{dc}(x,C_i)-\bar{d}_{dc}(x,\widehat{C}_x)} {\max\{\bar{d}_{dc}(x,C_i),\bar{d}_{dc}(x,\widehat{C}_x)\}}.

For fixed a≥0a\ge0 the function b↦(b−a)/max⁡{a,b}b\mapsto(b-a)/\max\{a,b\} is non-decreasing, so the minimum is attained at the closest cluster, and ρcluster\rho_{\mathrm{cluster}} is the silhouette coefficient computed on dc-distances:

ρcluster(x)=b(x)−a(x)max⁡{a(x),b(x)},\rho_{\mathrm{cluster}}(x)=\frac{b(x)-a(x)}{\max\{a(x),b(x)\}},
a(x)=1∣C^x∣−1∑y∈C^x∖{x}ddc(x,y),b(x)=min⁡Ci≠C^x1∣Ci∣∑y∈Ciddc(x,y).a(x)=\frac{1}{|\widehat{C}_x|-1}\sum_{y\in\widehat{C}_x\setminus\{x\}}d_{dc}(x,y), \qquad b(x)=\min_{C_i\ne\widehat{C}_x}\frac{1}{|C_i|}\sum_{y\in C_i}d_{dc}(x,y).

As in the reference implementation, which uses the silhouette function of scikit-learn [18], the within-cluster mean a(x)a(x) is taken over the other members of C^x\hat{C}_x.

Noise points. With the core-distance threshold of a cluster κ(C)=max⁡y∈Cκ(y)\kappa(C) = \max_{y \in C} \kappa(y) and mC(x)=min⁡y∈Cddc(x,y)m_C(x) = \min_{y \in C} d_{dc}(x, y), a noise point receives the minimum of two scores,

ρsparse(x)=min⁡C∈Cκ(x)−κ(C)max⁡{κ(x),κ(C)},ρfar(x)=min⁡C∈CmC(x)−κ(C)max⁡{mC(x),κ(C)}\rho_{\mathrm{sparse}}(x) = \min_{C \in\mathcal{C}} \frac{\kappa(x) - \kappa(C)}{\max\{\kappa(x), \kappa(C)\}}, \qquad\rho_{\mathrm{far}}(x) = \min_{C \in\mathcal{C}} \frac{m_C(x) - \kappa(C)}{\max\{m_C(x), \kappa(C)\}}
ρnoise(x)=min⁡{ρsparse(x),ρfar(x)}.\rho_{\mathrm{noise}}(x) = \min\{\rho_{\mathrm{sparse}}(x), \rho_{\mathrm{far}}(x)\}.

ρsparse\rho_{\mathrm{sparse}} is positive if xx is sparser than every cluster, and ρfar\rho_{\mathrm{far}} is positive if xx is not density-connected to any cluster.

Edge cases ([2 Section 3.1]). (i) If all points are noise, every score is −1-1. (ii) If there is a single cluster and no noise, every score is 00. (iii) Points in singleton clusters score 00. (iv) If there is a single cluster plus noise, the cluster points are compared with the closest noise point instead of the (non-existent) closest cluster, i.e. b(x)b(x) is replaced by min⁡y∈Nddc(x,y)\min_{y \in N} d_{dc}(x, y). (v) If a denominator is zero, for example when more than μ\mu duplicate points have core distance 00, the corresponding fraction is set to 00.

Package design

Intended users. discoCVI is written for data analysts who cluster data with a density-based method, for example with dbscan [11], and need to judge or tune the result without ground truth. Using the package requires no knowledge of how DISCO is computed: one function returns a score, and a second returns one score per point.

Interface. The package exports five functions with plain numeric inputs and outputs:

  • disco_score(X, labels, min_points = 5) returns the DISCO score of a clustering, a single number in [−1,1][-1, 1];

  • disco_samples(X, labels, min_points = 5) returns the pointwise scores ρ(x)\rho(x);

  • p_cluster() and p_noise() return the two components of the score for cluster points and noise points (p_noise() returns ρsparse\rho_{\mathrm{sparse}} and ρfar\rho_{\mathrm{far}} separately);

  • compute_dc_distances(X, min_points = 5) returns the dc-distance matrix, which is useful for analysing small datasets or comparing many labellings of the same data.

XX is a numeric matrix or data frame and labels an integer vector in which -1 marks noise. The function names, the argument min_points and the noise label -1 are those of the reference Python implementation, which itself follows the conventions of scikit-learn, so that code and results carry over between the two languages.

Design choices. The functions return plain numeric vectors (or a list of two vectors for p_noise()) rather than objects of an S3, S4 or R6 class. A validity index produces numbers that users typically put into a data frame, average, plot, or pass to sapply() over a grid of parameters, and a class would add no information while making these operations less direct. The package is deliberately agnostic to the clustering algorithm: it accepts labels from DBSCAN, HDBSCAN, OPTICS, kk-means or any other source, and therefore lists dbscan only as a suggested package. The only dependencies are FNN [3], for the nearest-neighbour search that defines the core distances, and Rcpp [7], for the compiled spanning-tree step. The computation is deterministic and single-threaded; this keeps resource use predictable and lets users parallelise over candidate clusterings, which is where parallelism pays off in a parameter search. Inputs are validated, with informative errors for empty data, mismatched lengths of X and labels, and min_points < 2.

Documentation and tests. Every exported function has a help page with an example, a vignette (vignette("discoCVI")) walks through the workflow of the next section, and the test suite checks the values of all exported functions (see the implementation section). Bugs and feature requests can be reported on GitHub (https://github.com/aminentezari/discoCVI/issues).

A typical workflow

We illustrate the workflow with two interleaving half-moons and 40 points of uniform noise.

library(discoCVI)
library(dbscan)

set.seed(42)
moons <- function(n, sd = 0.08) {
    t1 <- runif(n / 2, 0, pi); t2 <- runif(n / 2, 0, pi)
    rbind(cbind(cos(t1), sin(t1)), cbind(1 - cos(t2), 0.5 - sin(t2))) +
        matrix(rnorm(2 * n, sd = sd), ncol = 2)
}
X <- rbind(moons(600), cbind(runif(40, -1.5, 2.5), runif(40, -1, 1.5)))

Scoring a clustering. We cluster the data with HDBSCAN. Since dbscan labels noise as 0 and DISCO expects −1, the labels are converted first; passing them unchanged would silently treat all noise points as one extra cluster.

labels <- hdbscan(X, minPts = 10)$cluster
labels[labels == 0] <- -1L
table(labels)
#> labels
#> -1 1 2
#> 32 304 304

disco_score(X, labels)
#> [1] 0.4438417

disco_score(X, kmeans(X, centers = 2, nstart = 10)$cluster)
#> [1] 0.1017555

DISCO rates the HDBSCAN result, which follows the moons and separates the scattered points as noise, higher than the k-means partition, which cuts across the moons.

DISCO is considerably stricter than the silhouette coefficient: values close to 1 are rare, and good clusterings typically score well below what the silhouette would suggest. Its rules of thumb therefore do not apply, and DISCO is best used, as here, to compare clusterings of the same data.

Choosing a parameter. Because DISCO needs no ground truth, it can be used to select the parameter of the clustering algorithm.

score_minpts <- function(m) {
    lab <- hdbscan(X, minPts = m)$cluster
    lab[lab == 0] <- -1L
    disco_score(X, lab)
}
grid <- c(3, 5, 10, 20, 50)
round(sapply(grid, score_minpts), 3)
#> [1] -0.213 0.445 0.444 0.442 0.365

The min_points argument of disco_score() is a different parameter: it is the neighbourhood size DISCO uses to measure density (default 5, as in the original paper) and need not equal the minPts of the clustering. Here minPts values from 5 to 20 give almost the same score, so the choice of 10 above is not critical, whereas minPts = 3 is clearly worse.

Inspecting points. Pointwise scores show where a clustering is convincing and where it is not (Figure 1). For noise points, p_noise() shows which noise labels are least convincing, that is, which points lie in a dense region or are density-connected to a cluster.

Figure 1. Pointwise DISCO scores of the HDBSCAN clustering. Colours run from red (score −1) through yellow (0) to blue (+1), so light-blue points are well placed and yellowish points are borderline; crosses mark points labelled as noise.

s <- disco_samples(X, labels)
nz <- p_noise(X, labels)
noise <- data.frame(point = which(labels == -1),
                    p_sparse = nz$p_sparse, p_far = nz$p_far)
head(noise[order(pmin(noise$p_sparse, noise$p_far)), ], 3)

#>   point      p_sparse        p_far
#> 1   117 -0.025553586 -0.025553586
#> 31  638 -0.005671184 -0.005671184
#> 2   347  0.025974304  0.025974304

For these points the two components coincide: this happens when the dc-distance from a noise point to the closest cluster equals its own core distance, so that both scores compare the same quantities.

Implementation: DISCO without an n-by-n matrix

Key observation

Sort the n−1n-1 edges of the MST by increasing weight and add them one at a time, merging the two groups of points they connect (Kruskal order (Kruskal, [13]). This produces the single-linkage dendrogram of the mutual-reachability graph (Gower and Ross, [10]): a binary tree whose nn leaves are the points and whose n−1n-1 internal nodes are the merges, each with height wvw_v equal to the weight of the corresponding edge.

Lemma. For two points x≠yx \ne y, ddc(x,y)=wvd_{dc}(x,y) = w_v, where vv is the lowest common ancestor of xx and yy in the merge tree.

Proof. The MST path between xx and yy is unique, and xx and yy end up in the same group exactly when the last edge of that path is added. Since edges are added in increasing order, this is the largest edge on the path, which is ddc(x,y)d_{dc}(x,y), and it is the edge that creates vv. □

Now fix a point xx and let v1,…,vrv_1,\ldots,v_r be its ancestors, from its parent up to the root, and sks_k the child of vkv_k that does not contain xx. The sets of leaves below s1,…,srs_1,\ldots,s_r partition X∖{x}X\setminus\{x\}, and by the Lemma every point below sks_k is at dc-distance exactly wvkw_{v_k} from xx. As in the definition, the MST and the merge tree are built over all nn points, noise included; noise points only affect which leaves are counted. Writing cC(s)c_C(s) for the number of points of cluster CC below node ss, we obtain

SC(x)=∑y∈Cddc(x,y)=∑k=1rwvkcC(sk),mC(x)=min⁡{wvk:cC(sk)>0}.S_C(x)=\sum_{y\in C}d_{dc}(x,y)=\sum_{k=1}^{r}w_{v_k}c_C(s_k),\qquad m_C(x)=\min\{w_{v_k}:c_C(s_k)>0\}.

Both quantities satisfy a simple recursion from the root down: for a node uu with parent vv and sibling ss,

SC(u)=SC(v)+wvcC(s),mC(u)={min⁡{mC(v),wv}if cC(s)>0,mC(v)otherwise.S_C(u)=S_C(v)+w_vc_C(s),\qquad m_C(u)= \begin{cases} \min\{m_C(v),w_v\} & \text{if }c_C(s)>0,\\ m_C(v) & \text{otherwise}. \end{cases}

with SC(root)=0S_C(\mathrm{root})=0 and mC(root)=∞m_C(\mathrm{root})=\infty. The same recursion with the number of noise points below ss gives the dc-distance to the closest noise point, needed in the one-cluster case. Since ddc(x,x)=0d_{dc}(x,x)=0, a(x)=SC(x)/(∣C∣−1)a(x)=S_C(x)/(|C|-1) and b(x)b(x) follows from SC′(x)/∣C′∣S_{C'}(x)/|C'|; the noise scores use mC(x)m_C(x) and the core distances. Every term of DISCO is therefore available without forming a single dc-distance explicitly.

Algorithm and complexity

The complete procedure is summarised below; internal nodes of the merge tree are numbered n+1,…,2n−1n+1,\ldots,2n-1 in the order in which they are created, so that every parent has a larger number than its children.

Input : X (n x p), labels (clusters 1..K, noise -1), mu >= 2
Output: pointwise DISCO scores rho(x_1), ..., rho(x_n)

1  handle edge cases (i) all noise and (ii) one cluster without noise
2  kappa <- core distances (distance to the (mu-1)-th other point)
3  E      <- Prim MST of d_m, computing d_m(x_i, x_j) when needed
4  sort E by weight; build the merge tree with union-find:
       each edge (i, j, w) creates node v with children
       root(i), root(j) and height w_v = w
5  bottom-up (v = n+1, ..., 2n-1):
       c_C(v) <- c_C(left) + c_C(right)    for every cluster C
       z(v)   <- z(left)   + z(right)      (number of noise points)
6  top-down (v = 2n-1, ..., n+1), for both children u of v, sibling s:
       S_C(u) <- S_C(v) + w_v * c_C(s)
       m_C(u) <- min(m_C(v), w_v) if c_C(s) > 0, else m_C(v)
       m_N(u) <- min(m_N(v), w_v) if z(s)   > 0, else m_N(v)
7  cluster points: a = S_own / (|own| - 1),
       b = min_C S_C / |C|    (or m_N in the one-cluster case (iv)),
       rho = (b - a) / max(a, b); singleton clusters -> (iii)
8  noise points: rho = min(rho_sparse(kappa), rho_far(m_C, kappa))
9  set fractions with a zero denominator to 0                         (v)

Step 2 uses FNN. Step 3 is Prim’s algorithm [19] written in C++ via Rcpp; it evaluates dm(xi,xj)d_m(x_i,x_j) on the fly and needs O(n2p)O(n^2p) time and O(n)O(n) memory. Step 4 uses union by size [23] and takes O(nlog⁡n)O(n \log n) time. Steps 5 and 6 are written in R with vectorised operations on K×(2n−1)K \times(2n-1) matrices and take O(nK)O(nK) time and memory. Beer et al. [2] state an overall complexity of O(n2)O(n^2) for DISCO, which this algorithm does not change: the running time is still dominated by the spanning tree. What changes is the memory, which drops from O(n2)O(n^2) to O(n(p+K))O(n(p+K)), and the constant factor, since no n×nn \times n matrix has to be allocated, filled or traversed. The result is exact: the only differences to a matrix-based computation come from adding the same distances in a different order.

Changes in version 0.2.0 and testing

disco_score() and disco_samples() use the merge-tree algorithm. compute_dc_distances(), which by definition returns an n×nn \times n matrix, no longer builds the mutual-reachability matrix and fills the dc-distance matrix block by block in Kruskal order instead of running a breadth-first search from every point, and p_cluster() is vectorised as a single matrix product. The interface is unchanged.

Tests. The test suite contains the functions of version 0.1.1 as a reference, with a single change: points in singleton clusters score 0, as explained below, so that both versions follow the published definition. It compares the values returned by all exported functions over random configurations: one to eight dimensions, μ\mu from 2 to 10, with and without noise, singleton clusters, one cluster plus noise, mostly-noise labellings and random labels. All agree to within 10−1010^{-10}; observed differences are of the order of 10−1510^{-15}.

Singleton clusters. The DISCO definition assigns score 0 to points in singleton clusters [2 Section 3.1], as does the silhouette function of scikit-learn used by the reference implementation. Version 0.1.1 set a(x)=0a(x)=0 for such points and therefore returned 1. Version 0.2.0 follows the definition; labellings without singleton clusters are unaffected.

Performance

Comparison with the previous version

Setup. We compared discoCVI 0.1.1 (from CRAN) and 0.2.0 on synthetic data: three Gaussian clusters in two dimensions plus 5% uniform noise, labelled with the generating labels so that only DISCO is measured, with nn from 500 to 100,000 and μ=5\mu=5. Version 0.1.1 was run up to n=4,000n=4,000, beyond which it does not fit comfortably in memory. Every measurement was a separate Rscript process. Peak memory is the maximum resident set size of the process (reported by /usr/bin/time -l), which includes R itself (about 67 MB) and the C++ code. Energy was measured with CodeCarbon [6] around the whole process, and the median energy of a baseline process that generates the data without computing DISCO was subtracted. Each configuration was run five times in random order, after a warm-up; we report medians. Both versions returned identical scores for every nn. The machine was a 2023 MacBook Pro with an Apple M2 Pro chip and 16 GB of memory, running macOS 27, R 4.5.3, FNN 1.1.4.1, Rcpp 1.1.2 and CodeCarbon 3.2.8 (Python 3.10), using a single thread.

Time. Version 0.2.0 is 23 times faster at n=500n=500 and 138 times faster at n=4,000n=4,000 (Table 1, Figure 2). Both versions scale roughly quadratically; fitted log-log slopes are 2.1 for version 0.1.1 (500 to 4,000 points) and 1.9 for version 0.2.0 (8,000 to 100,000 points). The gain is a much smaller constant, not a lower complexity class: 100,000 points take about 50 seconds.

Figure 2. Time to compute the DISCO score as a function of the number of points (log-log scale). Points are medians and bars the range over five runs.

ntime 0.1.1 (s)time 0.2.0 (s)speed-upmemory 0.1.1 (MB)memory 0.2.0 (MB)energy 0.1.1 (mWh)energy 0.2.0 (mWh)
5000.2490.01123x118910.260.04
1,0001.0040.02246x200921.320.16
2,0004.3090.05381x377893.990.13
4,00018.5540.134138x12229344.890.25
8,000–0.407––98–0.58
16,000–1.433––109–1.58
32,000–5.344––125–5.90
64,000–20.319––162–44.47
100,000–49.944––198–105.99

Table 1. Median DISCO computation time, peak memory of the R process, and energy above the baseline, over five runs. Version 0.1.1 was not run beyond 4,000 points.

Memory. The memory of version 0.1.1 grows rapidly, from 118 MB at n=500n=500 to 1,222 MB at n=4,000n=4,000. Version 0.2.0 stays within about 30 MB of R’s own footprint up to n=8,000n=8,000 and needs 198 MB in total at n=100,000n=100,000 (Figure 3).

Figure 3. Peak memory (maximum resident set size) of the whole R process; the dashed line marks the memory used by R itself. Points are medians and bars the range over five runs.

Energy. At n=4,000n = 4,000, one evaluation used 44.9 mWh with version 0.1.1 and 0.26 mWh with version 0.2.0 (Figure 4). For long runs the average power was similar for both versions (about 8 W), so the energy saving follows the time saving. For the same energy budget of about 45 mWh, version 0.1.1 scores 4,000 points and version 0.2.0 scores 64,000. Energy values for runs shorter than a fraction of a second are close to the resolution of software-based measurement and should be read as indicative only.

Figure 4. Energy per DISCO evaluation measured with CodeCarbon, minus the baseline process (log-log scale). The dashed line marks the energy of version 0.1.1 at 4,000 points, which version 0.2.0 reaches only at 64,000 points.

Comparison with the reference implementation

We also ran the original Python implementation of Beer et al. [2] and discoCVI 0.2.0 on the same data files (the same generator as above, with nn from 500 to 8,000, plus one dataset of 500 points that contains a singleton cluster), each in its own process, three times per dataset. Only the DISCO computation was timed; peak memory is again the maximum resident set size of the whole process. The reference code uses three functions from scikit-learn, whose compiled dependencies could not be loaded on macOS 27; we replaced them by NumPy implementations of the same formulas, which agreed with scikit-learn to within 3×10−153 \times10^{-15} on test data on a system where scikit-learn runs. All code specific to DISCO was the authors’ original.

The pointwise scores of the two implementations agree to within 3×10−133 \times10^{-13} on every dataset (Table 2), including the dataset with a singleton cluster (7×10−147 \times10^{-14}), which confirms the correction described above. discoCVI is 2.9 times faster at n=500n = 500 and 8.7 times faster at n=8,000n = 8{,}000. The memory of the Python implementation grows with n2n^2 and reaches 1.1 GB at n=8,000n = 8{,}000, whereas discoCVI needs 96 MB, most of which is R itself.

nntime Python (s)time discoCVI (s)speed-upmemory Python (MB)memory discoCVI (MB)max. difference
5000.0320.0112.9x68881.4e-14
1,0000.0840.0233.6x103943.4e-14
2,0000.2620.0564.7x211936.4e-14
4,0000.9190.1307.1x420931.5e-13
8,0003.5330.4058.7x1134962.5e-13

Table 2. Original Python implementation versus discoCVI 0.2.0 on identical data: median time of the DISCO computation, peak memory of the whole process, and the largest absolute difference between the pointwise scores.

Limitations

The running time is quadratic in nn, so very large datasets (several hundred thousand points) remain slow even though memory is no longer a constraint. The package uses a single thread. DISCO is defined for any dissimilarity [2], whereas discoCVI currently supports Euclidean distances on numeric data; since the merge-tree passes need only the spanning tree, other dissimilarities would only require a different spanning-tree step. The benchmarks were run on one machine with synthetic two-dimensional data, and energy was measured in software, so absolute numbers depend on hardware; the comparisons are nevertheless paired (same data, same machine, interleaved runs), and the equality of the scores is verified by the test suite rather than by the benchmarks alone.

Discussion

The merge-tree formulation removes the memory barrier of DISCO and makes the index practical for datasets of tens of thousands of points on a laptop, with results that match both the previous version and the original implementation. In parameter searches the savings multiply: scoring 20 candidate clusterings of 4,000 points takes about six minutes and 0.9 Wh with version 0.1.1, and about three seconds and 5 mWh with version 0.2.0.

The remaining cost is the quadratic minimum spanning tree. In low dimensions, dual-tree Borůvka algorithms compute the Euclidean MST in close to O(nlog⁡n)O(n \log n) time [15] and are used to accelerate HDBSCAN [16]; the same idea applies to mutual-reachability distances and would combine directly with the merge-tree passes described here. When DISCO is computed for an HDBSCAN result with the same value of μ\mu, the spanning tree built by the clustering itself could also be reused. Both are planned for future versions.

Summary

discoCVI provides the DISCO index in R through a small interface of plain functions that works with labels from any clustering algorithm. Since version 0.2.0 it computes DISCO exactly from the merge tree of the mutual-reachability minimum spanning tree, without storing any n×nn \times n matrix. It agrees with the original Python implementation, follows the published definition for singleton clusters, is up to two orders of magnitude faster than its previous version and up to nine times faster than the reference implementation, and scores 100,000 points in under a minute with less than 200 MB of memory. The package is available from CRAN; the benchmark scripts and data are in its source repository at https://github.com/aminentezari/discoCVI.

Acknowledgements

The author thanks Anna Beer, Lena Krieger and Pascal Weber for the original Python implementation of DISCO, and Davide Chicco for supervising the development of version 0.1 of discoCVI.

References

  1. [1]Anna Beer, Andrew Draganov, Ellen Hohma, Philipp Jahn, Christian M. M. Frey, and Ira Assent. Connecting the dots – density-connectivity distance unifies DBSCAN, k-center and spectral clustering. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 80–92, 2023. doi: 10.1145/3580305.3599283.DOI
  2. [2]Anna Beer, Lena Krieger, Pascal Weber, Martin Ritzert, Ira Assent, and Claudia Plant. Internal evaluation of density-based clusterings with noise. In The Fourteenth International Conference on Learning Representations (ICLR), 2026. URL https://openreview.net/forum?id=izbBFuHtAX.arxiv.org/abs/2503.00127
  3. [3]Alina Beygelzimer, Sham Kakadet, John Langford, Sunil Arya, David Mount, and Shengqiao Li. FNN: Fast nearest neighbor search algorithms and applications, 2024. URL https://CRAN.R-project.org/package=FNN. R package version 1.1.4.1.
  4. [4]Ricardo J. G. B. Campello, Davoud Moulavi, and Jörg Sander. Density-based clustering based on hierarchical density estimates. In Advances in Knowledge Discovery and Data Mining (PAKDD), volume 7819 of Lecture Notes in Computer Science, pages 160–172. Springer, 2013. doi: 10.1007/978-3-642-37456-2_14.DOI
  5. [5]Davide Chicco, Giuseppe Sabino, Luca Oneto, and Giuseppe Jurman. The DBCV index is more informative than DCSI, CDbw, and VIASCKDE indices for unsupervised clustering internal assessment of concave-shaped and density-based clusters. PeerJ Computer Science, 11:e3095, 2025. doi: 10.7717/peerj-cs.3095.DOI
  6. [6]Benoît Courty, Victor Schmidt, Sasha Luccioni, et al. CodeCarbon: Estimate and track carbon emissions from machine learning computing, 2026. URL https://github.com/mlco2/codecarbon. Python package version 3.2.8.
  7. [7]Dirk Eddelbuettel and Romain François. Rcpp: Seamless R and C++ integration. Journal of Statistical Software, 40(8):1–18, 2011. doi: 10.18637/jss.v040.i08.
  8. [8]Amin Entezari. discoCVI: Implementation of the DISCO metric for internal clustering evaluation, 2026. URL https://CRAN.R-project.org/package=discoCVI. R package version 0.2.1.DOI
  9. [9]Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD), pages 226–231, 1996. URL https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf.
  10. [10]J. C. Gower and G. J. S. Ross. Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society. Series C (Applied Statistics), 18(1):54–64, 1969. doi: 10.2307/2346439.DOI
  11. [11]Michael Hahsler, Matthew Piekenbrock, and Derek Doran. dbscan: Fast density-based clustering with R. Journal of Statistical Software, 91(1):1–30, 2019. doi: 10.18637/jss.v091.i01.
  12. [12]T. C. Hu. The maximum capacity route problem. Operations Research, 9(6):898–900, 1961. doi: 10.1287/opre.9.6.898.DOI
  13. [13]Joseph B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1):48–50, 1956. doi: 10.1090/S0002-9939-1956-0078686-7.DOI
  14. [14]Loïc Lannelongue, Jason Grealey, and Michael Inouye. Green algorithms: Quantifying the carbon footprint of computation. Advanced Science, 8(12):2100707, 2021. doi: 10.1002/advs.202100707.DOI
  15. [15]William B. March, Parikshit Ram, and Alexander G. Gray. Fast Euclidean minimum spanning tree: Algorithm, analysis, and applications. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 603–612, 2010. doi: 10.1145/1835804.1835882.DOI
  16. [16]Leland McInnes and John Healy. Accelerated hierarchical density based clustering. In 2017 IEEE International Conference on Data Mining Workshops (ICDMW), pages 33–42, 2017. doi: 10.1109/ICDMW.2017.12.DOI
  17. [17]Davoud Moulavi, Pablo A. Jaskowiak, Ricardo J. G. B. Campello, Arthur Zimek, and Jörg Sander. Density-based clustering validation. In Proceedings of the 2014 SIAM International Conference on Data Mining, pages 839–847, 2014. doi: 10.1137/1.9781611973440.96.DOI
  18. [18]Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, et al. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011. URL https://jmlr.org/papers/v12/pedregosa11a.html.arxiv.org/abs/1201.0490
  19. [19]R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6):1389–1401, 1957. doi: 10.1002/j.1538-7305.1957.tb01515.x.DOI
  20. [20]Peter J. Rousseeuw. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20:53–65, 1987. doi: 10.1016/0377-0427(87)90125-7.DOI
  21. [21]Roy Schwartz, Jesse Dodge, Noah A. Smith, and Oren Etzioni. Green AI. Communications of the ACM, 63(12):54–63, 2020. doi: 10.1145/3381831.DOI
  22. [22]Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in NLP. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3645–3650, 2019. doi: 10.18653/v1/P19-1355.DOI
  23. [23]Robert E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215–225, 1975. doi: 10.1145/321879.321884.DOI

Paper details

vlnc:W_nn6zamm8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents