Heuristic search for k-anonymization in a generalization lattice

1. A method comprising:

computing, by a processing device, a path through a generalization lattice comprising a plurality of levels, wherein the plurality of levels each represent a different level of generalization of N columns of quasi-identifier data, wherein the computing of the path further comprises:

computing one or more first values using a scoring function, from a first node on a first level of the generalization lattice to one or more second neighboring nodes on a second level of the generalization lattice;

adding, from the one or more second neighboring nodes, a best node from the second level to the path based on the one or more first values;

computing one or more second values, using the scoring function, from the best node on the second level to one or more third neighboring nodes on a third level of the generalization lattice; and

adding, from the one or more third neighboring nodes, a best node from the third level to the path based on the one or more second values, wherein, at a completion of the computing for each of the plurality of levels, the path comprises a plurality of best nodes, wherein each of the plurality of best nodes is one node added from each of the plurality of levels; and

selecting an optimal node from the plurality of best nodes.

2. The method of claim 1 , wherein the optimal node is a node that is used to initialize a lattice search algorithm by providing a bound on an information loss function.

3. The method of claim 1 , further comprising:

transforming data in a dataset into integer data;

generating a plurality of generalizations of the integer data; and

creating the generalization lattice based on the plurality of generalizations.

4. The method of claim 1 , further comprising:

computing an upper bound based on the optimal node; and

pruning the generalization lattice based on the upper bound.

5. The method of claim 1 , wherein each one of the one or more second neighboring nodes comprises a tuple that represents combinations of generalizations of the N columns of the quasi-identifier data, and wherein the tuple for each one of the one or more second neighboring nodes corresponds to a number of generalizations for each column of the N columns based on a data hierarchy corresponding to the column.

6. The method of claim 1 , wherein the path commences at a start node and terminates at an end node, and wherein the start node is a top node of the generalization lattice and the end node is a bottom node of the generalization lattice.

7. The method of claim 1 , further comprising:

computing a plurality of paths through the generalization lattice using a plurality of scoring functions; and

selecting the optimal node from the plurality of paths.

8. A system comprising:

a processing device; and

a memory to store instructions that, when executed by the processing device, cause the processing device to:

compute a path through a generalization lattice comprising a plurality of levels, wherein the plurality of levels each represent a different level of generalization of N columns of quasi-identifier data, wherein the computing of the path further comprises:

compute one or more first values using a scoring function, from a first node on a first level of the generalization lattice to one or more second neighboring nodes on a second level of the generalization lattice;

add, from the one or more second neighboring nodes, a best node from the second level to the path based on the one or more first values;

compute one or more second values, using the scoring function, from the best node on the second level to one or more third neighboring nodes on a third level of the generalization lattice; and

add, from the one or more third neighboring nodes, a best node from the third level to the path based on the one or more second values, wherein, at a completion of the computing for each of the plurality of levels, the path comprises a plurality of best nodes, wherein each of the plurality of best nodes is one node added from each of the plurality of levels; and

select an optimal node from the plurality of best nodes.

9. The system of claim 8 , wherein the optimal node is a node that is used to initialize a lattice search algorithm by providing a bound on an information loss function.

10. The system of claim 8 , wherein the processing device, responsive to executing the instructions, further causes the system to:

transform data in a dataset into integer data;

generate a plurality of generalizations of the integer data; and

create the generalization lattice based on the plurality of generalizations.

11. The system of claim 8 , wherein the processing device, responsive to executing the instructions, further causes the system to:

compute an upper bound based on the optimal node; and

prune the generalization lattice based on the upper bound.

12. The system of claim 8 , wherein each one of the one or more second neighboring nodes comprises a tuple that represents combinations of generalizations of the N columns of the quasi-identifier data, and wherein the tuple for each one of the one or more second neighboring nodes corresponds to a number of generalizations for each column of the N columns based on a data hierarchy corresponding to the column.

13. The system of claim 8 , wherein the path commences at a start node and terminates at an end node, and wherein the start node is a top node of the generalization lattice and the end node is a bottom node of the generalization lattice.

14. The system of claim 8 , wherein the processing device, responsive to executing the instructions, further causes the system to:

compute a plurality of paths through the generalization lattice using a plurality of scoring functions; and

select the optimal node from the plurality of paths.

15. A non-transitory computer readable medium, having instructions stored thereon which, when executed by a processing device, cause the processing device to:

compute, by the processing device, a path through a generalization lattice comprising a plurality of levels, wherein the plurality of levels each represent a different level of generalization of N columns of quasi-identifier data, wherein the computing of the path further comprises:

compute one or more first values using a scoring function, from a first node on a first level of the generalization lattice to one or more second neighboring nodes on a second level of the generalization lattice;

add, from the one or more second neighboring nodes, a best node from the second level to the path based on the one or more first values;

compute one or more second values, using the scoring function, from the best node on the second level to one or more third neighboring nodes on a third level of the generalization lattice; and

add, from the one or more third neighboring nodes, a best node from the third level to the path based on the one or more second values, wherein, at a completion of the computing for each of the plurality of levels, the path comprises a plurality of best nodes, wherein each of the plurality of best nodes is one node added from each of the plurality of levels; and

select an optimal node from the plurality of best nodes.

16. The non-transitory computer readable medium of claim 15 , wherein the optimal node is a node that is used to initialize a lattice search algorithm by providing a bound on an information loss function.

17. The non-transitory computer readable medium of claim 15 , wherein the processing device is to:

transform data in a dataset into integer data;

generate a plurality of generalizations of the integer data; and

create the generalization lattice based on the plurality of generalizations.

18. The non-transitory computer readable medium of claim 15 , wherein the processing device is to:

compute an upper bound based on the optimal node; and

prune the generalization lattice based on the upper bound.

19. The non-transitory computer readable medium of claim 15 , wherein each one of the one or more second neighboring nodes comprises a tuple that represents combinations of generalizations of the N columns of the quasi-identifier data, and wherein the tuple for each one of the one or more second neighboring nodes corresponds to a number of generalizations for each column of the N columns based on a data hierarchy corresponding to the column.

20. The non-transitory computer readable medium of claim 15 , wherein the processing device is to:

compute a plurality of paths through the generalization lattice using a plurality of scoring functions; and

select the optimal node from the plurality of paths.