Anonymizing Tables

By Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas, An Zhu. International Conference on Database Theory, 2005

345 citations recorded by the source corpus.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/124050415f03dd4cf642415c62f2bbd19d1dbc70

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

A General Survey of Privacy-Preserving Data Mining Models and Algorithms (2008, methodology): “The only known techniques which provide guarantees on the quality of the solution are approximation algorithms [13, 14, 89], in which the solu-tion found is guaranteed to be within a certain factor of the cost of the optimal solution.”
Protecting privacy when mining and sharing user data (2012, background): “One in particular, k-anonymity, has been popular in relation to user data [3,119] until di↵erential privacy was introduced.”
Aggregate Query Answering on Anonymized Tables (2007, neutral): “Several approximation algorithms have been proposed [2, 12].”
Anatomy: simple and effective privacy preservation (2006, background): “Unfortunately, it is NP-hard to ﬁnd the optimal solution, even for simple schemes and quality metrics [2, 9, 11].”
Minimality Attack in Privacy Preserving Data Publishing (2007, methodology): “Compared to a most competent existing algorithms for k -anonymity, our method introduces very minor computation overhead but achieves comparable information loss.”
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.”
Mondrian Multidimensional K-Anonymity (2006, methodology): “Approximation algorithms have also been proposed for the problem of finding the k-anonymization suppressing the fewest cells [1, 10].”
Protecting Location Privacy with Personalized k-Anonymity: Architecture and Algorithms (2008, background): “We would like to note that the general problem of the optimal k-anonymization is shown to be NP-hard [18], [19].”
When Machine Learning Meets Privacy (2020, background): “As the user connectivity increases and web applications become ubiquitous, the responsibility of privacy management transfers more and more to individuals.”
Efficient k -Anonymization Using Clustering Techniques (2007, background): “Aggarwal et al. showed that determining whether there exists a 3-anonymization of a table by suppressing certain number of cells is NP-hard.”
Incognito: efficient full-domain K-anonymity (2005, methodology): “Finally, the minimal cell- and attribute-suppression varieties of k-anonymization were proven to be NP-hard (with hardness proofs constructed based on the number of cells and number of attributes, respectively), and O(klogk) [13] and O(k) [1] approximation algorithms were proposed.”
Never Walk Alone: Uncertainty for Anonymity in Moving Objects Databases (2008, background): “The underlying idea is that a message sent from a user is k-anonymous when it is indistinguishable from the spatial and temporal information of at least k − 1 other messages sent from different users.”
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): “An approximation algorithm for CG is described in [3] as a direct extension of the approximation algorithm for CS presented in [2].”