Secure Synchronized Spatio-Temporal Trajectory Similarity Search
Yiping Teng, Jiawei Qi, Lei Liu, Shiqing Wang, Li Hong Xu, Chunlong Fan · 2023
Attracting research interests and applications in academic and industrial community due to the proliferation of mobile devices, computation and processing services on spatiotemporal trajectory data has usually been outsourced to cloud platforms to save the costs of data storage, computation and management. To prevent the privacy leakage of trajectories from the direct data outsourcing, in this paper, we study the secure similarity search problem on spatio-temporal trajectories and present a secure synchronized spatio-temporal trajectory similarity search approach. In the approach, adopting the Matching Point-point distance Similarity (MPS) measurement, we first propose a Secure Matching Point-point Distance Similarity Computation (SMPSC) Protocol to support the secure similarity calculation on encrypted trajectories. To improve the computational performance, we further propose a Secure Grid Filtering (SGF) method by matching spatio-temporal grid codes to filter the dissimilar trajectories based on the distance threshold in MPS. At last, with SMPSC protocol and SGF method, we propose a Secure Synchronized Spatio-Temporal Trajectory similarity Search Processing (S3TS) method to retrieve similar trajectories based on MPS measurement. We theoretically analyze the computational complexity and security guarantees of the presented approach, and conduct extensive experiments on real and synthetic datasets to demonstrate its search performance.