On k-Anonymity and the Curse of Dimensionality

By Charu C. Aggarwal. 2005

824 citations recorded by the source corpus.

How researchers see this paper

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

In Privacy & Security

Citations in the corpus

Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data (2016, background): “However, its lack of randomization gives rise to caveats (Dwork & Roth, 2014), and attackers can infer properties of the dataset (Aggarwal, 2005).”
Privacy in Deep Learning: A Survey (2020, background): “However, k-anonymization has been shown to perform poorly on the anonymization of high-dimensional datasets [51].”
Scalable Private Learning with PATE (2018, background): “This is not the case of all privacy definitions, as demonstrated by successful attacks against anonymization techniques (Aggarwal, 2005; Narayanan & Shmatikov, 2008; Bindschaedler et al., 2017).”
Interactive machine learning for health informatics: when do we need the human-in-the-loop? (2016, background): “Consequently, it becomes difﬁcult to anonymize the data without an unacceptably high amount of information loss [39].”
Machine learning and genomics: precision medicine versus patient privacy (2018, background): “dition, when the number of sensitive variables is large, which is the case with genomic sequences and GWAS data, they can only be achieved by deleting most of these variables, hence losing in utility [35]. 4 Learning from noisy data: diﬀerential privacy Another formal data protection model, called d”
Personalized privacy preservation (2006, background): “This is because, the higher ws, the less SA-generalization is possible such that the function of Figure 5 entails smaller overhead.”
k -Anonymous Data Mining: A Survey (2008, methodology): “divorced any sex [1,100) 21 (16Y, 5N) married any sex [1,100) 19 (10Y, 9N) never married any sex [1,100) 26 (6Y, 20N)”
Technical Privacy Metrics (2015, background): “se it also satisfies approximate differential privacy, see Section5.4.3). priv KA ≡k, where ∀E : |E|≥k However, studies have shown k-anonymity to be insufficient, especially for high-dimensional data [4] and against correlation with other data sets [93], because it fails to protect against attribute”
PRIVE: anonymous location-based queries in distributed mobile systems (2007, background): “[23] the authors consider the case where each individual requires a diﬀerent degree K of anonymity, while Aggar-wal [1] shows that anonymizing a high-dimensional relation results to unacceptable loss of information due to the dimensionality curse.”
Estimating the success of re-identifications in incomplete datasets using generative models (2019, background): “While more advanced guarantees like k -anonymity 57 would give every individual in the dataset some protection, they have been shown to be NP-Hard 58 , hard to achieve in modern high-dimensional datasets 59 , and not always suf ﬁ cient 60 .”
Link prediction by de-anonymization: How We Won the Kaggle Social Network Challenge (2011, background): “This is a daunting task: a long line of research has demonstrated the feasibility of de-anonymization on various datasets [27], [21], [13], [17], [25], [26], [14], [1] and theoretical evidence exists for the impossibility of de-anonymization of high-dimensional data [3].”
The cost of privacy: destruction of data-mining utility in anonymized data publishing (2008, background): “Limitations of k-anonymity are: (1) it does not hide whether a given individual is in the database [26,30], (2) it reveals individuals’ sensitive attributes [21, 22], (3) it does not protect against attacks based on background knowledge [22, 23], (4) mere knowledge of the k-anonymization algorithm c”
Recommender Systems (2016, neutral): “The challenges for high-dimensional data are not trivial, and there are theoretical barriers [30] to the limits of anonymization.”
On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy (2011, background): “m is impractical. Requiring the usage of a data-independent global generalization scheme maybe too restrictive. Furthermore, it is well known that k-anonymity suffers from the curse of dimensionality [1]. We now discuss how these issues can be addressed. The comprehensive development of these ideas ”
When Machine Learning Meets Privacy (2020, background): “uch an attack is illustrated in Fig.6(c). 4.2 Machine Learning Aided Privacy Protection Schemes Many privacy protection schemes have been introduced. Obfuscation/perturbation [31, 140], anonymization [5, 6], reducing information sharing [82, 142], and cryptographic mechanisms [43, 127] are the major”
M-invariance: towards privacy preserving re-publication of dynamic datasets (2007, background): “b ={*, Bob, 21, 12k, [1, 2]} b ={*, Alice, 22, 14k, [1, 1]}”