Data mining services require accurate input data for their results to be meaningful, but privacy concerns may influence users to provide spurious information. We have investigated, with respect to mining association rules, whether users can be encouraged to provide correct information by ensuring that the mining process cannot, with any reasonable degree of certainty, violate their privacy. Specifically, we have developed a scheme called MASK, based on probabilistic distortion of user data, that can simultaneously provide a high degree of privacy to the user and retain a high level of accuracy in the mining results. The performance of the scheme has been validated against representative real and synthetic datasets. A special feature of MASK is that the distortion process can be implemented at the user machine itself without having to trust any intermediate third party.

In followup work, we have found that mining the distorted database can be orders of magnitude more time-consuming as compared to mining the original database. To address this problem, we have developed an algorithm called EMASK which by (a) generalizing the distortion process to perform symbol-specific distortion, (b) appropriately chooosing the distortion parameters, and (c) applying a variety of optimizations in the reconstruction process, provides runtime efficiencies that are well within an order of magnitude of undistorted mining.

In our latest effort, we present a generalized matrix-theoretic model of random perturbation, which facilitates a systematic approach to the design of perturbation mechanisms for privacy-preserving mining. Specifically, we demonstrate that (a) the prior techniques differ only in their settings for the model parameters, and (b) through appropriate choice of parameter settings, we can derive new perturbation techniques that provide highly accurate mining results even under strict privacy guarantees. We also propose a novel perturbation mechanism wherein the model parameters are themselves characterized as random variables, and demonstrate that this feature provides significant improvements in privacy at a very marginal cost in accuracy. Our experimental results indicate that our mechanisms incur substantially lower identity and support errors as compared to the prior techniques.

• Jayant Haritsa
• Shipra Agrawal

• Vijay Krishnan
• Shariq Rizvi