실루엣 (silhouette)은 $n$개의 요소로 구성된 데이터셋의 $k$-클러스터링 (k-clustering) 품질을 평가하기 위해 가장 널리 사용되는 척도 중 하나입니다. 실루엣의 평가는 클러스터링 할당 정보 외에 추가적인 정보를 필요로 하지 않습니다. 또한, 실루엣은 해석이 매우 쉬워, 클러스터링 전체의 품질이나 각 요소의 품질을 측정하는 점수를 제공합니다. 일반적인 메트릭 (metric) 하에서 다음 사항을 정확하게 계산하려면: (i) 데이터셋의 각 요소의 실루엣; (ii) 클러스터링의 전역 실루엣 (global silhouette); 계산 시 $Θ(n^2)$의 거리 계산이 필요합니다. 이러한 이차 복잡도 $Θ(n^2)$는 특히 거대한 현대적 데이터셋에서는 매우 치명적입니다. 놀랍게도, $O(n^2)$의 거리 계산을 사용하는 기존의 근사 방법들은 결과의 품질에 대해 증명 가능하고 제어 가능한 보장을 제공하지 않는 휴리스틱 (heuristics)에 불과합니다. 본 논문에서는 임의의 메트릭 $k$-클러스터링에 대해 다음을 추정하는 최초의 엄격하고 효율적인 알고리즘을 소개합니다: (i) 데이터셋의 각 요소의 (지역적) 실루엣; (ii) (전역) 실루엣. 샘플링 (sampling)에 기반한 우리의 방법은 $O(nk ext{ε}^{-2} ext{ln}(nk/ ext{δ}))$ 번의 거리 계산을 수행하며, 최소 $1- ext{δ}$의 확률로 $O( ext{ε})$의 가산 오차 (additive error)를 갖는 추정치를 제공합니다. 즉, $(0,1)$ 범위 내의 파라미터 $ ext{ε}$와 $ ext{δ}$가 정확도와 효율성 사이의 트레이드오프 (trade-off)를 제어합니다. 또한, 우리는 MapReduce 및 대규모 병렬 컴퓨팅 (Massively Parallel Computing, MPC) 프레임워크를 위한 우리 방법의 확장 가능하고 분산 가능한 설계를 소개합니다. 우리의 분산 알고리즘은 상수 번의 라운드 (rounds)와 아선형 (sublinear) 로컬 메모리를 사용합니다. 마지막으로, 우리는 최신 기술(state-of-the-art)들과 비교하여 광범위한 실험을 수행합니다. 결과에 따르면, 우리의 새로운 기술은 지역적 및 전역적 실루엣 추정 모두에서 정확도와 효율성 사이의 최적의 트레이드오프를 제공합니다. 또한, 우리의 방법은 실루엣의 정확한 계산이 실용적이지 않은 거대 데이터셋에 대해서도 효율적으로 확장됩니다.