In this paper we explore the notion of mobile users' similarity as a key enabler of innovative applications hinging on opportunistic mobile encounters. In particular, we analyze the performance of known similarity metrics, applicable to our problem domain, as well as propose a novel temporal-based metric, in an attempt to quantify the inherently qualitative notion of similarity. Towards this