A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <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> Minimal Anonymity Algorithms <s> The well-known privacy-preserved data mining modifies existing data mining techniques to randomized data. In this paper, we investigate data mining as a technique for masking data, therefore, termed data mining based privacy protection. This approach incorporates partially the requirement of a targeted data mining task into the process of masking data so that essential structure is preserved in the masked data. The idea is simple but novel: we explore the data generalization concept from data mining as a way to hide detailed information, rather than discover trends and patterns. Once the data is masked, standard data mining techniques can be applied without modification. Our work demonstrated another positive use of data mining technology: not only can it discover useful patterns, but also mask private information. We consider the following privacy problem: a data holder wants to release a version of data for building classification models, but wants to protect against linking the released data to an external source for inferring sensitive information. We adapt an iterative bottom-up generalization from data mining to generalize the data. The generalized data remains useful to classification but becomes difficult to link to other sources. The generalization space is specified by a hierarchical structure of generalizations. A key is identifying the best generalization to climb up the hierarchy at each iteration. Enumerating all candidate generalizations is impractical. We present a scalable solution that examines at most one generalization in each iteration for each attribute involved in the linking. <s> BIB002 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <s> Releasing person-specific data in its most specific state poses a threat to individual privacy. This paper presents a practical and efficient algorithm for determining a generalized version of data that masks sensitive information and remains useful for modelling classification. The generalization of data is implemented by specializing or detailing the level of information in a top-down manner until a minimum privacy requirement is violated. This top-down specialization is natural and efficient for handling both categorical and continuous attributes. Our approach exploits the fact that data usually contains redundant structures for classification. While generalization may eliminate some structures, other structures emerge to help. Our results show that quality of classification can be preserved even for highly restrictive privacy requirements. This work has great applicability to both public and private sectors that share information for mutual benefits and productivity. <s> BIB003 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <s> K-Anonymity has been proposed as a mechanism for protecting privacy in microdata publishing, and numerous recoding "models" have been considered for achieving 𝑘anonymity. This paper proposes a new multidimensional model, which provides an additional degree of flexibility not seen in previous (single-dimensional) approaches. Often this flexibility leads to higher-quality anonymizations, as measured both by general-purpose metrics and more specific notions of query answerability. Optimal multidimensional anonymization is NP-hard (like previous optimal 𝑘-anonymity problems). However, we introduce a simple greedy approximation algorithm, and experimental results show that this greedy algorithm frequently leads to more desirable anonymizations than exhaustive optimal algorithms for two single-dimensional models. <s> BIB004 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <s> Releasing person-specific data could potentially reveal sensitive information about individuals. k-anonymization is a promising privacy protection mechanism in data publishing. Although substantial research has been conducted on k-anonymization and its extensions in recent years, only a few prior works have considered releasing data for some specific purpose of data analysis. This paper presents a practical data publishing framework for generating a masked version of data that preserves both individual privacy and information usefulness for cluster analysis. Experiments on real-life data suggest that by focusing on preserving cluster structure in the masking process, the cluster quality is significantly better than the cluster quality of the masked data without such focus. The major challenge of masking data for cluster analysis is the lack of class labels that could be used to guide the masking process. Our approach converts the problem into the counterpart problem for classification analysis, wherein class labels encode the cluster structure in the data, and presents a framework to evaluate the cluster quality on the masked data. <s> BIB005 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <s> Most previous research on privacy-preserving data publishing, based on the k-anonymity model, has followed the simplistic approach of homogeneously giving the same generalized value in all quasi-identifiers within a partition. We observe that the anonymization error can be reduced if we follow a non-homogeneous generalization approach for groups of size larger than k. Such an approach would allow tuples within a partition to take different generalized quasi-identifier values. Anonymization following this model is not trivial, as its direct application can easily violate k-anonymity. In addition, non-homogeneous generalization allows for additional types of attack, which should be considered in the process. We provide a methodology for verifying whether a non-homogeneous generalization violates k-anonymity. Then, we propose a technique that generates a non-homogeneous generalization for a partition and show that its result satisfies k-anonymity, however by straightforwardly applying it, privacy can be compromised if the attacker knows the anonymization algorithm. Based on this, we propose a randomization method that prevents this type of attack and show that k-anonymity is not compromised by it. Nonhomogeneous generalization can be used on top of any existing partitioning approach to improve its utility. In addition, we show that a new partitioning technique tailored for non-homogeneous generalization can further improve quality. A thorough experimental evaluation demonstrates that our methodology greatly improves the utility of anonymized data in practice. <s> BIB006 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <s> A challenging task in privacy protection for public data is to realize an algorithm that generalizes a table according to a user's requirement. In this paper, we propose an anonymization scheme for generating a k-anonymous table, and show evaluation results using three different tables. Our scheme is based on full-domain generalization and the requirements are automatically incorporated into the generated table. The scheme calculates the scores of intermediate tables based on user-defined priorities for attributes and selects a table suitable for the user's requirements. Thus, the generated table meets user's requirements and is employed in the services provided by users without any modification or evaluation. <s> BIB007 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <s> p-Sensitive k-anonymity model has been recently defined as a sophistication of k-anonymity. This new property requires that there be at least p distinct values for each sensitive attribute within the records sharing a set of quasi-identifier attributes. In this paper, we identify the situations when the p-sensitive k-anonymity property is not enough for the sensitive attributes protection. To overcome the shortcoming of the p-sensitive k-anonymity principle, we propose two new enhanced privacy requirements, namely p^+-sensitive k-anonymity and (p,@a)-sensitive k-anonymity properties. These two new introduced models target at different perspectives. Instead of focusing on the specific values of sensitive attributes, p^+-sensitive k-anonymity model concerns more about the categories that the values belong to. Although (p,@a)-sensitive k-anonymity model still put the point on the specific values, it includes an ordinal metric system to measure how much the specific sensitive attribute values contribute to each QI-group. We make a thorough theoretical analysis of hardness in computing the data set that satisfies either p^+-sensitive k-anonymity or (p,@a)-sensitive k-anonymity. We devise a set of algorithms using the idea of top-down specification, which is clearly illustrated in the paper. We implement our algorithms on two real-world data sets and show in the comprehensive experimental evaluations that the two new introduced models are superior to the previous method in terms of effectiveness and efficiency. <s> BIB008 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <s> When developing personal DNA databases, there must be an appropriate guarantee of anonymity, which means that the data cannot be related back to individuals. DNA lattice anonymization (DNALA) is a successful method for making personal DNA sequences anonymous. However, it uses time-consuming multiple sequence alignment and a low-accuracy greedy clustering algorithm. Furthermore, DNALA is not an online algorithm, and so it cannot quickly return results when the database is updated. This study improves the DNALA method. Specifically, we replaced the multiple sequence alignment in DNALA with global pairwise sequence alignment to save time, and we designed a hybrid clustering algorithm comprised of a maximum weight matching (MWM)-based algorithm and an online algorithm. The MWM-based algorithm is more accurate than the greedy algorithm in DNALA and has the same time complexity. The online algorithm can process data quickly when the database is updated. <s> BIB009 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <s> Today, the publication of microdata poses a privacy threat. Vast research has striven to define the privacy condition that microdata should satisfy before it is released, and devise algorithms to anonymize the data so as to achieve this condition. Yet, no method proposed to date explicitly bounds the percentage of information an adversary gains after seeing the published data for each sensitive value therein. This paper introduces β-likeness, an appropriately robust privacy model for microdata anonymization, along with two anonymization schemes designed therefore, the one based on generalization, and the other based on perturbation. Our model postulates that an adversary's confidence on the likelihood of a certain sensitive-attribute (SA) value should not increase, in relative difference terms, by more than a predefined threshold. Our techniques aim to satisfy a given β threshold with little information loss. We experimentally demonstrate that (i) our model provides an effective privacy guarantee in a way that predecessor models cannot, (ii) our generalization scheme is more effective and efficient in its task than methods adapting algorithms for the k-anonymity model, and (iii) our perturbation method outperforms a baseline approach. Moreover, we discuss in detail the resistance of our model and methods to attacks proposed in previous research. <s> BIB010 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <s> In today's global information society, governments, companies, public and private institutions and even individuals have to cope with growing demands for personal data publication from scientists, statisticians, journalists and many other data consumers. Current researches on privacy-preserving data publishing by sanitization focus on static dataset, which have no updates. In real life however, data sources are dynamic and usually the updates in these datasets are mainly arbitrary. Then, applying any popular static privacy-preserving technique inevitably yields to information disclosure. Among the few works in the literature that relate to the serial data publication, none of them focuses on arbitrary updates, i.e. with any consistent insert/update/delete sequence, and especially in the presence of auxiliary knowledge that tracks updates of individuals. In this communication, we first highlight the invalidation of existing algorithms and present an extension of the m-invariance generalization model coined τ-safety. Then we formally state the problem of privacy-preserving dataset publication of sequential releases in the presence of arbitrary updates and chainability-based background knowledge. We also propose an approximate algorithm, and we show that our approach to τ-safety, not only prevents from any privacy breach but also achieve a high utility of the anonymous releases. <s> BIB011 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Minimal Anonymity Algorithms <s> The term Data Privacy is associated with data collection and dissemination of data. Privacy issues arise in various area such as health care, intellectual property, biological data etc. It is one of the challenging issues when sharing or publishing the data between one to many sources for research purpose and data analysis. Sensitive information of data owners must be protected. There are two kinds of major attacks against privacy namely record linkage and attribute linkage attacks Earlier, researchers have proposed new methods namely k-anonymity, l-dlverslty, t-closeness for data privacy. K-anonymity method preserves the privacy against record linkage attack alone. It fails to address attribute linkage attack. l-diversity method overcomes the drawback of k-anonymity method. But it fails to address identity disclosure attack and attribute disclosure attack in some exceptional cases. t-closeness method preserves the privacy against attribute linkage attack but not identity disclosure attack. But it computational complexity is large. In this paper, the authors propose a new method to preserve the privacy of individuals' sensitive data from record and attribute linkage attacks. In the proposed method, privacy preservation is achieved through generalization of quasi identifier by setting range values and record elimination. The proposed method is implemented and tested with various data sets. <s> BIB012
The µ-argus algorithm  is the earliest work achieving privacy preserving by generalization and suppression. It can handle a class of disclosure control rules based on c 2014 NSP Natural Sciences Publishing Cor. The bin size represents the number of records matching the characteristics. User provides an overall bin size and mark sensitive attribute by assigning a value to each attribute which ranges from 0 to 3. Then µ-argus algorithm identifies and handles combination (equivalent class) with small size. The handling covers two disclosure control measures, namely subtree generalization and cell suppression. They are called global recoding and local suppression in the work respectively which are applied simultaneously to dataset. Eventually, it implements k-anonymity by computing the frequency of all 3-value combinations of domain values and greedily using anonymity operation. µ-argus algorithm has a serious limit that it is only suitable for combination of 3 attributes. Therefore the anonymous dataset may not meet the requirement of k-anonymity when the size of quasi-identifier reaches more than three. Datafly  system proposed by Sweeney in 1998 guarantees anonymity using medical data by automatically generalizing, substituting, inserting and removing specific information without losing substantial information of original dataset. In the work, it summarizes three major difficulties in providing anonymous dataset. The first problem is that anonymity is in the eye of the beholder. The second is that concerns of unique and unusual information appearing within the dataset when producing anonymous dataset. The last one is that how to measure the degree of anonymity in released data. Datafly system is constructed in the process of considering three difficulties above. Datafly is an interactive model that users provide it with an overall anonymity level that determines the minimum bin size allowable for each field. Like bin size in µ-argus algorithm, the minimal bin size reflects the smallest number of records matching the characteristics. As the minimal bin size increases, the more anonymous the dataset is. The Datafly system calculates the size of each equivalent class emerged by quasi-identifiers stored in an array and generalizes those equivalent classes whose size is less than k based on a heuristic search metric which select the quasi-identifier with the largest number of distinct values. By the way, Datafly system uses full-domain generalization and record suppression to implements data anonymization. It is the first time that genetic algorithm is introduced to achieve privacy preserving which is proposed by Iyengar BIB001 . The core of this work is that how to model the problem of privacy preserving data publishing and makes the model fit for genetic algorithm. With the help of taxonomy tree structure, it encodes each state of generalization as a chromosome. At each time of iterative procedure, new solutions (that is new chromosome) are generated to achieve better result by the means of crossover and mutation. A better solution is based on the information metric. Applying a solution mainly includes two parts, namely conduct generalization operation exactly subtree generalization and carry out suppression as needed. Because execution of genetic algorithm needs setting some parameters, like size of the population, the probability of mutation and the times of iteration, in this work, the size of chromosome is 5000, 0.5 million times of iteration, and probability of mutation was set to 0.002. It takes approximately 18 hours to transform the training set of 30k record. From the result of experiment and the consumed time, we can infer that using genetic algorithm to achieve privacy preserving is time consuming, impractical and inefficient for very large dataset. Wang et al. BIB002 propose bottom-up generalization which is a data mining solution to privacy preserving data publishing. The brief description of this algorithm is that it computes the IP(G) of each generalization G, find the best generalization G best according to forgoing IP(G) which is the information metric of this algorithm, and applies the best generalization G best for dataset until the anonymous dataset satisfy the requirement of k-anonymity. It is well known that calculating all IP(G) for each generalization G is impossible. critical generalization replaces the operation of computing the IP(G) of each generalization G. The purpose of modifying algorithm steps is to reduce unnecessary calculation by the means of pruning redundant generalization judged by proved theory. It uses TEA (Taxonomy Encoded Anonymity) index, two observations and one theorem prune unnecessary generalization to improve the efficiency of this algorithm. TEA index for the sequence of quasi-identifiers is a tree of k level, each level of TEA index represents current generalization state of a quasi-identifier. Each leaf node stores the size of equivalent class that is determined by the path from this leaf node to the root. With the theorem shows below, it is sufficient to find the critical generalization. Theorem 1 G is critical only if every anonymity vid is generalized by some size-k segment of G, where k>1. At most |VID| generalizations satisfy this "only if" condition, where |VID| denotes the number of attributes in VID (VID is the set of quasi-identifiers). Top-down specialization BIB003  for privacy preserving can be learned about by comparing with bottom-up generalization. Specialization is a reverse operation of generalization. TDS (Top-Down Specialization) starts at the most general state of dataset according to taxonomy tree structure of quasi-identifiers, and choose best specialization attributes measured by trade-off metric to specialize dataset till further specialization would breach anonymity requirement. Compared with bottom-up generalization, TDS algorithm is more flexible that it can stop at any specialized state of dataset according to users' requirement. Another merit of TDS is that it takes multi-sequence of quasi-identifiers into account. Mondrian multidimensional algorithm proposed by LeFevre BIB004 is a kind of anonymity algorithm to achieve minimal anonymity by the means of top-down specialization. The difference between TDS scheme and Modrian Multidimensional algorithm can specializate one equivalent class not all equivalent class containing the specific value of selected quasi-identifier. Fung et al. also proposes k-anonymity algorithm to precede privacy preserving for cluster analysis in BIB005 . Using multidimensional suppression for k-anonymity is proposed by Slava et al.  . The algorithm (KACTUS: K-Anonymity Classification Tree Using Suppression) can generate effective anonymous dataset applied for the scenario of classification model. Value suppression is applied only on certain tuples depending on other quasi-identifier values. Because of only using suppression, it is unnecessary to build taxonomy tree structure for each quasi-identifier which is a relaxation compared with priori works equipped with predetermined taxonomy tree for categorical attributes and runtime-generated taxonomy tree structure for numeric attributes. The goal of this work is to generate anonymous dataset to reach the target that the classifier performance trained on anonymous dataset is approximately similar to the performance of classifier trained on the original dataset. KACTUS is composed of two main phases. In the first phase, it generates a classification tree trained on the original dataset. Some diverse top-down classification inducers are prepared for generating classification tree (e.g. C4.5 algorithm). Need to mention, the decision tree is trained on the collection of the given quasi-identifiers. In the second phase, the classification tree generated in the first phases is used by algorithm to emerge the anonymous dataset. The process of data anonymization on classification tree proceeds on bottom-up manner. Every leaf node of classification tree take notes of the number of records has the same equivalent class which is represented by the path from root node to leaf node. If all of leaf nodes in classification tree meet the requirement of k-anonymity, there is no need to suppress any quasi-identifiers existed in the classification tree currently. While, if leaves do not meet the requirement of k-anonymity, it can obtain a new leaf which may comply with k-anonymity by adequately pruning them. The anonymity operations of generalization and suppression are still widely used in latest research. Generalization is employed in BIB009 for improve DNALA. An appropriately robust privacy model is proposed for data anonymity which is called β -likeness in BIB010 , one of the anonymization schemes is based on generalization. In  , it focuses on the generalization hierarchy of numeric attributes, extends previous method and validates their proposal with the help of existed information metric. Information-based algorithm is proposed by Li et al.  for classification utility using generalization and suppression. Sun et al. BIB008 improves p-Sensitive k-anonymity model and proposes two private requirements, namely p + -sensitive k-anonymity and (p, α)-sensitive k-anonymity properties. It generates anonymous dataset with a top-down specialization manner by specializing values step by step. Wong et al. find that anonymization error can be reduced by employing a non-homogeneous generalization BIB006 . Generalization hierarchy is incorporated to implement user-oriented anonymization for public data in BIB007 . Adeel et al. BIB011 also use generalization operation coping with the problem of sequential release under arbitrary update. Mahesh et al. BIB012 propose a new method to preserve individuals sensitive data from record and attribute linkage attacks by setting range values and record elimination.