Capturing similarity among cells is the core of many tasks in single-cell transcriptomics, such as the identification of cell types and cell states. This problem can be formulated in a paradigm called metric learning. Metric learning aims to learn data embeddings (feature vectors) in a way that reduces the distance between feature vectors corresponding to cells belonging to the same cell type and increases the distance between the feature vectors corresponding to different cell types. Deep metric learning on the other hand uses neural networks to automatically learn discriminative features from the cells and then compute the metric. The (deep) metric learning approaches have been successfully applied to computational biology tasks like similar cell identification and synthesis of heterogeneous single-cell modalities. We identify two computational challenges: precise distance measurement between cells and scalability over a large amount of data in the applications of (deep) metric learning. And then we propose our solutions, optimal transport and coreset optimization. Empirical studies in image retrieval and clustering tasks show the promise of the proposed approaches. We propose to further explore the applicability of our methods to cell representation learning.