Federated Trajectory Search via a Lightweight Similarity Computation Framework

Contact tracing is one of the most effective ways of disease control during a pandemic. A typical method for contact tracing is to examine the spatio-temporal companion between the trajectories of patients and others. However, human trajectory data collected by mobile devices cannot be directly shared due to privacy. To utilize personal trajectory data in contact tracing, this paper presents a federated trajectory search engine called Fetra, which can efficiently process top-k search over a data federation composed of numerous mobile devices without uploading raw trajectories. To achieve this, we first propose a lightweight similarity measure LCTS based on spatio-temporal companion time to evaluate the similarity between trajectories. We then build a federated grid index named FGI via location anonymization. Given a query, a pruning strategy over FGI is applied to prune the candidate mobile devices dynamically. In addition, we propose a local optimization strategy to accelerate similarity computations in mobile devices. Extensive experiments on real-world dataset verify the effectiveness of LCTS and the efficiency of Fetra.