Abstract An important challenge for mobility analysis is the development of techniques that can associate users’ identities across multiple datasets. These can assist in developing hybrid sensing and tracking mechanisms across large urban spaces, inferring context by combining multiple datasets, but at the same time have important implications for privacy. In this paper we present a scheme to associate different identities of a person across two movement databases. Our two key contributions are the reformulation of this problem in terms of a two-class classification, and the development of efficient techniques for pruning the search space. We evaluate performance of the scheme on synthetic and real data from two co-located city-wide WiFi and Bluetooth networks, and show that the pruning has a remarkable effect on the performance of the scheme in identifying individuals across two distinct mobility datasets. Finally, we discuss the privacy implications of this scheme in the light of our findings.