Patent ID: 8112422

Claim:
A computer program product for anonymizing a database that includes a plurality of tuples, a respective one of the plurality of tuples including at least one quasi-identifier and a plurality of sensitive attributes associated with the respective one of the plurality of tuples, the computer program product comprising a non-transitory computer readable storage medium having computer readable program code embodied in the non-transitory computer readable storage medium, the computer readable program code comprising: computer readable program code that is configured to partition the plurality of tuples into groups, a respective group including at least k different values of a linear combination of at least two of the plurality of sensitive attributes, where k is at least two, and a corresponding distance range of the linear combinations of the at least two of the plurality of sensitive attributes that is at least e, where e is greater than zero, to provide a (k,e)-anonymous partition of the database that includes the plurality of sensitive attributes; computer readable program code that is configured to permute as units, the at least two sensitive values in the respective groups of the (k,e)-anonymous partition of the database that includes the plurality of sensitive attributes, to provide a (k,e)-anonymous permutation of the database that includes the plurality of sensitive attributes; and computer readable program code that is configured to query the (k,e)-anonymous permutation of the database that includes the plurality of sensitive attributes in response to a user query and to output a result of the user query of the (k,e)-anonymous permutation of the database that includes the plurality of sensitive attributes to the user; wherein the computer readable program code that is configured to partition the plurality of tuples into groups comprises computer readable program code that is configured to find a minimum size axis-parallel square that covers projections of the at least two of the plurality of sensitive attributes in a respective group; and wherein the computer readable program code that is configured to find a minimum size axis-parallel square that covers projections of the at least two of the plurality of sensitive attributes in a respective group comprises computer readable program code that is configured to compute centered axis-parallel squares and computer readable program code that is configured to compute axis-parallel squares anchored to a grid from the centered axis-parallel squares.