On the Anonymization of Sparse High-Dimensional Data
Published 1 April 2008Open access
Gabriel Ghinita, Yufei Tao, Panos Kalnis
Citations189
SJR quartileQ4
SJR score0.11
SNIP0.06
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
This work proposes a novel anonymization method for sparse high-dimensional data that employs a particular representation that captures the correlation in the underlying data, and facilitates the formation of anonymized groups with low information loss.
Abstract
10.1109/ICDE.2008.4497480
Keywords
Computer ScienceSocial Sciences
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
L-diversity: privacy beyond k-anonymity
2,376 Citations2006Ashwin Machanavajjhala, Johannes Gehrke +2 more
This paper shows with two simple attacks that a \kappa-anonymized dataset has some subtle, but severe privacy problems, and proposes a novel and powerful privacy definition called \ell-diversity, which is practical and can be implemented efficiently.
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.
Reducing the bandwidth of sparse symmetric matrices
1,461 Citations1969Elizabeth Cuthill, James McKee
A direct method of obtaining an automatic nodal numbering scheme to ensure that the corresponding coefficient matrix will have a narrow bandwidth is presented.
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.
Very Large Data BasesAnatomy: simple and effective privacy preservation
646 Citations2006Xiaokui Xiao, Yufei Tao
A linear-time algorithm is developed for computing anatomized tables that obey the l-diversity privacy requirement, and minimize the error of reconstructing the microdata.
IEEE Transactions on Knowledge and Data EngineeringPreventing Location-Based Identity Inference in Anonymous Spatial Queries
619 Citations2007Panos Kalnis, Gabriel Ghinita +2 more
A framework for preventing location-based identity inference of users who issue spatial queries to location-based services, and proposes transformations based on the well-established K-anonymity concept to compute exact answers for range and nearest neighbor search, without revealing the query source.
On k -anonymity and the curse of dimensionality
593 Citations2005Charų C. Aggarwal
It is shown that the curse of high dimensionality also applies to the problem of privacy preserving data mining, and when a data set contains a large number of attributes which are open to inference attacks, it becomes difficult to anonymize the data without an unacceptably high amount of information loss.
SIAM Journal on Numerical AnalysisAn Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
586 Citations1976Norman E. Gibbs, William G. Poole +1 more
Extensive testing on finite element matrices indicates that the algorithm typically produces bandwidth and profile which are comparable to those of the commonly-used reverse Cuthill–McKee algorithm, yet requires significantly less computation time.
IEEE Transactions on Knowledge and Data EngineeringAssociation rule hiding
522 Citations2004Vassilios S. Verykios, Ahmed K. Elmagarmid +3 more
This work investigates confidentiality issues of a broad category of rules, the association rules, and presents three strategies and five algorithms for hiding a group of associationrules, which is characterized as sensitive.
Real world performance of association rule algorithms
491 Citations2001Zijian Zheng, Ron Kohavi +1 more
The experimental results confirm the performance improvements previously claimed by the authors on the artificial data, but some of these gains do not carry over to the real datasets, indicating overfitting of the algorithms to the IBM artificial dataset.
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.
Deriving private information from randomized data
412 Citations2005Zhengli Huang, Wenliang Du +1 more
A modified randomization scheme is proposed, in which the correlation of random noises "similar" to the original data is allowed to improve privacy, and the reconstruction accuracy of both PCA-based and BE-based schemes become worse as the similarity increases.
ComputingThe NP-Completeness of the bandwidth minimization problem
407 Citations1976Ch. H. Papadimitriou
The Problem of minimizing the bandwidth of the nonzero entries of a sparse symmetric matrix by permuting its rows and columns and some related combinatorial problems are shown to be NP-Complete.
Aggregate Query Answering on Anonymized Tables
361 Citations2007Qing Zhang, Nick Koudas +2 more
A general framework of permutations-based anonymization to support accurate answering of aggregate queries is presented and it is shown that, for the same grouping, permutation-based techniques can always answer aggregate queries more accurately than generalization-based approaches.
Injecting utility into anonymized datasets
299 Citations2006Daniel Kifer, Johannes Gehrke
This paper discusses the shortcomings of current heuristic approaches to measuring utility and introduces a formal approach to measure utility and shows how to inject additional information into k-anonymity and l-diverse tables.
Achieving anonymity via clustering
277 Citations2006Gagan Aggarwal, Tomás Feder +5 more
This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k, and extends the algorithms to allow an ε fraction of points to remain unclustered, i.e., deleted from the anonymized publication.
Fast data anonymization with low information loss
277 Citations2007Gabriel Ghinita, Panagiotis Karras +2 more
This paper focuses on one-dimensional (i.e., single attribute) quasi-identifiers, and study the properties of optimal solutions for k-anonymity and l-diversity, and develops efficient heuristics to solve the one- dimensional problems in linear time based on meaningful information loss metrics.
arXiv (Cornell University)How To Break Anonymity of the Netflix Prize Dataset
270 Citations2006Arvind Narayanan, Vitaly Shmatikov
This work presents a new class of statistical de-anonymization attacks against high-dimensional micro-data, such as individual preferences, recommendations, transaction records and so on, and demonstrates that an adversary who knows only a little bit about an individual subscriber can easily identify this subscriber's record in the dataset.
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.
The VLDB JournalAnonymity preserving pattern discovery
111 Citations2006Maurizio Atzori, Francesco Bonchi +2 more
By shifting the concept of k-anonymity from the source data to the extracted patterns, this paper formally characterize the notion of a threat to anonymity in the context of pattern discovery, and provides a methodology to efficiently and effectively identify all such possible threats that arise from the disclosure of the set of extracted patterns.
BIT Numerical MathematicsA linear time implementation of the reverse Cuthill-McKee algorithm
79 Citations1980W. M. Chan, Alan D. George
An implementation of the Reverse Cuthill-McKee (RCM) algorithm whose run-time complexity is proved to be linear in the number of nonzeros in the matrix is provided.
IEEE Transactions on Information TheoryOn Achieving Local View Capacity Via Maximal Independent Graph Scheduling
60 Citations2011Vaneet Aggarwal, A. Salman Avestimehr +1 more
This paper formalizes the increase of sum-rate with increased knowledge of the network state, and proposes to use the metric of normalized sum-capacity, which is the h -local view sum- capacity divided by global-view sum capacity.
SIAM Journal on Matrix Analysis and ApplicationsReducing the Total Bandwidth of a Sparse Unsymmetric Matrix
39 Citations2006John Reid, J. A. Scott
The node-centroid and hill-climbing ideas of Lim, Rodrigues, and Xiao are adapted to the unsymmetric case and it is found that using these to refine a Cuthill-McKee-based ordering can give significant further bandwidth reductions.