With more people accessing Online Social Networks (OSN) using their mobile devices, location-based features have become an important part of the social networking. In this paper, we present the first measurement study of a new category of location-based online social networking services, a location-based social discovery (LBSD) network, that enables users to discover and communicate with nearby people. Unlike popular check-in-based social networks, LBSD allows users to publicly reveal their locations without being associ- ated to a specific “venue” and their usage is not influenced by the incentive mechanisms of the underlying virtual community. By analyzing over 8 million user profiles and around 150 million location updates collected from a popular new LBSD network, we first present the characteristics of spatial- temporal usage patterns of the observed users, showing that 40% of updates are from the user’s primary location and 80% are from their top 10 locations. We identify events that trigger bursts of growth in subscriber numbers, showing the importance of social media marketing. Finally, we investigate how usage patterns may be utilized to re-identify individuals with e.g. different identifiers or from datasets belonging to different online services. We evaluate re-identification by usage, spatial and spatial-temporal patterns and using a number of metrics and show that the best results can be achieved using location data, with a high accuracy: our experiments demonstrate that we can re-identify up-to 85% of users with a precision of 77% using monitored spatial data. Overall, we find that although users exhibit strong periodic behavior in their usage pattern and movements, the success rate of re-identification is highly dependent on the level of activeness and the lifetime of the users in the network.