Privacy-Preserving Similarity Queries for Outsourced Trajectory Data

Trajectory similarity query can retrieve a set of trajectories similar to the user's query from the database and is widely used in various fields such as travel recommendations. Previous studies mainly focused on accelerating trajectory similarity search in plaintext. However, with the increasing concern about privacy protection in outsourced cloud environments, conducting trajectory similarity queries while preserving privacy becomes a significant challenge. This paper proposes efficient privacy-preserving top-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> and range similarity queries over trajectory data. We leverage Discrete Synchronous Euclidean Distance (DSED) to measure the spatio-temporal similarity of trajectory data, and employ a filter-then-refine strategy to enhance efficiency. Specifically, Hilbert curve-based filtering is first applied to exclude a large portion of dissimilar trajectories, followed by homomorphic encryption-based refinement to retrieve precise results. Security analysis demonstrates that our schemes protect the privacy of trajectory data, query requests, and query results. Finally, extensive experimental results indicate that the proposed methods achieve a trade-off between data availability and privacy, achieving over 99% average precision while initially filtering out 90% of dissimilar trajectories, and improving query efficiency by at least an order of magnitude.