Generalizing data to provide anonymity when disclosing information

A technique for releasing information such that the ability to link the released data to other information is limited in an attempt to protect the identities of individuals is presented. Generalization is used by which stored values can be replaced with semantically consistent but less precise alternatives, and k-anonymity. A table provides k-anonymity when each combination of values that is associated with a quasi-identifier occurs k or more times, making it difficult to link the quasi-identifier to the other data. The notions of generalized table and of minimal generalization of a table with respect to a k-anonymity requirement is introduced. As an optimization problem, the data while providing adequate protection is minimally distorted.