A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> General Metric <s> Data on individuals and entities are being collected widely. These data can contain information that explicitly identifies the individual (e.g., social security number). Data can also contain other kinds of personal information (e.g., date of birth, zip code, gender) that are potentially identifying when linked with other available data sets. Data are often shared for business or legal reasons. This paper addresses the important issue of preserving the anonymity of the individuals or entities during the data dissemination process. We explore preserving the anonymity by the use of generalizations and suppressions on the potentially identifying portions of the data. We extend earlier works in this area along various dimensions. First, satisfying privacy constraints is considered in conjunction with the usage for the data being disseminated. This allows us to optimize the process of preserving privacy for the specified usage. In particular, we investigate the privacy transformation in the context of data mining applications like building classification and regression models. Second, our work improves on previous approaches by allowing more flexible generalizations for the data. Lastly, this is combined with a more thorough exploration of the solution space using the genetic algorithm framework. These extensions allow us to transform the data so that they are more useful for their intended purpose while satisfying the privacy constraints. <s> BIB001 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> General Metric <s> The technique of k-anonymization has been proposed in the literature as an alternative way to release public information, while ensuring both data privacy and data integrity. We prove that two general versions of optimal k-anonymization of relations are NP-hard, including the suppression version which amounts to choosing a minimum number of entries to delete from the relation. We also present a polynomial time algorithm for optimal k-anonymity that achieves an approximation ratio independent of the size of the database, when k is constant. In particular, it is a O(k log k)-approximation where the constant in the big-O is no more than 4, However, the runtime of the algorithm is exponential in k. A slightly more clever algorithm removes this condition, but is a O(k log m)-approximation, where m is the degree of the relation. We believe this algorithm could potentially be quite fast in practice. <s> BIB002 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> General Metric <s> Set-valued data, in which a set of values are associated with an individual, is common in databases ranging from market basket data, to medical databases of patients' symptoms and behaviors, to query engine search logs. Anonymizing this data is important if we are to reconcile the conflicting demands arising from the desire to release the data for study and the desire to protect the privacy of individuals represented in the data. Unfortunately, the bulk of existing anonymization techniques, which were developed for scenarios in which each individual is associated with only one sensitive value, are not well-suited for set-valued data. In this paper we propose a top-down, partition-based approach to anonymizing set-valued data that scales linearly with the input size and scores well on an information-loss data quality metric. We further note that our technique can be applied to anonymize the infamous AOL query logs, and discuss the merits and challenges in anonymizing query logs using our approach. <s> BIB003
General metric is used for the scenario that data publisher has no knowledge about application area of published dataset. For this reason, general metric leverages all kinds of factors, make it fit for different situation as much as possible by measuring discrepancy of anonymous and original dataset. In early works BIB002    , the definition of data metric is not totally formed, and it just has the concept of minimal distortion that corresponding algorithm must comply with. For example, one measure of information loss was the number of generalized entries in the anonymous dataset and some algorithm judges the data quality by the ratio of the size of anonymous and original dataset. Loss Metric (LM) for records is computed by summing up a normalized information loss of each quasi-identifier. Information loss (IL attr ) of each attribute is compute by In the formula, N g is represented for child count of the parent node which current value generalizes to and N is the child count of this quasi-identifier.  Loss metric (IL record ) of a record is calculated by the sum of information loss of quasi-identifiers under the assumption that each quasi-identifier has equal weight. Therefore, we can infer that Loss metric for the whole dataset (IL table ) is based on information loss of generalized record like the formula shown below. This series of information metric also adopted by   . Quality measure is based on the size of the equivalence class E in dataset D. the discernibility metric (C DM ) assigns each record t in dataset D a penalty determined by the size of the equivalence class containing t. If a record belongs to an equivalent class of size s, the penalty for the record is s. If a tuple is suppressed, then it is assigned a penalty of |D|. This penalty reflects the fact that a suppressed tuple cannot be distinguished from any other tuple in the dataset. In the formula 5, the first sum computes penalties for each non-suppressed tuple, and the second for suppressed tuples. Another metric is proposed by Iyengar BIB001 which is used in privacy preserving data mining. This classification metric assigns no penalty to an unsuppressed tuple if it c 2014 NSP Natural Sciences Publishing Cor. belongs to the majority class within its induced equivalence class. All other tuples are penalized a value of 1. The minority function in formula 6 accepts a set of class-labeled tuples and returns the subset of tuples belonging to any minority class with respect to that set. Normalized average equivalence class size metric (C AV G ) is proposed as an alternative. The intention of the metric is to measure how well the partitioning reaches the optimal case where each record is generalized in the equivalent class of k indistinguishable records. This sort of information metric also has many supporters BIB003 . Precision metric is based on taxonomy tree structure. If the original dataset D(A 1 , . . . , A N a ) and the anonymous dataset N a is the count of quasi-identifiers and h represents the height of taxonomy tree structure of A j after generalization. V GH A j is total height of taxonomy tree structure of A j . For any quasi-identifier A j , the smaller of prec(D ′ ), the worse of information loss.