Anonymization by Local Recoding in Data with Attribute Hierarchical Taxonomies
IEEE Transactions on Knowledge and Data EngineeringPublished 4 August 2008
Jiuyong Li, Raymond Chi-Wing Wong, A.W.-C. Fu, Jian Pei
Citations44
SJR quartileQ1
SJR score2.57
SNIP3.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A proper distance metric is defined to achieve local recoding generalization with small distortion of k-anonymity view and a means to control the inconsistency of attribute domains in a generalized view by local recode is proposed.
Abstract
Individual privacy will be at risk if a published data set is not properly deidentified.k-Anonymity is a major technique to deidentify a data set.Among a number of k-anonymization schemes, local recoding methods are promising for minimizing the distortion of a k-anonymity view.This paper addresses two major issues in local recoding k-anonymization in attribute hierarchical taxonomies.First, we define a proper distance metric to achieve local recoding generalization with small distortion.Second, we propose a means to control the inconsistency of attribute domains in a generalized view by local recoding.We show experimentally that our proposed local recoding method based on the proposed distance metric produces higher quality k-anonymity tables in three quality measures than a global recoding anonymization method, Incognito, and a multidimensional recoding anonymization method, Multi.The proposed inconsistency handling method is able to balance distortion and consistency of a generalized view.
Keywords
Computer Science
Choice Reviews OnlineFinding groups in data: an introduction to cluster analysis
10,614 Citations1991
International Journal of Uncertainty Fuzziness and Knowledge-Based Systemsk-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
8,492 Citations2002Latanya Sweeney
The solution provided in this paper includes a formal protection model named k-anonymity and a set of accompanying policies for deployment and examines re-identification attacks that can be realized on releases that adhere to k- anonymity unless accompanying policies are respected.
ACM SIGMOD RecordPrivacy-preserving data mining
2,993 Citations2000Rakesh Agrawal, Ramakrishnan Srikant
IEEE Transactions on Knowledge and Data EngineeringProtecting respondents identities in microdata release
2,302 Citations2001Pierangela Samarati
This paper addresses the problem of releasing microdata while safeguarding the anonymity of respondents to which the data refer and introduces the concept of minimal generalization that captures the property of the release process not distorting the data more than needed to achieve k-anonymity.
International Journal of Uncertainty Fuzziness and Knowledge-Based SystemsACHIEVING k-ANONYMITY PRIVACY PROTECTION USING GENERALIZATION AND SUPPRESSION
1,974 Citations2002Latanya Sweeney
This paper provides a formal presentation of combining generalization and suppression to achieve k-anonymity and shows that Datafly can over distort data and µ-Argus can additionally fail to provide adequate protection.
Privacy-preserving data mining
1,706 Citations2000Rakesh Agrawal, Ramakrishnan Srikant
This work considers the concrete case of building a decision-tree classifier from training data in which the values of individual records have been perturbed, and proposes a novel reconstruction procedure to accurately estimate the distribution of original data values.
Data Privacy through Optimal k-Anonymization
1,130 Citations2005Roberto J. Bayardo, R. Agrawal
This paper proposes and evaluates an optimization algorithm for the powerful de-identification procedure known as k-anonymization, and presents a new approach to exploring the space of possible anonymizations that tames the combinatorics of the problem, and develops data-management strategies to reduce reliance on expensive operations such as sorting.
Mondrian Multidimensional K-Anonymity
1,127 Citations2006Kristen LeFevre, David J. DeWitt +1 more
A new multidimensional model is proposed, which provides an additional degree of flexibility not seen in previous (single-dimensional) approaches, which leads to higher-quality anonymizations, as measured both by general-purpose metrics and more specific notions of query answerability.
Incognito
1,061 Citations2005Kristen LeFevre, David J. DeWitt +1 more
A set of algorithms for producing minimal full-domain generalizations are introduced, and it is shown that these algorithms perform up to an order of magnitude faster than previous algorithms on two real-life databases.
On the design and quantification of privacy preserving data mining algorithms
1,018 Citations2001Dakshi Agrawal, Charų C. Aggarwal
It is proved that the EM algorithm converges to the maximum likelihood estimate of the original distribution based on the perturbed data, and proposed metrics for quantification and measurement of privacy-preserving data mining algorithms are proposed.
On the complexity of optimal K-anonymity
827 Citations2004Adam Meyerson, Ryan Williams
It is proved that two general versions of optimal k-anonymization of relations are NP-hard, including the suppression version which amounts to choosing a minimum number of entries to delete from the relation.
Transforming data to satisfy privacy constraints
782 Citations2002Vijay S. Iyengar
This paper addresses the important issue of preserving the anonymity of the individuals or entities during the data dissemination process by the use of generalizations and suppressions on the potentially identifying portions of the data.
Journal of CryptologyPrivacy Preserving Data Mining
673 Citations2002Yehuda Lindell, Pinkas
This work considers a scenario in which two parties owning confidential databases wish to run a data mining algorithm on the union of their databases, without revealing any unnecessary information, and proposes a protocol that is considerably more efficient than generic solutions and demands both very few rounds of communication and reasonable bandwidth.
Privacy-preserving <i>k</i> -means clustering over vertically partitioned data
631 Citations2003Jaideep Vaidya, Chris Clifton
This work presents a method for k-means clustering when different sites contain different attributes for a common set of entities, where each site learns the cluster of each entity, but learns nothing about the attributes at other sites.
Top-Down Specialization for Information and Privacy Preservation
574 Citations2005Benjamin C. M. Fung, Ke Wang +1 more
The results show that quality of classification can be preserved even for highly restrictive privacy requirements, and has great applicability to both public and private sectors that share information for mutual benefits and productivity.
Elsevier eBooksMaintaining Data Privacy in Association Rule Mining
492 Citations2002Shariq J. Rizvi, Jayant R. Haritsa
This work presents a scheme, 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.
Data Mining and Knowledge DiscoveryOrdinal, Continuous and Heterogeneous k-Anonymity Through Microaggregation
427 Citations2005Josep Domingo‐Ferrer, Vicenç Torra
Categorical microaggregation is proposed to be used as an alternative to generalization/suppression for nominal and ordinal k-anonymization and continuousMicroaggregation as the method for continuous k-Anonymization is proposed.
Utility-based anonymization using local recoding
418 Citations2006Jian Xu, Wei Wang +4 more
This paper proposes a simple framework to specify utility of attributes and develops two simple yet efficient heuristic local recoding methods for utility-based anonymization, which outperform the state-of-the-art multidimensional global recode methods in both discernability and query answering accuracy.
Bottom-Up Generalization: A Data Mining Solution to Privacy Protection
313 Citations2005Ke Wang, Philip S. Yu +1 more
This paper investigates data mining as a technique for masking data, therefore, termed data mining based privacy protection, and adapts an iterative bottom-up generalization from data mining to generalize the data.
Lecture notes in computer scienceAnonymizing Tables
296 Citations2004Gagan Aggarwal, Tomás Feder +5 more
It is shown that the k-Anonymity problem is NP-hard even when the attribute values are ternary, and an O(k)-approximation algorithm is provided for the problem, which improves upon the previous best-known O( klog k)- approximation.
Privacy-preserving Bayesian network structure computation on distributed heterogeneous data
224 Citations2004Rebecca N. Wright, Zhiqiang Yang
An efficient and privacy-preserving version of the K2 algorithm is given to construct the structure of a Bayesian network for the parties' joint data on the combination of their databases without revealing anything about their data to each other.
Workload-aware anonymization
216 Citations2006Kristen LeFevre, David J. DeWitt +1 more
A suite of anonymization algorithms that produce an anonymous view based on a target class of workloads, consisting of one or more data mining tasks, as well as selection predicates are provided.
Lecture notes in computer scienceAchieving k-Anonymity by Clustering in Attribute Hierarchical Structures
93 Citations2006Jiuyong Li, Raymond Chi-Wing Wong +2 more
This paper defines generalisation distances between tuples to characterise distortions by generalisations and concludes that the generalisation distance is a metric distance, and proposes an efficient clustering-based algorithm for k-anonymisation.
IEEE Transactions on Knowledge and Data EngineeringPrivacy-Preserving Kth Element Score over Vertically Partitioned Data
61 Citations2008Jaideep Vaidya, Chris Clifton
A real application of the proposed protocol for securely computing a score separating the kth and the (k + 1) to compute such a score while revealing little additional information is shown.
On Multidimensional k-Anonymity with Local Recoding Generalization
37 Citations2007Yang Du, Tian Xia +3 more
This paper proves that it is NP-hard both to find the table with the maximum quality, and to discover a solution with an approximation ratio at most 5/4, and develops an algorithm with good balance between the approximation ratio and time complexity.