P-STM: privacy-protected Social Tie Mining of individual trajectories

Shuo Wang, Surya Nepal, Richard Sinnott, Carsten Rudolph

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

11 Citations (Scopus)


With the prevalence of location-aware devices and applications, enormous volumes of human spatiotemporal trajectories are being produced. It is feasible to estimate the similarity between user movement patterns according to such trajectories, which can be regarded as a potential social tie between users. There are two key research challenges associated with social tie discovery from trajectories: (1) trajectories contain users' accurate locations and releasing such data for social tie discovery raises serious privacy concerns; (2) trajectories are archived as discrete approximations of actual movement patterns using different sampling strategies and rates which are intrinsically heterogeneous. To address these challenges, this paper proposes a Privacy-protected Social Tie Mining (P-STM) approach. It provides a new social tie discovery solution based on the similarity of calibrated trajectories incorporating three key components: (1) a location entropy-based indicative dense region (IDR) mining approach to handle the heterogeneity of trajectories under differential privacy; (2) a private model-based calibration system used to rewrite trajectories using a sanitized IDR set to improve the utility of sanitized trajectories for similarity evaluation; (3) a social tie mining approach to indicate potential social ties between individuals using the similarity trajectories, which aims at finding the acquaintances for users based on solely their local geographical activities. The proposed approach is evaluated using real-world trajectory datasets from location-based social networks.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE International Conference on Web Services, IEEE ICWS 2019 - Part of the 2019 IEEE World Congress on Services, 8–13 July 2019 Milan, Italy
EditorsElisa Bertino, Carl K. Chang, Peter Chen, Ernesto Damiani, Michael Goul, Katsunori Oyama
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages10
ISBN (Electronic)9781728127170
ISBN (Print)9781728127187
Publication statusPublished - 2019
EventIEEE International Conference on Web Services 2019 - Milan, Italy
Duration: 8 Jul 201913 Jul 2019
Conference number: 26th
https://ieeexplore.ieee.org/xpl/conhome/8805195/proceeding (Proceedings)


ConferenceIEEE International Conference on Web Services 2019
Abbreviated titleICWS 2019
Internet address


  • Differential privacy
  • Privacy-preserving
  • Social ties
  • Trajectories
  • Utility

Cite this