The k-anonymity problem is hard
作者： Paola Bonizzoni , Gianluca Della Vedova , Riccardo Dondi
DOI: 10.1007/978-3-642-03409-1_4
关键词:
摘要: The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization recently proposed the k-anonymity. This approach requires that rows in a table are clustered sets size at least k and all cluster related to same tuple, after suppression some records. has been shown be NP-hard when values over ternary alphabet, = 3 length unbounded. In this paper we give lower bound on approximation two restrictions problem, records binary alphabet 3, have most 8 4, showing these APX-hard.
springer.com
core.ac.uk
harvard.edu
sci-hub.st 参考文章(11)
Rina Panigrahy, Rajeev Motwani, Krishnaram Kenthapadi, Dilys Thomas, Tomas Feder, Gagan Aggarwal, An Zhu, Approximation Algorithms for k-Anonymity Journal of Privacy Technology. ,(2005)
Hyoungmin Park, Kyuseok Shim, None, Approximate algorithms for K-anonymity Proceedings of the 2007 ACM SIGMOD international conference on Management of data - SIGMOD '07. pp. 67- 78 ,(2007) , 10.1145/1247480.1247490
Paola Alimonti, Viggo Kann, Some APX-completeness results for cubic graphs Theoretical Computer Science. ,vol. 237, pp. 123- 134 ,(2000) , 10.1016/S0304-3975(98)00158-3
Pierangela Samarati, Latanya Sweeney, Generalizing data to provide anonymity when disclosing information (abstract) symposium on principles of database systems. pp. 188- ,(1998) , 10.1145/275487.275508
P. Samarati, Protecting respondents identities in microdata release IEEE Transactions on Knowledge and Data Engineering. ,vol. 13, pp. 1010- 1027 ,(2001) , 10.1109/69.971193
Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, An Zhu, Achieving anonymity via clustering symposium on principles of database systems. pp. 153- 162 ,(2006) , 10.1145/1142351.1142374
Giorgio Gambosi, Pierluigi Crescenzi, Alberto Marchetti-Spaccamela, Viggo Kann, Giorgio Ausiello, Marco Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties ,(1999)
LATANYA SWEENEY, k -anonymity: a model for protecting privacy International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems. ,vol. 10, pp. 557- 570 ,(2002) , 10.1142/S0218488502001648
A. Gionis, T. Tassa, k-Anonymization with Minimal Loss of Information IEEE Transactions on Knowledge and Data Engineering. ,vol. 21, pp. 206- 219 ,(2009) , 10.1109/TKDE.2008.129
Giorgio Ausiello, Alberto Marchetti-Spaccamela, Pierluigi Crescenzi, Giorgio Gambosi, Marco Protasi, Viggo Kann, Complexity and Approximation Springer Berlin Heidelberg. ,(1999) , 10.1007/978-3-642-58412-1