Disclosure-free GPS trace search in smartphone networks

Abstract

In this paper we present a powerful distributed framework for finding similar trajectories in a smart phone network, without disclosing the traces of participating users. Our framework, coined Smart Trace, exploits opportunistic and participatory sensing in order to quickly answer queries of the form: "Report the users that move more similar to Q, where Q is some query trace". Smart Trace, relies on an in-situ data storage model, where geo-location data is recorded locally on smart phones for both performance and data-disclosure reasons. Smart Trace then deploys an efficient top-K query processing algorithm that exploits distributed trajectory similarity measures, resilient to spatial and temporal noise, in order to derive the most relevant answers to Q quickly and efficiently. We assess our ideas with realistic and real workloads from Microsoft Research Asia and other sources. Our study reveals that Smart Trace computes the desired results with 74% less energy consumption and 13% faster than its centralized and decentralized counterparts. Our experimental results also confirm our analytical study. © 2011 IEEE.