Secure Computing of GPS Trajectory Similarity: A Review

Location Based Services (LBS) powered apps generate a massive amount of GPS trajectory data everyday. Because many of these trajectories are similar, if not exactly the same, (e.g., people traveling together or taking the same route everyday), there is a significant amount of redundancy in the data generated. This redundant data increases storage cost and network bandwidth cost. In order to counteract this and efficiently provide the LBS, LBS providers are considering trajectory similarity computation. There are several methods reported in the literature regarding similarity in GPS trajectories, which directly work on data in the plaintext format. However, computing trajectory similarity traditionally introduces privacy and security concerns among users since the number of incidents of the privacy breaches is on the rise. Hence, researchers have recently come up with innovative ways to perform trajectory similarity operations in the encrypted domain, without revealing the actual data. These approaches increase privacy and boost user confidence, which results in more customers for LBS providers. In this paper, we review various methods proposed in the plaintext domain and in the encrypted domain for secured trajectory comparison. We also discuss potential methods for encrypted domain computing that can be used in the domain of trajectory similarity and list the open research challenges.