A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Optimal Anonymity Algorithms <s> Today's globally networked society places great demands on the dissemination and sharing of information. While in the past released information was mostly in tabular and statistical form, many situations call for the release of specific data (microdata). In order to protect the anonymity of the entities (called respondents) to which information refers, data holders often remove or encrypt explicit identifiers such as names, addresses, and phone numbers. Deidentifying data, however, provides no guarantee of anonymity. Released information often contains other data, such as race, birth date, sex, and ZIP code, that can be linked to publicly available information to reidentify respondents and inferring information that was not intended for disclosure. In this paper we address the problem of releasing microdata while safeguarding the anonymity of respondents to which the data refer. The approach is based on the definition of k-anonymity. A table provides k-anonymity if attempts to link explicitly identifying information to its content map the information to at least k entities. We illustrate how k-anonymity can be provided without compromising the integrity (or truthfulness) of the information released by using generalization and suppression techniques. We introduce the concept of minimal generalization that captures the property of the release process not distorting the data more than needed to achieve k-anonymity, and present an algorithm for the computation of such a generalization. We also discuss possible preference policies to choose among different minimal generalizations. <s> BIB001 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Optimal Anonymity Algorithms <s> Often a data holder, such as a hospital or bank, needs to share person-specific records in such a way that the identities of the individuals who are the subjects of the data cannot be determined. One way to achieve this is to have the released records adhere to k- anonymity, which means each released record has at least (k-1) other records in the release whose values are indistinct over those fields that appear in external data. So, k- anonymity provides privacy protection by guaranteeing that each released record will relate to at least k individuals even if the records are directly linked to external information. This paper provides a formal presentation of combining generalization and suppression to achieve k-anonymity. Generalization involves replacing (or recoding) a value with a less specific but semantically consistent value. Suppression involves not releasing a value at all. The Preferred Minimal Generalization Algorithm (MinGen), which is a theoretical algorithm presented herein, combines these techniques to provide k-anonymity protection with minimal distortion. The real-world algorithms Datafly and µ-Argus are compared to MinGen. Both Datafly and µ-Argus use heuristics to make approximations, and so, they do not always yield optimal results. It is shown that Datafly can over distort data and µ-Argus can additionally fail to provide adequate protection. <s> BIB002
Samarati BIB001 proposes an algorithm for finding minimal full-domain generalization to implement optimal anonymity using binary search. In BIB002 , it proposes an algorithm for finding minimal generalization with minimal distortion that is called MinGen. MinGen try to examine all of potential full-domain generalization, so that find the optimal generalization according to relevant information metric. However, in the work, it points out that an exhaustive search of all possible generalization is impractical even for the modest sized dataset. Incognito  is an efficient anonymity algorithm by producing minimal full-domain generalization to achieve k-anonymity, which takes advantage of two key features of dynamic programming, namely, bottom-up aggregation along dimensional hierarchies and a priori aggregate computation. Moreover, it uses generalization lattice and three properties to facilitate finding minimal full-domain generalization. There is a brief explanation for figure 4. The leftmost two structures are taxonomy tree structure of Zipcode and Sex quasi-identifier. And the rightmost structure is two-attribute lattice assembling with the tree structure of Zipcode and Sex. The related three properties are generalization property, rollup property and subset property which are showed below in detail. Incognito algorithm generates all possible k-anonymous full-domain generalization of original dataset based on subset property. It checks whether single-attribute reaches the requirement of k-anonymity at the start of algorithm execution, then iterates by increasing the size of quasi-identifiers forming larger multi-attribute generalization lattice till reach the scale of given quasi-identifiers. Generalization Property: Let T be a dataset, and let P and Q be sets of attributes in T such that D P < D D Q . If T is k-anonymous with respect to P, then T is also kanonymous with respect to Q. Rollup Property: Let T be a dataset, and let P and Q be sets of attributes in T such that D P < D D Q . If we have f 1 , the frequency set of T with respect to P, then, we can generate the count of f 2 , the frequency set of T with respect to Q, by summing the set of counts in f 1 associated by γ with each value set of f 2 . Subset Property: Let T be a dataset, and let Q be a set of attributes in T. If T is k-anonymous with respect to Q, then T is k-anonymous with respect to any set of attributes P such that P ⊆ Q. K-Optimize  algorithm is an algorithm of implementing optimal anonymity by pruning unsatisfied released table using a set enumeration tree. The difference between K-Optimize and Incognito is that K-Optimize uses subtree generalization and record suppression, while, Incognito incorporates full-domain generalization into scheme.