Differentially Private Frequent Sequence Mining.

Area of Science:

• Computer Science
• Data Mining
• Privacy-Preserving Technologies

Background:

• Frequent sequence mining (FSM) is crucial for pattern discovery in sequential data.
• Achieving rigorous differential privacy in FSM presents challenges in balancing data utility and privacy.
• Existing methods struggle with the noise-to-candidate ratio in differentially private FSM.

Purpose of the Study:

• To develop a novel differentially private frequent sequence mining (FSM) algorithm, PFS2.
• To enhance the utility-privacy tradeoff in FSM by effectively pruning candidate sequences.
• To introduce support for general gap-constrained FSM under differential privacy.

Main Methods:

• Leveraging a sampling-based candidate pruning technique using sample databases.
• Utilizing noisy local support estimates on sample databases to identify potentially frequent sequences.
• Employing gap-aware sequence shrinking, sensitivity computation, and threshold relaxation for accuracy and privacy calibration.

Main Results:

• PFS2 is formally proven to be ε-differentially private.
• The algorithm effectively prunes unpromising candidate sequences, significantly improving the privacy-utility tradeoff.
• Experiments demonstrate high accuracy in privately finding frequent sequences on real datasets.

Conclusions:

• PFS2 is the first algorithm to support general gap-constrained FSM within differential privacy.
• The proposed sampling and pruning techniques effectively mitigate the noise impact in private FSM.
• PFS2 offers a robust solution for accurate and private frequent sequence discovery.