An Efficient and Effective Model for Preserving Privacy Data in Location-Based Graphs

Location-based services (LBSs), which are used for navigation, tracking, and mapping across digital devices and social platforms, establish a user’s position and deliver tailored experiences. Collecting and sharing such trajectory datasets with analysts for business purposes raises critical privacy concerns, as both symmetry in recurring behavior mobility patterns and asymmetry in irregular movement mobility patterns in sensitive locations collectively expose highly identifiable information, resulting in re-identification risks, trajectory disclosure, and location inference. In response, several privacy preservation models have been proposed, including k-anonymity, l-diversity, t-closeness, LKC-privacy, differential privacy, and location-based approaches. However, these models still exhibit privacy issues, including sensitive location inference (e.g., hospitals, pawnshops, prisons, safe houses), disclosure from duplicate trajectories revealing sensitive places, and the re-identification of unique locations such as homes, condominiums, and offices. Efforts to address these issues often lead to utility loss and computational complexity. To overcome these limitations, we propose a new (ξ, ϵ)-privacy model that combines data generalization and suppression with sliding windows and R-Tree structures, where sliding windows partition large trajectory graphs into simplified subgraphs, R-Trees provide hierarchical indexing for spatial generalization, and suppression removes highly identifiable locations. The model addresses both symmetry and asymmetry in mobility patterns by balancing generalization and suppression to protect privacy while maintaining data utility. Symmetry-driven mechanisms that enhance resistance to inference attacks and support data confidentiality, integrity, and availability are core requirements of cryptography and information security. An experimental evaluation on the City80k and Metro100k datasets confirms that the (ξ, ϵ)-privacy model addresses privacy issues with reduced utility loss and efficient scalability, while validating robustness through relative error across query types in diverse analytical scenarios. The findings provide evidence of the model’s practicality for large-scale location data, confirming its relevance to secure computation, data protection, and information security applications.