Sub-trajectory Similarity Join with Obfuscation
Sub-trajectory Similarity Join with Obfuscation
复制标题
DOI：
10.1145/3468791.3468822
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Yanchuan Chang;Jianzhong Qi;E. Tanin;Xingjun Ma;H. Samet
中科院分区：
文献类型：
--
作者：
Yanchuan Chang;Jianzhong Qi;E. Tanin;Xingjun Ma;H. Samet
由于智能手机等配备GPS的设备的普及，用户轨迹数据变得越来越容易获得。许多现有的研究集中在查询轨迹是彼此相似的整体。我们观察到，部分相似的轨迹彼此包含有用的信息，用户的旅行模式，不应该被忽视。这种部分相似的轨迹在流行病接触者追踪等应用中至关重要。因此，我们建议查询的轨迹是在一个给定的距离范围内，从对方在一个给定的时间段。我们制定这个问题作为一个子轨迹相似性连接查询命名为STS-连接。我们进一步提出了一个分布式索引结构和查询算法的STS加入，用户保留他们的原始位置数据，只发送混淆的轨迹到服务器进行查询处理。这有助于保护用户位置隐私，这在处理此类数据时至关重要。理论分析和对真实的数据的实验验证了本文提出的索引结构和查询算法的有效性和高效性。
User trajectory data is becoming increasingly accessible due to the prevalence of GPS-equipped devices such as smartphones. Many existing studies focus on querying trajectories that are similar to each other in their entirety. We observe that trajectories partially similar to each other contain useful information about users’ travel patterns which should not be ignored. Such partially similar trajectories are critical in applications such as epidemic contact tracing. We thus propose to query trajectories that are within a given distance range from each other for a given period of time. We formulate this problem as a sub-trajectory similarity join query named as the STS-Join. We further propose a distributed index structure and a query algorithm for STS-Join, where users retain their raw location data and only send obfuscated trajectories to a server for query processing. This helps preserve user location privacy which is vital when dealing with such data. Theoretical analysis and experiments on real data confirm the effectiveness and the efficiency of our proposed index structure and query algorithm.