A differentially private algorithm for range queries on trajectories

Abstract

We propose a novel algorithm to ensure ϵ-differential privacy for answering range queries on trajectory data. In order to guarantee privacy, differential privacy mechanisms add noise to either data or query, thus introducing errors to queries made and potentially decreasing the utility of information. In contrast to the state of the art, our method achieves significantly lower error as it is the first data- and query-aware approach for such queries. The key challenge for answering range queries on trajectory data privately is to ensure an accurate count. Simply representing a trajectory as a set instead of sequence of points will generally lead to highly inaccurate query answers as it ignore..