A framework for high-accuracy privacy-preserving mining

By Shipra Agrawal, Jayant R. Haritsa. 2004

234 citations recorded by the source corpus.

To preserve client privacy in the data mining process, a variety of techniques based on random perturbation of individual data records have been proposed recently. In this paper, we present FRAPP, a generalized matrix-theoretic framework of random perturbation, which facilitates a systematic approach to the design of perturbation mechanisms for privacy-preserving mining. Specifically, FRAPP is used to demonstrate that (a) the prior techniques differ only in their choices for the perturbation matrix elements, and (b) a symmetric perturbation matrix with minimal condition number can be identified, maximizing the accuracy even under strict privacy guarantees. We also propose a novel perturbation mechanism wherein the matrix elements are themselves characterized as random variables, and demonstrate that this feature provides significant improvements in privacy at only a marginal cost in accuracy. The quantitative utility of FRAPP, which applies to random-perturbation-based privacy-preserving mining in general, is evaluated specifically with regard to frequent-itemset mining on a variety of real datasets. Our experimental results indicate that, for a given privacy requirement, substantially lower errors are incurred, with respect to both itemset identity and itemset support, as compared to the prior techniques.

Subfields: Artificial Intelligence, Information Systems, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Management Science and Operations Research

Citations in the corpus

Collecting Telemetry Data Privately (2017, background): “In the context of telemetry collection one typically considers algorithms that exhibit differential privacy in the local model [12, 14, 7, 5, 3, 18], also called randomized response model [19], γ-amplification [13], or FRAPP [1].”
Composition attacks and auxiliary information in data privacy (2008, background): “Recent work has greatly expanded the applicability of differential privacy and its relaxations, both in the theoretical [15, 6, 14, 4, 28] and applied [17, 3, 25] literature.”
PrivCheck: privacy-preserving check-in data publishing for personalized location based services (2016, unknown): “• Frapp [1].”
A Random Rotation Perturbation Approach to Privacy Preserving Data Classification (2005, background): “Unclassified dataset could also be expored/published with privacy-protection if necessary.”
Privacy preserving decision tree learning over multiple parties (2007, methodology): “In data mining, several efforts have been made to preserve the privacy of individual records using randomization techniques [7] [8] [18] [29] [16] and to preserve the privacy of the database while running data mining algorithms over multiple data sources using cryptographic techniques such as…”
Answering Multi-Dimensional Analytical Queries under Local Differential Privacy (2019, background): “…or known to the server ( e.g. , how much time a user spends on a service is Trust model of LDP. Users do not trust the server and require We adopt the local model of differential privacy (LDP) [13], which is also called randomized response model [39], γ -amplification [17], or FRAPP [2]. e.g.”
Privacy-preserving data publishing: A survey of recent developments (2010, background): “The first group is local perturbation [Agrawal and Haritsa 2005], which assumes that a record owner does not trust anyone except himself and perturbs his own data record by adding noise before submission to the untrusted data publisher.”
Distributed Data Mining with Differential Privacy (2011, methodology): “Some used randomization techniques to modify data to preserve individual record’s privacy [ 9 ], [10].”
Discovering frequent patterns in sensitive data (2010, methodology): “To enable comparison, we set the parameters of our algorithms as follows: First, we set k so that f k equals the threshold θ used by [6].”
On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy (2011, methodology): “Random sampling [1, 2] has been studied as a method for privacy preserving data mining, where privacy notions other th an differential privacy were used.”
Mining Association Rules under Privacy Constraints (2008, methodology): “This matrix is termed as the “Gamma-Diagonal matrix” in [10].”
Random projection-based multiplicative data perturbation for privacy preserving distributed data mining (2006, background): “The work in [13] considered this framework again and showed how to optimally set the perturbation parameters for reconstruction while maintaining -amplification.”
Is Interaction Necessary for Distributed Private Learning? (2017, background): “Local privacy was implicitly studied in previous works under different names, like γ-amplification [4, 20] and randomized response [46].”