incognito
Class Incognito_K

java.lang.Object
  anonymizer.Anonymizer
      incognito.Incognito_K

public class Incognito_K
extends Anonymizer

Implementation of the Incognito algorithm for k-anonymity that appeared in the following paper:

 @inproceedings{Incognito,
 author = {LeFevre, Kristen and DeWitt, David J. and Ramakrishnan, Raghu},
 title = {Incognito: efficient full-domain K-anonymity},
 booktitle = {SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data},
 year = {2005},
 isbn = {1-59593-060-4},
 pages = {49--60},
 location = {Baltimore, Maryland},
 doi = {http://doi.acm.org/10.1145/1066157.1066164},
 publisher = {ACM},
 address = {New York, NY, USA},
 }
 

Our implementation uses the bottom-up precomputation optimization described in Section 3.3.2 of the paper. At any time during anonymization, only the original table and lattice entries that are k-anonymous are kept on the database.

After the entire generalization lattice is traversed (in breadth-first order), among all successful anonymization, we choose the one that yields the maximum number of equivalence classes (please see selectAnonymization() for details).

The paper discusses suppression as an option (the idea is the same as Datafly by Sweeney). Our implementation allows suppression through the data member suppressionThreshold. When set to 0, our method will simply disallow suppression.

Field Summary

private LatticeManager	man Lattice manager that controls how the generalization lattice is traversed
int	suppressionThreshold Suppression threshold (set to 0 if not needed)

Fields inherited from class anonymizer.Anonymizer

anonTable, conf, eqTable, sqlwrapper

Constructor Summary

Incognito_K(Configuration conf)
Class constructor

Method Summary

void	anonymize() Anonymizing the input.
void	changeKAnonymityRequirement(int newKvalue) Overwrites the privacy parameter k
protected AnonRecordTable	createAnonRecordsTable(java.lang.String tableName) Create anonRecords table
protected EquivalenceTable	createEquivalenceTable(java.lang.String tableName) Create equivalence table
private void	generalize(LatticeEntry root) Generalizes the original table according to a lattice entry and sets the result for the generated table as anonymous or not.
protected void	insertTupleToAnonTable(java.lang.String[] vals, long eid) Insert a tuple to the anonRecords table
protected long	insertTupleToEquivalenceTable(java.lang.String[] vals) Insert a tuple to the equivalence table
private boolean	satisfiesPrivacyDef(AnonRecordTable table) Checks whether the parameter table satisfies the privacy definition (in this case, k-anonymity with suppression)
private void	selectAnonymization(java.util.LinkedList<LatticeEntry> anons) Simply select the anonymization that yields the maximum number of distinct equivalences

Methods inherited from class anonymizer.Anonymizer

anonymizeDataset, anonymizeDataset, isReadyForSuppression, main, outputResults_Anatomy, outputResults_GenVals, outputResults_GenValsDist, outputResults, readData, suppressEquivalences

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

suppressionThreshold

public int suppressionThreshold

Suppression threshold (set to 0 if not needed)

man

private LatticeManager man

Lattice manager that controls how the generalization lattice is traversed

Constructor Detail

Incognito_K

public Incognito_K(Configuration conf)
            throws java.lang.Exception

Class constructor

Parameters:

conf - Configuration instance

Throws:

java.lang.Exception

Method Detail

changeKAnonymityRequirement

public void changeKAnonymityRequirement(int newKvalue)

Overwrites the privacy parameter k

Parameters:

newKvalue - New value of k

createEquivalenceTable

protected EquivalenceTable createEquivalenceTable(java.lang.String tableName)

Create equivalence table

Specified by:

createEquivalenceTable in class Anonymizer

Parameters:

tableName - Name of the table

Returns:

A new equivalence table

createAnonRecordsTable

protected AnonRecordTable createAnonRecordsTable(java.lang.String tableName)

Create anonRecords table

Specified by:

createAnonRecordsTable in class Anonymizer

Parameters:

tableName - Name of the table

Returns:

A new anonymization records table

insertTupleToEquivalenceTable

protected long insertTupleToEquivalenceTable(java.lang.String[] vals)
                                      throws java.lang.Exception

Insert a tuple to the equivalence table

Specified by:

insertTupleToEquivalenceTable in class Anonymizer

Parameters:

vals - All values of the tuple to be inserted (as read from the source, i.e., before any generalization)

Returns:

Equivalence id of the equivalence to which the tuple belongs

Throws:

java.lang.Exception

insertTupleToAnonTable

protected void insertTupleToAnonTable(java.lang.String[] vals,
                                      long eid)
                               throws java.lang.Exception

Insert a tuple to the anonRecords table

Specified by:

insertTupleToAnonTable in class Anonymizer

Parameters:

vals - All values of the tuple to be inserted (as read from the source, i.e., before any generalization)

eid - Equivalence id of the equivalence to which the tuple belongs

Throws:

java.lang.Exception

anonymize

public void anonymize()
               throws java.lang.Exception

Anonymizing the input. This function can be reused (with new k maybe), as long as eqTable and anonTable objects are fresh and the configuration has not changed.

Specified by:

anonymize in class Anonymizer

Throws:

java.lang.Exception

satisfiesPrivacyDef

private boolean satisfiesPrivacyDef(AnonRecordTable table)
                             throws java.lang.Exception

Checks whether the parameter table satisfies the privacy definition (in this case, k-anonymity with suppression)

Parameters:

table - Table to be checked for anonymity

Returns:

true if the privacy definition is satisfied

Throws:

java.lang.Exception

generalize

private void generalize(LatticeEntry root)
                 throws java.lang.Exception

Generalizes the original table according to a lattice entry and sets the result for the generated table as anonymous or not. If not, the corresponding table will be dropped from the database. If too, this root will be added to the set of successful anonymizations.

Parameters:

root - An entry of the generalization lattice that specifies how many times each qi-attribute will be generalized

Throws:

java.lang.Exception

selectAnonymization

private void selectAnonymization(java.util.LinkedList<LatticeEntry> anons)
                          throws java.lang.Exception

Simply select the anonymization that yields the maximum number of distinct equivalences

Parameters:

anons - List of lattice entries that correspond to anonymized tables

Throws:

java.lang.Exception