title: Differentially Private Frequent Sequence Mining via Sampling-based Candidate Pruning.
abstract: In this paper, we study the problem of mining frequent sequences under the rigorous differential privacy model. We explore the possibility of designing a differentially private frequent sequence mining (FSM) algorithm which can achieve both high data utility and a high degree of privacy. We found, in differentially private FSM, the amount of required noise is proportionate to the number of candidate sequences. If we could effectively reduce the number of unpromising candidate sequences, the utility and privacy tradeoff can be significantly improved. To this end, by leveraging a sampling-based candidate pruning technique, we propose a novel differentially private FSM algorithm, which is referred to asPFS2. The core of our algorithm is to utilize sample databases to further prune the candidate sequences generated based on the downward closure property. In particular, we use the noisy local support of candidate sequences in the sample databases to estimate which sequences are potentially frequent. To improve the accuracy of such private estimations, a sequence shrinking method is proposed to enforce the length constraint on the sample databases. Moreover, to decrease the probability of misestimating frequent sequences as infrequent, a threshold relaxation method is proposed to relax the user-specified threshold for the sample databases. Through formal privacy analysis, we show that ourPFS2algorithm isε-differentially private. Extensive experiments on real datasets illustrate that ourPFS2algorithm can privately find frequent sequences with high accuracy.
authors.affiliation: State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing, China.
authors.forename: Shengzhi
authors.initials: S
authors.lastname: Xu
authors.affiliation: State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing, China.
authors.forename: Sen
authors.initials: S
authors.lastname: Su
authors.affiliation: State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing, China.
authors.forename: Xiang
authors.initials: X
authors.lastname: Cheng
authors.affiliation: State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing, China.
authors.forename: Zhengyi
authors.initials: Z
authors.lastname: Li
authors.affiliation: Math and Computer Science Department, Emory University, Atlanta, GA.
authors.forename: Li
authors.initials: L
authors.lastname: Xiong