The effect of homogeneity on the computational complexity of combinatorial data anonymization

DOI10.1007/S10618-012-0293-7MaRDI QIDQ2435706zbMATH OpenOpenAlexFDO

Authors Robert Bredereck, André Nichterlein, Geevarghese Philip, Rolf Niedermeier

Publication date 19 February 2014

Published in Data Mining and Knowledge Discovery (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10618-012-0293-7

zbMATH Keywords

\(\ell\)-diversity\(k\)-anonymity\(p\)-sensitivitydomain generalization hierarchiesfixed-parameter tractabilitymatrix modification problemsNP-hardnessparameterized algorithmics

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05)

Recommendations

• The effect of homogeneity on the complexity of \(k\)-anonymity
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Pattern-guided \(k\)-anonymity
• Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries

Cites work

• A practical approximation algorithm for optimal \(k\)-anonymity
• Achieving anonymity via clustering
• ACHIEVING k-ANONYMITY PRIVACY PROTECTION USING GENERALIZATION AND SUPPRESSION
• Anonymizing binary and small tables is hard to approximate
• Database Theory - ICDT 2005
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• Fixed-parameter tractability of anonymizing data by suppressing entries
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• k-Anonymization with Minimal Loss of Information
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Parametrized complexity theory.
• Pattern-Guided Data Anonymization and Clustering
• Reflections on multivariate algorithmics and problem parameterization
• Resolving the Complexity of Some Data Privacy Problems
• The l-diversity problem: tractability and approximability
• The NP-completeness column: An ongoing guide
• Towards fully multivariate algorithmics: some new results and directions in parameter ecology

Cited in

(6)

• Pattern-guided k-anonymity
• Using patterns to form homogeneous teams
• A refined complexity analysis of degree anonymization in graphs
• Privacy in elections: k-anonymizing preference orders
• The effect of homogeneity on the complexity of \(k\)-anonymity
• \(k\)-attribute-anonymity is hard even for \(k=2\)

Describes a project that uses

Uses Software

• UCI

This page was built for publication: The effect of homogeneity on the computational complexity of combinatorial data anonymization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2435706)