The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization recently proposed is the k-anonymity. This approach requires that the rows in a table are clustered in sets of size at least k and that all the rows in a cluster are related to the same tuple, after the suppression of some records. The problem has been shown to be NP-hard when the values are over a ternary alphabet, k = 3 and the rows length is unbounded. In this paper we give a lower bound on the approximation of two restrictions of the problem, when the records values are over a binary alphabet and k = 3, and when the records have length at most 8 and k = 4, showing that these restrictions of the problem are APX-hard. © 2009 Springer Berlin Heidelberg

Bonizzoni, P., Della Vedova, G., Dondi, R. (2009). The k-anonymity problem is hard. In Proceedings 17th International Symposium on Fundamentals of Computation Theory (FCT 2009) (pp.26-37). Springer Verlag [10.1007/978-3-642-03409-1_4].

The k-anonymity problem is hard

Bonizzoni, P;Della Vedova, G;Dondi, R
2009

Abstract

The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization recently proposed is the k-anonymity. This approach requires that the rows in a table are clustered in sets of size at least k and that all the rows in a cluster are related to the same tuple, after the suppression of some records. The problem has been shown to be NP-hard when the values are over a ternary alphabet, k = 3 and the rows length is unbounded. In this paper we give a lower bound on the approximation of two restrictions of the problem, when the records values are over a binary alphabet and k = 3, and when the records have length at most 8 and k = 4, showing that these restrictions of the problem are APX-hard. © 2009 Springer Berlin Heidelberg
No
paper
privacy; anonimity; database
English
17th International Symposium on Fundamentals of Computation Theory (FCT 2009) SEP 02-04
978-3-642-03408-4
Bonizzoni, P., Della Vedova, G., Dondi, R. (2009). The k-anonymity problem is hard. In Proceedings 17th International Symposium on Fundamentals of Computation Theory (FCT 2009) (pp.26-37). Springer Verlag [10.1007/978-3-642-03409-1_4].
Bonizzoni, P; Della Vedova, G; Dondi, R
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/8401
Citazioni
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
Social impact