arXiv:2408.17153v2 Announce Type: replace-cross Abstract: In the era of Big Data, scalable and accurate clustering algorithms for high-dimensional data are essential. We present new Bayesian Distance Clustering (BDC) models and inference algorithms with improved scalability while maintaining the predictive accuracy of modern Bayesian nonparametric models. Unlike traditional methods, BDC models the distance between observations rather than the observations directly, offering a compromise between the scalability of distance-based methods and the enhanced predictive power and probabilistic interpretation of model-based methods. However, existing BDC models still rely on performing inference on the partition model to group observations into clusters. The support of this partition model grows exponentially with the dataset's size, complicating posterior space exploration and leading to many costly likelihood evaluations. Inspired by $k$-medoids, we propose using tessellations in discrete space to simplify inference by focusing the learning task on finding the best tessellation centers, or "medoids". Additionally, we extend our models to effectively handle multi-view data, such as data comprised of clusters that evolve across time, enhancing their applicability to complex datasets. The real data application in numismatics demonstrates the efficacy of our approach.