A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Generalization and Suppression <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> Generalization and Suppression <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> BIB002 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Generalization and Suppression <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> BIB003 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Generalization and Suppression <s> In this paper, we present a template-based privacy preservation to protect against the threats caused by data mining abilities. The problem has dual goals: preserve the information for a wanted classification analysis and limit the usefulness of unwanted sensitive inferences that may be derived from the data. Sensitive inferences are specified by a set of "privacy templates". Each template specifies the sensitive information to be protected, a set of identifying attributes, and the maximum association between the two. We show that suppressing the domain values is an effective way to eliminate sensitive inferences. For a large data set, finding an optimal suppression is hard, since it requires optimization over all suppressions. We present an approximate but scalable solution. We demonstrate the effectiveness of this approach on real life data sets. <s> BIB004 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Generalization and Suppression <s> Classification is a fundamental problem in data analysis. Training a classifier requires accessing a large collection of data. Releasing person-specific data, such as customer data or patient records, may pose a threat to an individual's privacy. Even after removing explicit identifying information such as Name and SSN, it is still possible to link released records back to their identities by matching some combination of nonidentifying attributes such as {Sex, Zip, Birthdate}. A useful approach to combat such linking attacks, called k-anonymization, is anonymizing the linking attributes so that at least k released records match each value combination of the linking attributes. Previous work attempted to find an optimal k-anonymization that minimizes some data distortion metric. We argue that minimizing the distortion to the training data is not relevant to the classification goal that requires extracting the structure of predication on the "future" data. In this paper, we propose a k-anonymization solution for classification. Our goal is to find a k-anonymization, not necessarily optimal in the sense of minimizing data distortion, which preserves the classification structure. We conducted intensive experiments to evaluate the impact of anonymization on the classification on future data. Experiments on real-life data show that the quality of classification can be preserved even for highly restrictive anonymity requirements <s> BIB005 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Generalization and Suppression <s> Cloud computing provides massive computation power and storage capacity which enable users to deploy applications without infrastructure investment. Many privacy-sensitive applications like health services are built on cloud for economic benefits and operational convenience. Usually, data sets in these applications are anonymized to ensure data owners? privacy, but the privacy requirements can be potentially violated when new data join over time. Most existing approaches address this problem via re-anonymizing all data sets from scratch after update or via anonymizing the new data incrementally according to the already anonymized data sets. However, privacy preservation over incremental data sets is still challenging in the context of cloud because most data sets are of huge volume and distributed across multiple storage nodes. Existing approaches suffer from poor scalability and inefficiency because they are centralized and access all data frequently when update occurs. In this paper, we propose an efficient quasi-identifier index based approach to ensure privacy preservation and achieve high data utility over incremental and distributed data sets on cloud. Quasi-identifiers, which represent the groups of anonymized data, are indexed for efficiency. An algorithm is designed to fulfil our approach accordingly. Evaluation results demonstrate that with our approach, the efficiency of privacy preservation on large-volume incremental data sets can be improved significantly over existing approaches. Highlights? We investigate the efficiency of privacy preservation over large-scale incremental data sets on cloud. ? A distributed quasi-identifier index structure is proposed to efficiently update anonymous incremental data sets. ? Locality-sensitive hash function is used to place similar quasi-identifier groups on the same node to improve efficiency. ? We elaborate the process of generalization or specialization when data updates occur. <s> BIB006 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Generalization and Suppression <s> The pervasiveness of location-aware devices has spawned extensive research in trajectory data mining, resulting in many important real-life applications. Yet, the privacy issue in sharing trajectory data among different parties often creates an obstacle for effective data mining. In this paper, we study the challenges of anonymizing trajectory data: high dimensionality, sparseness, and sequentiality. Employing traditional privacy models and anonymization methods often leads to low data utility in the resulting data and ineffective data mining. In addressing these challenges, this is the first paper to introduce local suppression to achieve a tailored privacy model for trajectory data anonymization. The framework allows the adoption of various data utility metrics for different data mining tasks. As an illustration, we aim at preserving both instances of location-time doublets and frequent sequences in a trajectory database, both being the foundation of many trajectory data mining tasks. Our experiments on both synthetic and real-life data sets suggest that the framework is effective and efficient to overcome the challenges in trajectory data anonymization. In particular, compared with the previous works in the literature, our proposed local suppression method can significantly improve the data utility in anonymous trajectory data. <s> BIB007 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Generalization and Suppression <s> As organizations start to publish the data that they collect, either internally or externally, in the form of statistical tables they need to consider the protection of the confidential information held in those tables. The algorithms used to protect the confidential information in these statistical tables are computationally expensive. However a simple preprocessing optimization applied prior to protection can save time, improve the resultant protection and on occasions enable the use of exact methods where otherwise heuristic methods would have been necessary. The theory behind this preprocessing optimization, how it can be applied and its effectiveness are described in this paper. <s> BIB008
Achieving k-anonymity by generalization and suppression will lead to not precise, but consistent representation of original dataset. Comprehensive consideration needs to be taken about three vital aspects referred to PPDP, which are privacy requirement, data utility and algorithm complexity. There are roughly four types of generalization with difference in scope and principle which are full-domain generalization, subtree generalization, cell generalization and multidimensional generalization. By the way, specification is the reverse anonymity operation of generalization. 1)Full-domain generalization BIB001 is proposed in early research of PPDP, it has the smallest search space in four types of generalization, while it leads to large data distortion. The key of full-domain generalization is that the value of quasi-identifier must be generalized to the same level in given taxonomy tree structure. We will use the taxonomy tree structure in figure 2 to explain. Before any anonymity operation, all values stay at the bottom of taxonomy. If node Undergraduate is generalized to its parent node Student, then node Graduate must be generalized to node Student, at the same time, nodes ITer and HR need to be generalized to node Worker. 2) Subtree generalization BIB002 BIB006 , its boundary is smaller than full-domain generalization. When a node in taxonomy tree structure generalizes to its parent node, all child nodes of the parent node need to be generalized to the parent node. For example, in figure 2, if node Undergraduate is generalized to its parent node Student, it needs to generalize node Graduate to its parent node Student to meet the requirement of subtree generalization. Unrestricted subtree generalization  is similar to the subtree generalization, except that siblings of the generalized node could remain unchanged. For example, in figure 2, if node Undergraduate is generalized to its parent node Student, node Graduate is unnecessary to generalize to its parent node Student. 3) Cell generalization  is slightly different from generalization ways above. Cell generalization is for single record, while, full-domain generalization is for all of records in the dataset. The search space with this generalization is significantly larger compared to other generalization, but the data distortion is relatively small. For example, in figure 2, when node Undergraduate generalizes to its parent node Student, it can maintain the record with Undergraduate value in the dataset. When the anonymous dataset is used for classification of data mining, it suffers from data exploration problem. For example, classifier may not know how to distinguish Undergraduate and Student. Those problems are the common traits of local recoding scheme. In most situations of generalization schemes, it mixes suppression operations in its process of data anonymization. It is without any doubts that there exists some theory or techniques to go on data anonymization only using suppression operation BIB005 BIB007 BIB008 . Like the category of generalization, there are five kinds of suppression, attribute suppression  , record suppression  , value suppression BIB004 , cell suppression BIB003 and multidimensional suppression  . Attribute suppression suppresses the whole values of the attribute. Record suppression means suppressing the records. Value suppression refers to suppressing the given value in the dataset. While cell suppression compared to cell generalization, works on small scope and suppresses some records with the given value in dataset.