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 , 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 : 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 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 and let a clustering consist of disjoint clusters, with the remaining points labelled as noise; for a cluster point , denotes its cluster.
Distances. For a parameter (min_points in the package, default 5), the core distance is the Euclidean distance from to its -th nearest neighbour, where counts as its own first neighbour, as in the reference implementation; equivalently, it is the distance to the -th nearest other point, and is required. The mutual-reachability distance [4] is
and the dc-distance [1] is the minimax path distance in the complete graph weighted by , that is, the smallest possible value of the largest edge on a path from to , with . It equals the largest edge on the path between and 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,
Cluster points. With the mean dc-distance from to the points of , a cluster point receives
For fixed the function is non-decreasing, so the minimum is attained at the closest cluster, and is the silhouette coefficient computed on dc-distances:
As in the reference implementation, which uses the silhouette function of scikit-learn [18], the within-cluster mean is taken over the other members of .
Noise points. With the core-distance threshold of a cluster and , a noise point receives the minimum of two scores,
is positive if is sparser than every cluster, and is positive if is not density-connected to any cluster.
Edge cases ([2 Section 3.1]). (i) If all points are noise, every score is . (ii) If there is a single cluster and no noise, every score is . (iii) Points in singleton clusters score . (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. is replaced by . (v) If a denominator is zero, for example when more than duplicate points have core distance , the corresponding fraction is set to .
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 ;disco_samples(X, labels, min_points = 5)returns the pointwise scores ;p_cluster()andp_noise()return the two components of the score for cluster points and noise points (p_noise()returns and 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.
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, -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 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 leaves are the points and whose internal nodes are the merges, each with height equal to the weight of the corresponding edge.
Lemma. For two points , , where is the lowest common ancestor of and in the merge tree.
Proof. The MST path between and is unique, and and 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 , and it is the edge that creates . □
Now fix a point and let be its ancestors, from its parent up to the root, and the child of that does not contain . The sets of leaves below partition , and by the Lemma every point below is at dc-distance exactly from . As in the definition, the MST and the merge tree are built over all points, noise included; noise points only affect which leaves are counted. Writing for the number of points of cluster below node , we obtain
Both quantities satisfy a simple recursion from the root down: for a node with parent and sibling ,
with and . The same recursion with the number of noise points below gives the dc-distance to the closest noise point, needed in the one-cluster case. Since , and follows from ; the noise scores use 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 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 on the fly and needs time and memory. Step 4 uses union by size [23] and takes time. Steps 5 and 6 are written in R with vectorised operations on matrices and take time and memory. Beer et al. [2] state an overall complexity of 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 to , and the constant factor, since no 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 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, from 2 to 10, with and without noise, singleton clusters, one cluster plus noise, mostly-noise labellings and random labels. All agree to within ; observed differences are of the order of .
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 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 from 500 to 100,000 and . Version 0.1.1 was run up to , 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 . 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 and 138 times faster at (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.
| n | time 0.1.1 (s) | time 0.2.0 (s) | speed-up | memory 0.1.1 (MB) | memory 0.2.0 (MB) | energy 0.1.1 (mWh) | energy 0.2.0 (mWh) |
| 500 | 0.249 | 0.011 | 23x | 118 | 91 | 0.26 | 0.04 |
| 1,000 | 1.004 | 0.022 | 46x | 200 | 92 | 1.32 | 0.16 |
| 2,000 | 4.309 | 0.053 | 81x | 377 | 89 | 3.99 | 0.13 |
| 4,000 | 18.554 | 0.134 | 138x | 1222 | 93 | 44.89 | 0.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 to 1,222 MB at . Version 0.2.0 stays within about 30 MB of R’s own footprint up to and needs 198 MB in total at (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 , 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 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 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 on every dataset (Table 2), including the dataset with a singleton cluster (), which confirms the correction described above. discoCVI is 2.9 times faster at and 8.7 times faster at . The memory of the Python implementation grows with and reaches 1.1 GB at , whereas discoCVI needs 96 MB, most of which is R itself.
| time Python (s) | time discoCVI (s) | speed-up | memory Python (MB) | memory discoCVI (MB) | max. difference | |
| 500 | 0.032 | 0.011 | 2.9x | 68 | 88 | 1.4e-14 |
| 1,000 | 0.084 | 0.023 | 3.6x | 103 | 94 | 3.4e-14 |
| 2,000 | 0.262 | 0.056 | 4.7x | 211 | 93 | 6.4e-14 |
| 4,000 | 0.919 | 0.130 | 7.1x | 420 | 93 | 1.5e-13 |
| 8,000 | 3.533 | 0.405 | 8.7x | 1134 | 96 | 2.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 , 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 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 , 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 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]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]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]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]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]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]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]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]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]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]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]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]T. C. Hu. The maximum capacity route problem. Operations Research, 9(6):898–900, 1961. doi: 10.1287/opre.9.6.898.DOI
- [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]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]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]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]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]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]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]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]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]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]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



