Differentially Private Frequent Sequence Mining via Sampling-based Candidate Pruning.

Area of Science:

• Computer Science
• Data Mining
• Privacy-Preserving Technologies

Background:

• Frequent sequence mining (FSM) is crucial for pattern discovery in sequential data.
• Ensuring data privacy during FSM is challenging due to the sensitive nature of the data.
• Existing differentially private FSM algorithms often struggle with a utility-privacy tradeoff.

Purpose of the Study:

• To develop a differentially private FSM algorithm that achieves high data utility and strong privacy guarantees.
• To address the challenge of noise amplification in differentially private FSM.
• To improve the efficiency and accuracy of private frequent sequence mining.

Main Methods:

• Proposed a novel algorithm, PFS2, for differentially private FSM.
• Leveraged a sampling-based candidate pruning technique using sample databases.
• Utilized noisy local support for estimating potentially frequent sequences.
• Introduced sequence shrinking and threshold relaxation methods to enhance estimation accuracy.

Main Results:

• PFS2 effectively prunes unpromising candidate sequences, reducing noise.
• The algorithm demonstrates improved accuracy in identifying frequent sequences under differential privacy.
• Experimental results on real datasets validate the algorithm's performance.

Conclusions:

• PFS2 offers a robust solution for private frequent sequence mining.
• The proposed methods significantly enhance the utility-privacy tradeoff in FSM.
• PFS2 achieves epsilon-differential privacy while maintaining high accuracy.