Search papers, labs, and topics across Lattice.
This paper introduces a novel differentially private mechanism for symbolic trajectory data, addressing the limitations of noise-addition techniques on non-numeric data. The proposed mechanism, based on the permute-and-flip approach, avoids exponential enumeration of possible trajectories by intelligently sampling low-error private words. Empirical evaluation on a real traffic dataset demonstrates up to 55% error reduction compared to existing methods, while also guaranteeing differential privacy.
Existing differential privacy methods struggle with symbolic trajectory data, but this new mechanism slashes error by up to 55% on real-world data.
Privacy techniques have been developed for data-driven systems, but systems with non-numeric data cannot use typical noise-adding techniques. Therefore, we develop a new mechanism for privatizing state trajectories of symbolic systems that may be represented as words over a finite alphabet. Such systems include Markov chains, Markov decision processes, and finite-state automata, and we protect their symbolic trajectories with differential privacy. The mechanism we develop randomly selects a private approximation to be released in place of the original sensitive word, with a bias towards low-error private words. This work is based on the permute-and-flip mechanism for differential privacy, which can be applied to non-numeric data. However, a na\"{\i}ve implementation would have to enumerate an exponentially large list of words to generate a private word. As a result, we develop a new mechanism that generates private words without ever needing to enumerate such a list. We prove that the accuracy of our mechanism is never worse than the prior state of the art, and we empirically show on a real traffic dataset that it introduces up to $55\%$ less error than the prior state of the art under a conventional privacy implementation.
