The nearest prototype classification is a less computationally intensive\nreplacement for the $k$-NN method, especially when large datasets are\nconsidered. In metric spaces, centroids are often used as prototypes to\nrepresent whole clusters. The selection of cluster prototypes in non-metric\nspaces is more challenging as the idea of computing centroids is not directly\napplicable.\n In this paper, we present CRS, a novel method for selecting a small yet\nrepresentative subset of objects as a cluster prototype. Memory and\ncomputationally efficient selection of representatives is enabled by leveraging\nthe similarity graph representation of each cluster created by the NN-Descent\nalgorithm. CRS can be used in an arbitrary metric or non-metric space because\nof the graph-based approach, which requires only a pairwise similarity measure.\nAs we demonstrate in the experimental evaluation, our method outperforms the\nstate of the art techniques on multiple datasets from different domains.\n