Effective Privacy-Preserving Calculation of Transition Probabilities Using Sampling Techniques

Recent advances in GPS technology have made it possible to collect user location information. However, location data often contain sensitive information and raise significant privacy concerns. Differential privacy methods, like Geo-Indistinguishability, protect user privacy by adding noise to location data, but managing the privacy budget while maintaining data utility remains challenging. This paper proposes a method to effectively calculate transition probabilities, a key metric in various location-based services, from differentially private location data by using sampling techniques to collect partial location data, thereby effectively handling the privacy budget and ensuring data utility. Especially, we introduce a user distribution-based sampling method to secure sufficient data for accurate transition probability calculations. The main contributions of this study are twofold: first, utilizing sampling techniques to enhance data utility while optimizing the privacy budget; second, introducing a user distribution-based sampling method for adequate data collection. Experimental results with real-world data demonstrate that the proposed method improves the accuracy of transition probability calculations compared to existing solutions.