# Scalable and Distributed Silhouette Approximation

arXiv: https://arxiv.org/abs/2607.01993 · HTML: https://mlsanity.com/paper/2607.01993/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 59 references that are in the map.
- First posted on arXiv 2 Jul 2026.

## Builds on (most cited first, 12 of 12)

- [Fast and Eager k-Medoids Clustering: O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms](https://mlsanity.com/paper/2008.05171/) (2020)
- [Stop using the elbow criterion for k-means and how to choose the number of clusters instead](https://mlsanity.com/paper/2212.12189/) (2022)
- [Distributed k-Means and k-Median Clustering on General Topologies](https://mlsanity.com/paper/1306.0604/) (2013)
- [Communication Steps for Parallel Query Processing](https://mlsanity.com/paper/1306.5972/) (2013)
- [From A-to-Z Review of Clustering Validation Indices](https://mlsanity.com/paper/2407.20246/) (2024)
- [Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially](https://mlsanity.com/paper/1802.09205/) (2018)
- [Estimating the Optimal Number of Clusters in Categorical Data Clustering by Silhouette Coefficient](https://mlsanity.com/paper/2501.15542/) (2025)
- [Medoid Silhouette clustering with automatic cluster number selection](https://mlsanity.com/paper/2309.03751/) (2023)
- [Clustering Uncertain Graphs](https://mlsanity.com/paper/1612.06675/) (2016)
- [k-Means for Streaming and Distributed Big Sparse Data](https://mlsanity.com/paper/1511.08990/) (2015)
- [Accurate MapReduce Algorithms for k-median and k-means in General Metric Spaces](https://mlsanity.com/paper/1904.12728/) (2019)
- [Fully Scalable MPC Algorithms for Euclidean k-Center](https://mlsanity.com/paper/2504.16382/) (2025)

## Abstract (arXiv)

The silhouette is one of the most widely used measures to assess the quality of a k-clustering of a dataset of n elements. Its evaluation requires no information beyond the clustering assignment. In addition, the silhouette is extremely easy to interpret, providing a score to measure the quality of a clustering as a whole or for each element. The exact computation of the: (i) silhouette of each element of a dataset; and (ii) the global silhouette of the clustering; require Theta(n2) distance calculations, under general metrics. The quadratic complexity Theta(n2) is extremely prohibitive, especially on massive modern datasets. Surprisingly, existing approximate methods using O(n2) distance calculations are heuristics not offering provable and controllable guarantees on the quality of their results. We introduce the first rigorous and efficient algorithms to estimate: (i) the (local) silhouette of each element of a dataset; and (ii) the (global) silhouette; of any metric k-clustering. Our methods, based on sampling, perform O(nkvarepsilon-2ln (nk/δ)) distance computations, and provide estimates with additive error O(varepsilon) with probability at least 1-δ. That is, parameters varepsilon and δ in (0,1) control the trade-off between accuracy and efficiency. We also introduce a scalable and distributed design of our methods for the MapReduce and Massively Parallel Computing (MPC) frameworks. Our distributed algorithms use a constant number of rounds and sublinear local memory. Finally, we perform extensive experiments against state-of-the-art approaches. The results show that our new techniques yield the best trade-off between accuracy and efficiency for both local and global silhouette estimation. In addition, our methods scale efficiently to massive datasets for which an exact computation of the silhouette is not practical.