Skip to Main content Skip to Navigation
New interface
Conference papers

Differentially Private Sequential Data Publication via Variable-Length N-Grams

Rui Chen 1 Gergely Acs 2 Claude Castelluccia 2 
2 PLANETE - Protocols and applications for the Internet
Inria Grenoble - Rhône-Alpes, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Sequential data is being increasingly used in a variety of applications. Publishing sequential data is of vital importance to the advancement of these applications. However, as shown by the re-identi cation attacks on the AOL and Netflix datasets, releasing sequential data may pose considerable threats to individual privacy. Recent research has indicated the failure of existing sanitization techniques to provide claimed privacy guarantees. It is therefore urgent to respond to this failure by developing new schemes with provable privacy guarantees. Diff erential privacy is one of the only models that can be used to provide such guarantees. Due to the inherent sequentiality and high-dimensionality, it is challenging to apply di erential privacy to sequential data. In this paper, we address this challenge by employing a variable-length n-gram model, which extracts the essential information of a sequential database in terms of a set of variable-length n-grams. Our approach makes use of a carefully designed exploration tree structure and a set of novel techniques based on theMarkov assumption in order to lower the magnitude of added noise. The published ngrams are useful for many purposes. Furthermore, we develop a solution for generating a synthetic database, which enables a wider spectrum of data analysis tasks. Extensive experiments on real-life datasets demonstrate that our approach substantially outperforms the state-of-the-art techniques.
Document type :
Conference papers
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Claude Castelluccia Connect in order to contact the contributor
Submitted on : Friday, November 2, 2012 - 11:28:19 AM
Last modification on : Friday, February 4, 2022 - 3:19:04 AM
Long-term archiving on: : Saturday, December 17, 2016 - 7:27:01 AM


Files produced by the author(s)


  • HAL Id : hal-00747830, version 1



Rui Chen, Gergely Acs, Claude Castelluccia. Differentially Private Sequential Data Publication via Variable-Length N-Grams. ACM Computer and Communication Security (CCS), ACM, Oct 2012, Raleigh, United States. ⟨hal-00747830⟩



Record views


Files downloads