On the complexity of optimal K-anonymity

By Adam Meyerson, Ryan Williams. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

920 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/d7a2934dd6a2d8ea2ec772e483d6fb28c7f6e636

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

Citations in the corpus

M-invariance: towards privacy preserving re-publication of dynamic datasets (2007, background): “In particular, it is shown [3, 13, 17] that computing the optimal generalized table is NP hard, even when a simple quality metric is deployed.”
t-Closeness: Privacy Beyond k-Anonymity and l-Diversity (2007, background): “Optimal k-anonymity has been proved to be NP-hard for k ≥ 3 [13].”
Privacy Preservation in the Publication of Trajectories (2008, background): “Finding the optimal set of points to delete from T in order to derive a secure T and achieve the minimum possible information loss is harder than the simpler k-anonymity problem in relational databases, discussed in Section 2, which is already shown to be NP-hard [14].”
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 .”
L-diversity: privacy beyond k-anonymity (2006, neutral): “[1-10], [ 11-20 ], etc), we would end up with very large q ∗ -blocks.”
The new Casper: query processing for location services without compromising privacy (2006, methodology): “The k -anonymity model [39, 40] has been widely used in maintaining data privacy (e.g., see [7, 29, 30, 31]).”
Achieving anonymity via clustering (2006, methodology): “The best known algorithms [1, 14] for previous problem formulations had an approximation ratio linear in the anonymity parameter r.”
Injecting utility into anonymized datasets (2006, background): “(d) Zip/Condition Marginal Zip CodeAge Count 14850 [41-50] 3 [31-40] 1 14853 [51-60] 2 [21-30] 2 [31-40] 1 13063 [21-30] 1 [31-40] 1 13068 [31-40] 1 [21-30] 1”
Aggregate Query Answering on Anonymized Tables (2007, background): “It has been shown that the problem of general k- nonymity with suppression and arbitrary domain generalizations (instead of predefined generalization hierarchies) is NP-complete [12, 3, 9].”
Big data privacy: a technological perspective and review (2016, background): “1 K-anonymity It is a framework for constructing and evaluating algorithms and systems that release information such that released information limits what can be revealed about the properties of entities that are to be protected Homogeneity-attack, background knowledge O(k logk) [35, 73]”
A General Survey of Privacy-Preserving Data Mining Models and Algorithms (2008, background): “Since each cluster contains at least k-records, the anonymized data is guaranteed to at least satisfy the definitions of k-anonymity.”
Fast Data Anonymization with Low Information Loss (2007, background): “though the problem is NP-hard in the general case [14], we show that the complexity is linear to the size of the input table for 1-D quasi-identifiers(2).”
Personalized privacy preservation (2006, background): “Focusing on the Primary Case, the authors of [16] develop an algorithm that generates the releasable data using “suppression” [3, 12] (as opposed to generalization in this paper).”
On k-Anonymity and the Curse of Dimensionality (2005, background): “In general, the problem of (cid:12)nding the optimal k -anonymous representation is known to be NP-hard [13].”
Privacy-Preserving Data Mining: Models and Algorithms (2008, background): “In [12], it has been shown that optimal k- nonymization”