The most widely used internal measure for clustering evaluation is the\nsilhouette coefficient, whose naive computation requires a quadratic number of\ndistance calculations, which is clearly unfeasible for massive datasets.\nSurprisingly, there are no known general methods to efficiently approximate the\nsilhouette coefficient of a clustering with rigorously provable high accuracy.\nIn this paper, we present the first scalable algorithm to compute such a\nrigorous approximation for the evaluation of clusterings based on any metric\ndistances. Our algorithm hinges on a Probability Proportional to Size (PPS)\nsampling scheme, and, for any fixed $\\varepsilon, \\delta \\in (0,1)$, it\napproximates the silhouette coefficient within a mere additive error\n$O(\\varepsilon)$ with probability $1-\\delta$, using a very small number of\ndistance calculations. We also prove that the algorithm can be adapted to\nobtain rigorous approximations of other internal measures of clustering\nquality, such as cohesion and separation. Importantly, we provide a distributed\nimplementation of the algorithm using the MapReduce model, which runs in\nconstant rounds and requires only sublinear local space at each worker, which\nmakes our estimation approach applicable to big data scenarios. We perform an\nextensive experimental evaluation of our silhouette approximation algorithm,\ncomparing its performance to a number of baseline heuristics on real and\nsynthetic datasets. The experiments provide evidence that, unlike other\nheuristics, our estimation strategy not only provides tight theoretical\nguarantees but is also able to return highly accurate estimations while running\nin a fraction of the time required by the exact computation, and that its\ndistributed implementation is highly scalable, thus enabling the computation of\ninternal measures for very large datasets for which the exact computation is\nprohibitive.\n