Data clustering is a very important and challenging task in Artificial Intelligence (AI) field with many applications such as bio-informatics, medical, enhancing recommendation engines or fraud detection. Among the different families of clustering algorithms, one of the most widely used is the prototypebased clustering, because of its simplicity and reasonable computational time. In this study, we propose a prototype-based clustering algorithm for relational data based on the barycentric coordinates formalism. We compared experimentally the quality of the proposed approach on artificial and real data-sets. The experiments show the high quality of the algorithm in terms of clustering results. We also showed that our approach is a significant improvement in terms of computational and memory complexity compared to the state-of-the-art approaches. We consider that these results are encouraging and pave the road to numerous applications in data clustering.