Two privacy-preserving approaches for data publishing with identity reservation

Consider an original data table \(D=\{ID, A_{1}, \ldots , A_{d}, A_{s}\}\) in which there are no duplicate records, where \(A_{1}, \ldots , A_{d}\) are QI attributes.¹ For the convenience of reference, Table 1 summarizes the meanings of symbols used in the paper.

In privacy-preserving data publishing, for every privacy model \(\pi \), there is a corresponding anonymization approach to transforming the original data table to an anonymous table which satisfies \(\pi \). And privacy models k-anonymity, distinct l-diversity, and \((\alpha , k)\)-anonymity all assume that an individual has only one record. For these privacy models, their anonymous tables are in the form of \(D^{*}(QI', A_{s})\), where \(QI'\) is an anonymous version of the original QI obtained by applying anonymization approach to QI in original table D. For the problem of identity-reserved anonymity, we need to keep the information in which multiple records belong to the same individual, so the explicit identifier should not be directly deleted and we use numbers to identify different individuals. The published anonymous table of D is in the form of \(D^{*}(Id\_num, QI', A_{s})\), where the values of \(Id\_num\) are numbers, which denote different individuals. Some notions directly related to our approaches are presented in the following.

The first one is equivalence class [3], which is the elementary unit of anonymous table. Formally, we have:

The second is the definitions of k-anonymity [3], distinct l-diversity [10], and \((\alpha , k)\)-anonymity [11], which are suitable for the situation where an individual has a record only.

Distinct l-diversity and \((\alpha , k)\)-anonymity can prevent identity disclosure and attribute disclosure, and k-anonymity can only prevent identity disclosure [2].

The following is the definitions of IRk-anonymity, IR (k, l)-anonymity, and IR\((\alpha , \beta )\)-anonymity [13], which are obtained by extending k-anonymity, distinct l-diversity, and \((\alpha , k)\)-anonymity to the scenario where an individual could have multiple records, respectively.

Obviously, \(|R(s_{j})|/|Q|\le \beta \), the condition for IR\((\alpha , \beta )\)-anonymity, is equal to \(|P(s_{j})|/|Q|\le \beta \) because \(s_{j}\) appears in any individual at most once.

In order to satisfy the requirement of given privacy model \(\pi \), the original table usually needs to be generalized in the values of quasi-identifier. The idea is to replace a specific value by a general value. Although the generalization operation reduces the data quality of an original table, it still can retain its semantic information to some extent. Therefore, the method attracts increasing attention in the field of privacy-preserving data publishing. For an anonymization algorithm, it first needs to satisfy the given privacy model and then considers to keep data quality (when an equivalence class satisfies the given privacy model, it is unnecessary to generalize its attributes’ values to higher levels) and spend time as little as possible. In general, the stronger the privacy preservation of a privacy model is, the worse its data quality is and the more runtime it needs. Many existing approaches generalize the values of attributes in quasi-identifier according to predefined taxonomy trees [10‐23], which are given by the domain experts. For example, Fig. 1 shows the taxonomy trees for categorical attribute Postcode and numeric attribute age.²

Wang et al. [24] pointed out that the taxonomy tree restricts the choice of data generalization and causes some unnecessary information loss. If the values of Postcode in two records are 10076 and 10085, respectively, we can generalize them to \(\{10076, 10085\}\) in order to make the two records into an equivalence class. However, they are generalized to \(100^{*}\) according to the taxonomy tree. If the values of Age in two records are 34 and 35, respectively, we can generalize them to [34, 35] for forming an equivalence class. However, they are generalized to [30, 39] according to the taxonomy tree. Thus, Wang et al. [24] supplied a different scheme of data generalization, focusing on both numeric and categorical attributes.

An interval number \([a, b]\,(a\le b)\) is used to denote a numeric attribute’s value between a and b. For a point value, we have \(a=b\). Given \(\omega \) records, the values in a numeric attribute \(A\in QI\) are \(r_{i}[A]=[a_{i}, b_{i}], i\in \{1, 2,\ldots , \omega \}\), respectively. We can generalize them to the interval number \([\min \{a_{i}\}, \max \{b_{i}\}]\). A set V is considered as the value of a categorical attribute. If it is point-valued, V is a set that contains only an element. Given \(\omega \) records, the values in a categorical attribute \(A'\in QI\) are \(r_{i}[A']=V_{i}, i\in \{1, 2,\ldots , \omega \}\), respectively, which are generalized to \(\bigcup \nolimits _{1\le i\le \omega }V_{i}\). And \(r_{1}, r_{2},\ldots , r_{\omega }\) are generalized and have the same values of attributes in QI, which constitute an equivalence class. The identity element of the equivalence class is denoted as \(\overline{r}=\delta (r_{1}, r_{2},\ldots , r_{\omega })\), where \(\overline{r}[A]=[\min \{a_{i}\}, \max \{b_{i}\}]\) for each numeric attribute \(A\in QI\), \(\overline{r}[A']=\bigcup \nolimits _{1\le i\le \omega }V_{i}\) for each categorical attribute \(A'\in QI\), and \(\overline{r}[A_{s}]=null\).

There exists information loss due to data generalization. So various metrics have been proposed for calculating how much information is lost. For the generalization with taxonomy tree, normalized certainty penalty (NCP) [21, 25] and generalized loss metric (GLM) [26, 27] are the two main metrics proposed. They are the same for numerical attributes but different for categorical ones. That is, for a numerical attribute A, and an interval \(I=[l, u]\) from the domain [L, U] of A, used to generalize A’s value, the information loss associated with I is defined as follows:For a categorical attribute \(A'\), where T is its taxonomy tree and a node p in T is used to generalize \(A'\)’s value, the information loss associated with p is defined as follows (for NCP and GLM, respectively):where \(u_{p}\) is the set of leaf nodes of the subtree rooted at p in T and u is the set of all the leaf nodes in T.

For example, a record has values 32 and 10073 for Age and Postcode attributes, respectively, whose taxonomy trees are shown in Fig. 1. Assume that 32 and 10073 are generalized to [30, 34] and 1007*. The information loss for Age by using NCP and GLM is the same: \(\frac{34-30}{39-30}=\frac{4}{9}\). We can see that [30, 34] actually contains 30, 31, 32, 33, and 34, and there are five different numbers, while \(34-30=4\). Similarly, [30, 39] actually contains ten different numbers, while \(39-30=9\). The information loss for categorical attribute Postcode by using NCP is \(\frac{4}{7}\), while it is \(\frac{4-1}{7-1}=\frac{1}{2}\) by using GLM. \(1007^{*}\) is equal to {10070, 10073, 10076, 10077} and there are four different numbers. The set of all the leaf nodes in the taxonomy tree of Postcode is {10070, 10073, 10076, 10077, 10085, 10086, 10087} and there are seven different numbers. We can see that the definitions of GLM are consistent with respect to numeric and categorical attributes, while NCP is not. So GLM is more suitable.

For NCP and GLM, they consider only the information loss between an original value and a generalized value of an attribute. When we create an equivalence class by continually adding the records of individuals until it satisfies given privacy model, it is necessary to compute the information loss from current equivalence class to the later equivalence class obtained by adding the records of an individual to current equivalence class. As a result, we need to consider the information loss caused by one generalization value to another. The definition of information loss between a generalized value (or original value) and another needs to be given.

For the generalization method without predefined taxonomy trees, Wang et al. [24] presented the information metrics for categorical and numerical attributes, as given by Eqs. (6) and (7), respectively. However, the results of Eqs. (6) and (7) are not normalized, i.e. the results (except 0) all are greater than 1. Also, it is unreasonable to denote the information loss by using the times (the number related to the later generalized value is divided by the number related to the original value or before generalized value), because the denominator is varied and so the standard is not uniform. In this paper, based on GLM we will improve the information metrics for numeric and categorical attributes, which are described in Sect. 4.1.

For a record r, the value is \(r[A]=[a, b]\) on a numeric attribute A, which is the original value or a generalized value, and the (later) generalized value is \(r^{*}[A]=[a^{*}, b^{*}]\). Then the information loss of r on attribute A is given byFor a record r, the value is the set \(r[A']\) on a categorical attribute \(A'\), which is the original value or a generalized value, and the (later) generalized value is the set \(r^{*}[A']\). Then the information loss of r on attribute \(A'\) is

When r[A] is the original value, we have \(b-a=0\), which is consistent with GLM/NCP as a result for numeric attribute. When [a, b] is a generalized value, \(Loss(r[A], r^{*}[A])=\frac{b^{*}-a^{*}}{U-L}-\frac{b-a}{U-L}\) denotes the increment of information loss from [a, b] to \([a^{*}, b^{*}]\).

When \(r[A']\) is the original value, \(|r[A']|=1\); it is consistent with GLM as a result for categorical attribute. When \(r[A']\) is a generalized value, \(Loss(r[A'], r^{*}[A'])=\frac{|r^{*}[A']|-1}{|X|-1}-\frac{|r[A']|-1}{|X|-1}\) denotes increment of information loss from \(r[A']\) to \(r^{*}[A']\).

For our anonymization approach, if there exists an individual \(p_{i}\), which is added to any an equivalence class and the equivalence class does not satisfy given privacy requirement, or is added to the equivalence class, whose distance to \(p_{i}\) is minimum, and data quality of the equivalence class is decreased seriously, we need to suppress the records of the individual. The suppression of a value of an attribute is to replace it by a special mark (i.e. \(*\), a special generalization), indicating that the replaced values are not disclosed, and its information loss is 1.

Some approaches consider the problem of data anonymization as a clustering problem satisfying k-anonymity or l-diversity [18, 19, 24]. They gave some definitions about distance between two records, distance between a record and an equivalence class, and distance between two equivalence classes. In this subsection, we will also give some definitions about distances from information loss perspective, including distance between two individuals, distance between an individual and an equivalence class, and distance between two equivalence classes. Different from the concepts of distances in [18, 19, 24], we consider that an individual could have multiple records, and use Eqs. (11) and (12) to calculate the information loss for numeric attributes and categorical attributes, respectively.

To make \(R(p_{1})\cup R(p_{2})\) become an equivalence class, we need to generalize these records to \(\overline{r}_{p_{1}p_{2}}\). In Eq. (16), the first product term denotes the information loss caused by generalizing the records in \(R(p_{1})\) to \(\overline{r}_{p_{1}p_{2}}\) and the second is the information loss caused by generalizing the records in \(R(p_{2})\) to \(\overline{r}_{p_{1}p_{2}}\).

For example, in Table 2, \(r_{5}\) and \(r_{6}\) both belong to individual 4, whose original identity element is \(\{F , 33, 10087, null \}\), and \(r_{8}\) and \(r_{9}\) both belong to individual 6, whose original identity element is \(\{F , 34, 10070, null \}\). If we put the records of individuals 4 and 6 into an equivalence class, the identity element of the equivalence class is \(\{F , [33, 34], \{10070, 10087\}, null \}\), i.e. the records of individuals 4 and 6 are all generalized to \(\{F , [33, 34], \{10070, 10087\}, null \}\). Then the information loss caused by the generalization is the distance between individuals 4 and 6.

To make \(R(p)\cup Q\) become an equivalence class, we need to generalize these records to \(\overline{r}_{pq}\). In Eq. (17), the first product term denotes the information loss caused by generalizing the records in \(R(p_{1})\) to \(\overline{r}_{pq}\) and the second is the information loss caused by generalizing the records in Q to \(\overline{r}_{pq}\).

To make \(Q_{1}\cup Q_{2}\) become an equivalence class, we need to generalize these records to \(\overline{r}_{q_{12}}\). In Eq. (18), the first product term denotes the information loss caused by generalizing the records in \(Q_{1}\) to \(\overline{r}_{q_{12}}\) and the second is the information loss caused by generalizing the records in \(Q_{2}\) to \(\overline{r}_{q_{12}}\).

Wang et al. [24] presented a clustering algorithm for data anonymization achieving l-diversity. In this subsection, by improving their method, we will propose the heuristic greedy clustering algorithm DAnonyIR, as shown in Algorithm 1. It generalizes the original data table to an anonymous table which satisfies given privacy requirement for identity reservation. To explain our algorithm, first we need the following concept:

DAnonyIR The whole clustering algorithm DAnonyIR is shown in Algorithm 1. Its input is the original data table, QI attributes, and some parameters about privacy requirement \(\pi \). The output is an anonymous table. The basic idea of the algorithm is as follows: when \(D\ne \emptyset \), we try to create an equivalence class Q from D; if Q satisfies \(\pi \), we add it to \(D^{*}\); if \(D=\emptyset \) and Q still does not satisfy \(\pi \), the individuals in Q are residual and we use Handle function to deal with them. Firstly, on line 1, we preprocess the original data. That is, recode the explicit identifier of D with numbers. As the information where several records belong to the same individual needs to be kept, the explicit identifier is replaced with a different number to denote a different individual. On lines 2–19, we try to create continually equivalence classes until \(D=\emptyset \). The process of creating an equivalence class is shown on lines 3–15, First, select randomly individual p from D and initialize equivalence class Q with these records of p. \(\overline{r}_{q}\) is the identity element of Q. Now Q only contains an individual and it does not satisfy \(\pi \), so we set \(SatFlag=False\), where variable SatFlag denotes whether Q satisfies \(\pi \). When Q does not satisfy \(\pi \) and \(D\ne \emptyset \), we perform repeatedly lines 7–14. On lines 7 and 8, we get the individual \(p'\) and the equivalence class \(Q'\) from D and \(D^{*}\), whose distances to Q are minimum, respectively. Because the current Q does not satisfy \(\pi \), we need to add more individuals. We can add \(p'\) to Q, or combine Q with \(Q'\). In order to reduce the information loss, we select the way in which less information loss is caused. If \(Dist(p', Q)\le Dist(Q', Q)\), we add \(R(p')\) to Q and update the identity element of Q; otherwise, we merge Q with \(Q'\) and update the identity element of Q. On line 14, we call function SaPriIR to judge whether Q satisfies \(\pi \). On lines 16 and 18, if \(SatFlag=True\), i.e. Q satisfies \(\pi \), we add Q to \(D^{*}\). On lines 20–26, when the lines 2–19 are executed and \(D=\emptyset \), if the last equivalence class Q does not satisfy \(\pi \), for every individual in Q, we call function Handle to decide to add its records to an equivalence class or suppress it. Because these individuals are directly put in \(D^{*}\), it will lead to privacy leakage. After that, we obtain the set \(D^{*}\) of equivalence classes which are not generalized. Then for \(Q_{i}\in D^{*}\) and every record in \(Q_{i}\), we substitute its values on QI attributes with its identity element, so the anonymous table satisfying \(\pi \) is obtained.

SatPriIR For function SatPriIR, the procedure is different for a different privacy model with identity reservation. For IR (k, l)-anonymity, IR\((\alpha , \beta )\)-anonymity, EIRl-diversity, and EIR\((\alpha , \beta )\)-anonymity, it is substituted with SatPriIR\(\_kl\), SatPriIR\(\_\alpha \beta \), SatPriIR\(\_El\), and SatPriIR\(\_E\alpha \beta \), respectively. The privacy models EIRl-diversity and EIR\((\alpha , \beta )\)-anonymity are proposed in the paper, so we describe the functions SatPriIR\(\_El\) and SatPriIR\(\_E\alpha \beta \) in detail, as shown in Algorithms 2 and 4, respectively. For SatPriIR\(\_kl\), we scan Q once to obtain the number \(n_{Q}\) of individuals and the number \(m_{Q}\) of sensitive values appearing in Q. If \(n_{Q}\ge k\) and \(m_{Q}\ge l\), then Q satisfies the IR (k, l)-anonymity, and return True; otherwise, return False. For SatPriIR\(\_\alpha \beta \), the algorithm is similar to SatPriIR\(\_E\alpha \beta \), and the difference is on line 12 in Algorithm 4. According to Definition 2.3 (3), if \(MaxRecNum/|Q|\le \alpha \) and \(MaxSenNum/|Q|\le \beta \), then Q satisfies IR\((\alpha , \beta )\)-anonymity, and return True; otherwise, return False.

SatPriIR_El In Algorithm 2, on line 1, we get the collection of subsets \(\varPsi \), in which \(S(p_{i})\) is the set of sensitive values of the individual \(p_{i}\). On line 2, we set a variable \(\xi \) to store single element sets in \(\varPsi \). From lines 3 to 8, we find all single element sets, delete them from \(\varPsi \) and add them to set \(\xi \). On lines 9–16, if \(|\xi |=\emptyset \), we directly call function BHS [28] to get all minimal hitting sets of \(\varPsi \), and find a minimum hitting set h. Function BHS is described in Algorithm 3. According to Theorem 3.1, if \(|h|\ge l\), then Q satisfies EIRl-diversity, and return True; otherwise, return False. On lines 17 and 18, if \(|\xi |\ne \emptyset \) and \(|\xi |\ge l\), then the cardinality of any minimum hitting set is not less than l, because \(\xi \) is contained in any minimal hitting set, also any minimum hitting set. So return True. From lines 19 to 31, we consider another case, \(0<|\xi |<l\). On lines 20 to 24, we use \(\xi \) to further simplify \(\varPsi \) according to the definition of a hitting set. \(\forall S(p_{i})\in \varPsi \), if \(S(p_{i})\cap \xi \ne \emptyset \), then \(\varPsi =\varPsi \backslash S(p_{i})\). On lines 25 and 26, we call BHS to get all minimal hitting sets of current \(\varPsi \), and then find a minimum hitting set \(h'\). If \(|h'|+|\xi |\ge l\), return True; otherwise, return False. In fact, we divide \(\varPsi \) to two parts: One contains the sets whose intersection with \(\xi \) is not \(\emptyset \) and the other contains the sets whose intersection with \(\xi \) is \(\emptyset \). \(\xi \) is the only minimum hitting set of the first part. We need to find a minimum hitting set \(h'\) of the second part. \(h'\cup \xi \) is a minimum hitting set of the whole \(\varPsi \).

BHS We combine an example to explain Algorithm 3. LetOn line 1, we transform \(\varPsi \) towhere xy (or \(x\cdot y\)) and \(x+y\) denote the AND and OR results of x and y, respectively. For any hitting set of \(\varPsi \), e.g. \(\{x_{1}, x_{4}, x_{5}\}\), we have \(\varPi \cdot x_{1}x_{4}x_{5}=0\). On lines 2 and 3, when \(\varPi \) only contains a conjunctive item, and assume that \(\varPi =\overline{x_{1}}\,\overline{x_{3}}\), return \(x_{1}+x_{3}\), i.e. \(\{x_{1}\}\) and \(\{x_{3}\}\) are minimal hitting sets, because \(\varPi \cdot x_{1}=0\) and \(\varPi \cdot x_{3}=0\). In this example, \(\varPi \) has 8 conjunctive items, the algorithm executes the fifth line. We simplify \(\varPi \) with the absorption law \(A+AB=A\) and obtainOn lines 6 and 7, if every conjunctive item in \(\varPi \) contains literal \(\overline{s}\), then s is the only a minimal hitting sets, because \(\varPi \cdot s=0\). In this example, \(\overline{x_{4}}\) is a single literal item, and line 9 is executed. We have \(sig=x_{4}\), which is contained in all hitting sets. We delete \(\overline{x_{4}}\) from \(\varPi \), andSelect literal \(\overline{x_{1}}\) whose frequency appearing in \(\varPi \) is highest for accelerating convergence. We haveThe first part is these minimal hitting sets containing \(x_{1}\) and the second part is the ones which do not contain \(x_{1}\). For \(BHS(\overline{x_{3}}\,\overline{x_{5}}+\overline{x_{5}}\,\overline{x_{7}})\), because the two conjunctive items both contain \(\overline{x_{5}}\), so return \(x_{5}\).So the final return result isand \(\{x_{1}, x_{4}, x_{5}\}\), \(\{x_{3}, x_{4}, x_{5}, x_{6}\}\), and \(\{x_{3}, x_{4}, x_{6}, x_{7}\}\) are minimal hitting sets.

SatPriIR\(\_E\alpha \beta \) For Algorithm 4, from lines 2 to 10, we obtain the MaxRecNum which denotes the maximum number of records of individuals in Q and count the number of occurrences of any sensitive value appearing in Q. On line 11, we find MaxSenNum which is the maximum value in \(\{Num_{s_{1}},\ldots , Num_{s_{m_{Q}}}\}\), where \(s_{1}, \ldots , s_{m_{Q}}\) are sensitive values appearing in Q and \(Num_{s_{j}}\) is the number of occurrences of \(s_{j}\). By Theorem 3.2, if \(MaxRecNum/|Q|\le \alpha \) and \(MaxSenNum/n_{Q}\le \beta \), Q satisfies EIR\((\alpha , \beta )\)-anonymity, so return True; otherwise, return False.

In fact, when some records of an individual are added to Q, in order to check whether the current Q satisfies privacy requirement \(\pi \), we do not call SatPriIR_kl, SatPriIR_El, SatPriIR\(\_\alpha \beta \), or SatPriIR\(\_E\alpha \beta \). Because these individuals are added to Q one by one (when we combine an equivalence class \(Q'\) to Q, we may consider as the individuals of \(Q'\) are added to Q one by one), we can use incremental methods to check whether Q satisfies \(\pi \), denoted by SatPriIRInc_kl, SatPriIRInc_El, SatPriIRInc\(\_\alpha \beta \), and SatPriIRInc\(\_E\alpha \beta \), respectively. SatPriIRInc_El and SatPriIRInc\(\_E\alpha \beta \) are shown in Algorithms 5 and 6, respectively. For SatPriIRInc_kl, when an individual p is added to Q, we only need to update the number \(n_{Q}\) of individuals and the number \(m_{Q}\) of sensitive values appearing in Q according to p. For SatPriIRInc\(\_\alpha \beta \), the updated process to MaxRecNum and MaxRecNum is the same as SatPriIRInc\(\_E\alpha \beta \).

SatPriIRInc_El The idea of \(SatPriIRInc\_El\) is introduced by [28]. For the set of records Q,contains all minimal hitting sets of \(\varPsi =\{S(p_{1}), S(p_{2}),\ldots , S(p_{n_{Q}})\}\). In fact,For convenience, we represent \(\mathcal {H}_{Q}\) with Boolean formula. When an individual p is added to Q, we use Algorithm 5 to get all minimal hitting sets \(\mathcal {H}_{Qp}\) of \(\varPsi \cup S(p)\). If \(Q=\emptyset \), then \(\mathcal {H}_{Qp}=s_{1}+s_{2}+\cdots +s_{r}\), i.e. \(\mathcal {H}_{Qp}=\{s_{1},s_{2},\ldots ,s_{r}\}\); otherwise, we use the method shown on line 4 to get \(\mathcal {H}_{Qp}\) and simplify it with Boolean algebra. Then find a minimum hitting set h from \(\mathcal {H}_{Qp}\). If \(h\ge l\), return True; otherwise, return False.

SatPriIRInc_E\(\alpha \beta \) When an individual p is added to Q, Algorithm 6 is used to check whether at the moment Q satisfies EIR\((\alpha , \beta )\)-anonymity. We only need to check whether \(|R(p_{i})|\) is greater than MaxRecNum and the numbers of occurrences of \(s_{1}, s_{2},..,s_{r}\) in Q at the moment are greater than MaxSenNum to decide whether to update MaxRecNum and MaxSenNum.

Handle Function Handle is shown in Algorithm 7. For every residual individual \(p''\) in D, we need to decide to add its records to an equivalence class or suppress it. On lines 1 and 2, we set two variables MinDis and Min. The initial value of MinDis is a greater value. From lines 3 to 10, we find the equivalence class \(Q_{min}\) which still satisfies privacy requirement \(\pi \) after merging \(p''\) (this step is ignored for IR (k, l)-anonymity, and EIRl-diversity, as the equivalence class after adding the records of an individual satisfies still them, if an equivalence class satisfies the two privacy models) and the distance to \(p''\) is minimum. If distance MinDis is less than the information loss caused by suppressing \(R(p'')\), we merge \(p''\) to \(Q_{min}\); otherwise, we suppress \(R(p'')\).

When \(D=\emptyset \) and the equivalence class Q still does not satisfy privacy requirement \(\pi \), we call function Handle to deal with these individuals in Q. In Algorithm 7, for every residual individual \(p''\) we find \(Q_{min}\). If \(p''\) is added to \(Q_{min}\), we need to generalize the records of \(p''\) and \(Q_{min}\) to \(\overline{r}_{p''q_{min}}\), which is the identity element of the equivalence class \(Q_{p''q_{min}}\), formed by generalizing the records in \(p''\) and \(Q_{min}\), and MinDis is the information loss caused by generalization. Should we generalize or suppress \(p''\)? We select the way that causes less information loss. That is, if suppression is selected, the information loss caused by suppression is less than that caused by generalization.

Running Example We utilize our DAnonyIR by calling SatPriIRInc\(\_kl\), SatPriIRInc\(\_El\), SatPriIRInc\(\_\alpha \beta \) and SatPriIRInc\(\_E\alpha \beta \) to generalize original data table to anonymous tables, which satisfy IR (k, l)-anonymity, EIRl-diversity, IR\((\alpha , \beta )\)-anonymity, and EIR\((\alpha , \beta )\)-anonymity, denoted by DAnonyIR\(\_kl\), DAnonyIR\(\_El\), DAnonyIR\(\_\alpha \beta \), and DAnonyIR\(\_E\alpha \beta \), respectively. Assume that we apply DAnonyIR\(\_{El}\) (\(l=3\)) to anonymize data D in Table 2, in which the domains of gender, Age, and Postcode are \(\{M, F\}\), [30, 39], \(\{10085, 10076,\)\(10086, 10087, 10077, 10070, 10073\}\), respectively. First, recode the Name of D with numbers. That is, the attribute Name is substituted with Id_num, and the values of Name {Mike, Lily,..., Lucy} are substituted with {1, 2,..., 7}. So we have that \(D\ne \emptyset \).

We try to create an equivalence class Q from D. Select randomly an individual p from D, and assume that individual 6 is selected. \(D=D-R(6)\) and \(Q=R(6)\). The identity element \(\overline{r}_{q}\) of Q is \(\{F, 34, 10070, null\}\). Because Q only contains individual 6 and it does not satisfy EIR 3-diversity, we set \(SatFlag=False\). \(!SatFlag=True\) and \(D\ne \emptyset \), so we add continually an individual to Q. The individual whose distance to Q is minimum is the one with Id_num=7 for our example. The computation of distance between individual 7 and Q is as follows: \(\overline{r}_{7q}\) is the identity element of \(Q\cup R(7)\), which is \(\{F, [33, 34], \{10070, 10073\}, null\}\). Thuswhere \(\overline{r}_{7}\) is the identity element of individual 7, which is \(\{F, 33, 10073, null\}\). The distances between individuals 1, 2, 3, 4, 5 and Q are 5.556, 1.500, 4.167, 1.111, and 1.833, respectively.

We execute line 10 in Algorithm 1. \(D=D-R(7)\), \(Q=Q\cup R(7)\), and \(\overline{r}_{q}\) is \(\{F, [33, 34], \{10070, 10073\}, null\}\). When we check whether Q satisfies EIR 3-diversity, we do not call SatPriIR_El and use the incremental method SatPriIRInc_El. That is, we do not call SatPriIR_El to find a minimum hitting set ofBy using SatPriIRInc_El,The collection of all minimal hitting sets of previous \(\varPsi \) is \(\{\{Leukaemia\}, \{Heart\}\}\), and the collection of all minimal hitting sets of current \(\varPsi \) is \(\{\{Leukaemia, Syphilis\},\{Heart,Syphilis\}\}\), whose cardinalities both are less than 3. Q does not satisfy EIR 3-diversity and \(D\ne \emptyset \), so we add continually an individual to Q. The distance of individual 4 to Q are is minimum, which can be calculated as follows: \(\overline{r}_{4q}\) is the identity element of \(Q\cup R(4)\), which is \(\{F, [33, 34], \{10070, 10073, 10087\}, null\}\), and \(\overline{r}_{4}\) is the identity element of individual 4, which is \(\{F, 33, 10087,\)\(null\}\), and thusThe distances between individuals 1, 2, 3, 5 and Q are 7.501, 2.278, 5.834, and 2.722, respectively.

Then \(D=D-R(4)\), \(Q=Q\cup R(4)\), and \(\overline{r}_{q}\) is \(\{F, [33\!\sim \!34], \{10070, 10073, 10087\}, null\}\). AndBy using \(SatPriIRInc\_El\), the collection of all minimal hitting sets of \(\varPsi \) is \(\{\{Leukaemia, Syphilis, Hypertension\},\)\(\{Leukaemia, Syphilis, Diabetes\},\)\(\{Leukaemia, Syphilis, Diabetes\},\)\(\{Heart, Syphilis, Diabetes\}\}\) byin which every set is a minimum hitting set, and the cardinality is equal to 3. Q satisfies EIR 3-diversity. Algorithm 1 executes line 17; the first equivalence class is added to \(D^{*}\), i.e. \(D^{*}=\{\{r_{8}, r_{9}, r_{10}, r_{5}, r_{6}\}\}\).

\(D=\{r_{1}, r_{2}, r_{3}, r_{4}, r_{7}\}\) and \(D\ne \emptyset \). We try to create another equivalence class from D. Select randomly individual p from D. Assume that individual 3 is selected, then \(D=D-R(3)\) and \(Q=R(3)\). We have \(\overline{r}_{q}=\{M, 36, 10086, null\}\). Q only contains an individual and it does not satisfy 3-diversity. Also \(D\ne \emptyset \). Thus we add continually an individual to Q. The individual is 1, whose distance to Q is 0.500 and is minimum. The distance between Q and the first equivalence class in \(D^{*}\) is 8.778. Therefore, \(Q=Q\cup R(1)\), and \(\overline{r}_{q}=\{M, 36, \{10085, 10086\}, null\}\). Then R(2) and R(5) are added consecutively to Q, and Q satisfies EIR 3-diversity.Now \(D\ne \emptyset \) and \(SatFlag=True\), i.e. there are no residual individuals. Algorithm 1 executes line 27. For every equivalence class Q in \(Q^{*}\), we substitute its values on QI attributes with Q’s identity element.

Published anonymous table \(D^{*}\), as shown in Table 4, satisfies EIR 3-diversity, and it can prevent identity disclosure and attribute disclosure. We also take Mike as an example. Assume that an attacker knows Mike’s QI information (i.e. \(\{M, 36,\)\(10085\}\)) and knows that Mike is in published table \(D^{*}\), then the attacker can infer that Mike is in equivalence class \(Q_{2}\). There are three different individuals in \(Q_{2}\), and the attacker cannot know which one is corresponding to Mike. Thus, the identity disclosure is prevented. In \(Q_{2}\), there are two reasoning sets, i.e. \(\{r_{1}, r_{3}, r_{4}, r_{7}\}\) and \(\{r_{2}, r_{3}, r_{4}, r_{7}\}\). Every reasoning set contains at least three different sensitive values, so the attacker cannot know which sensitive disease is corresponding to Mike, and so attribute disclosure is prevented.

Similarly, we use DAnonyIR\(\_{E\alpha \beta }\) with \(\alpha =0.4\) and \(\beta =0.6\) to anonymize data D in Table 2. Assume the first selected individuals are 6 and 3 in creating equivalence classes \(Q_{1}\) and \(Q_{2}\), respectively. The anonymous table is also shown in Table 4, which satisfies EIR (0.4, 0.6)-diversity. We also take Mike as an example. According to the background knowledge of an attacker, Mike is inferred in equivalence class \(Q_{2}\). Because the percentage of any individual’s records in \(Q_{2}\) is not more than 0.4, there are multiple individuals. The attacker cannot know which one is corresponding to Mike, and the identity disclosure is prevented. As shown above, there are two reasoning sets in \(Q_{2}\). In every reasoning set of \(Q_{2}\), the percentage of any sensitive value is not more than 0.6. So the attacker cannot know which sensitive disease is corresponding to Mike with certain probability \((>\!0.6)\) and attribute disclosure is prevented.

In this subsection, we discuss the vulnerability of IR (k, l)-anonymity and IR\((\alpha , \beta )\)-anonymity. The experimental results for IR (k, l)-anonymity and IR\((\alpha , \beta )\)-anonymity are as shown in Figs. 2 and 3, respectively. We can see that GeneIR\(\_kl\) and DAnonyIR\(\_kl\) (GeneIR\(\_\alpha \beta \) and DAnonyIR\(\_\alpha \beta \)) both generate many vulnerable equivalence classes, and the percentage of vulnerable equivalence classes for DAnonyIR\(\_kl\) (DAnonyIR\(\_\alpha \beta \)) is more than that for GeneIR\(\_kl\) (GeneIR\(\_\alpha \beta \)). GeneIR continually repeats the process: randomly selects an attribute in QI to generalize according to the predefined taxonomy tree, then checks D to gain equivalence classes, which satisfy IR (k, l)-anonymity or IR\((\alpha , \beta )\)-anonymity, and moves them to \(D^{*}\). While DAnonyIR uses the set generalization and considers the distance among individuals in an equivalence class. If an equivalence class satisfies IR (k, l)-anonymity or IR\((\alpha , \beta )\)-anonymity, we remove the equivalence class to \(D^{*}\). An equivalence class obtained by GeneIR contains more individuals, so the possibility that satisfies EIRl-diversity or EIR\((\alpha , \beta )\)-anonymity is higher.

When l increases but QI is fixed (i.e. \(|QI|=6\)), for an equivalence class satisfying IR (k, l)-anonymity, it is more difficult to satisfy EIRl-diversity, because EIRl-diversity requires that the number of different sensitive values of every reasoning set in the equivalence class is larger than or equal to l, so v increases, as shown in Fig. 2a. When \(\alpha \) increases but parameters QI and \(\beta \) are fixed (i.e. \(|QI|=6\) and \(\beta =0.4\)), for an equivalence class satisfying IR\((\alpha , \beta )\)-anonymity, the number of individuals decreases in the equivalence class. Therefore, it is more difficult to satisfy EIR\((\alpha , \beta )\)-anonymity, and v increases, as shown in Fig. 3a. When \(\beta \) increases but parameters QI and \(\alpha \) are fixed (i.e. \(|QI|=6\) and \(\alpha =0.6\)), the constraint is looser, for an equivalence class satisfying IR\((\alpha , \beta )\)-anonymity, it is easier to satisfy EIR\((\alpha , \beta )\)-anonymity. Consequently, v decreases, as shown in Fig. 3b.

From Figs. 2b and 3c, we observe that the change of QI size almost does not affect v for GeneIR\(\_kl\), DAnonyIR\(\_kl\), GeneIR\(\_\alpha \beta \) and DAnonyIR\(\_\alpha \beta \). When |QI| increases, and parameters l, \(\alpha \) and \(\beta \) are fixed (i.e. \(l=6\), \(\alpha =0.6\), and \(\beta =0.4\)), the number of equivalence classes is almost not changed. That is, the size of an equivalence class is almost not affected, so does the ratio of vulnerable equivalence classes.

In this subsection, we analyse the data quality from information loss and accuracy of query answering.

The runtimes exhibited by these algorithms based on the setting of values of different parameters l, \(\alpha \), \(\beta \), and |QI| are shown in Figs. 8 and 9. GeneIR can find quickly equivalence classes and check whether they satisfy IR (k, l)-anonymity or IR\((\alpha , \beta )\)-anonymity for each generalization operation. Apparently, its runtime is less than that of DAnonyIR. For GeneIR algorithm, it is possible that multiple equivalence classes are generated by scanning the dataset once or several times, while for DAnonyIR algorithm, an equivalence class is generated by scanning the dataset q times, where q is the number of individuals in the equivalence class. Therefore, the runtime of GeneIR is far less than that of DAnonyIR.

As shown in Fig. 8, the time of DAnonyIR\(\_kl\) and DAnonyIR\(\_El\) is close, because they both use the DAnonyIR algorithm, in which function SatPriIR is different, and they are SatPriIRInc\(\_kl\) and SatPriIRInc\(\_El\). They both incremental methods and consider only an individual how to influence privacy, so the time of DAnonyIR\(\_kl\) and DAnonyIR\(\_El\) is close. It is similar to show that the time of DAnonyIR\(\_\alpha \beta \) and DAnonyIR\(\_E\alpha \beta \) is close.

For DAnonyIR\(\_kl\) and DAnonyIR\(\_El\), when l or |QI| increases, the runtime is increased, as shown in Fig. 8, which is consistent with the time complexity analysis of DAnonyIR. For each equivalence class Q, the first individual is randomly selected, and we do not need to compute, so little time is spent. For every other individual in the equivalence class, we need scan D and \(D^{*}\) to get the individual or equivalence class with minimum distance to Q, respectively. In Fig. 8a, when l increases with fixed QI (i.e. \(|QI|=6\)), the number of equivalence classes is decreased. That is, the number of individuals is increased in each equivalence class, so the algorithm needs more calculations, and thus the runtime increases. When |QI| increases and l is fixed (i.e. \(l=6\)), more attributes are considered for distance calculation, and thus the algorithm needs more time, as shown in Fig. 8b. When l or |QI| increases, the runtime of GeneIR\(\_kl\) is increased, because GeneIR\(\_kl\) need more generalization operations.

For DAnonyIR\(\_\alpha \beta \) and DAnonyIR\(\_E\alpha \beta \), when \(\alpha \) or \(\beta \) increases, the runtime is decreased, as shown in Fig. 9a, b, which is consistent with the time complexity analysis of DAnonyIR. When QI and \(\beta \) (\(\alpha \)) are fixed (i.e. \(|QI|=6\) and \(\beta =0.4\,(\alpha =0.6)\)), as \(\alpha \) (\(\beta \)) increases, the number of records is decreased in each equivalence class. That is, the number of equivalence class is increased. So the algorithm needs less calculations, and thus the runtime is decreased. From Fig. 9c, we can see that the runtime increases with |QI|, which is consistent with the time complexity analysis of DAnonyIR. When |QI| increases but \(\alpha \) and \(\beta \) are fixed (i.e. \(\alpha =0.6\) and \(\beta =0.4\)), more attributes are considered in calculating distance, thus the algorithm needs more time. When \(\alpha \) (\(\beta \)) increases, the runtime of GeneIR\(\_\alpha \beta \) is decreased, because the constraint condition is loosed and thus GeneIR\(\_\alpha \beta \) needs less generalization operations. As |QI| increases, GeneIR\(\_\alpha \beta \) needs to generalize more attributes in order to obtain equivalence classes, so its runtime is increased.

Compared with DAnonyIR\(\_kl\) (DAnonyIR\(\_\alpha \beta \)), DAnonyIR\(\_El\) (DAnonyIR\(\_E\alpha \beta \)) needs more time to judge whether an equivalence class satisfies the EIRl-anonymity (EIR\((\alpha , \beta )\)-diversity). For Fig. 8 (Fig. 9), the maximum increment is only 28.5s (25.9s).

From these experimental results, we can see that the percentage of vulnerable equivalence classes is fairly high. That is, if we use IR (k, l)-anonymity and IR\((\alpha , \beta )\)-diversity, there are many equivalence classes that could cause privacy leakage. Although GeneIR\(\_kl\) and GeneIR\(\_\alpha \beta \) can achieve quickly anonymization, in terms of the data quality and ability of privacy preservation, they are worse than our DAnonyIR. Comparing with DAnonyIR\(\_kl\) and DAnonyIR\(\_\alpha \beta \), our DAnonyIR\(\_El\) and DAnonyIR\(\_E\alpha \beta \) have higher information loss and relative error ratio for query answering, and spend more time, but the increments in these aspects are small and acceptable, because DAnonyIR\(\_El\) and DAnonyIR\(\_E\alpha \beta \) supply stronger privacy preservation and the anonymized process is offline. Therefore, our enhanced privacy models and DAnonyIR algorithm are suitable for anonymizing just once over static datasets in an offline manner. However, when anonymization needs to take place quite frequently for data streams and execution time plays a major role, these approaches can be considered as inappropriate. The two previous privacy models do not reach a right privacy level while they suffer from great information loss by using GeneIR. On the other hand, the time exhibited by our DAnonyIR approach is not acceptable. Therefore, an appropriate approach for anonymizing data streams will be proposed in our further work.

Privacy preservation approaches for publishing static datasets contain these scenarios: single record and single sensitive attribute, single record and multiple sensitive attributes, and multiple records and single sensitive attribute, where single record and multiple records mean that an individual has only a record and multiple records in a data table, respectively.

In this subsection, we discuss the anonymization approaches for dynamic datasets and data streams, which almost all consider the scenario with single record and single sensitive attribute.

There are some studies on anonymizing set-valued data, trajectory data, and social network. Terrovitis et al. [39] presented \(k^{m}\)-anonymity for the set-valued or transaction data, which guarantees that an adversary with maximum knowledge of m items cannot distinguish each transaction from k transactions. They proposed two heuristic anonymization algorithms, which greedily identify itemsets that violate the anonymity requirement and choose generalization rules that fix the corresponding problems. (h, k, p)-coherence introduced by Xu et al. [40] confines an attacker with maximum knowledge of p items to identify each transaction from k transactions in which no more than \(h\%\) share a common private item. They gave an algorithm for achieving (h, k, p)-coherence by suppression while preserving as much information as possible. Cao et al. [41] proposed \(\rho \)-uncertainty privacy model, which does not allow an attacker knowing any subset of a transaction t to infer a sensitive item \(\alpha \in t\) with confidence higher than \(\rho \), and presented an algorithm by combining generalization and suppression to transform a data table and make it satisfy \(\rho \)-uncertainty. Chen et al. [42] studied the privacy problem of trajectory data. They proposed \((K, C)_{L}\)-privacy model, which requires any subsequence q of any adversary’s L-knowledge to be shared by either 0 or at least K records in a trajectory database and the confidence of inferring any sensitive value from q to be at most C, and showed that the proposed suppression method can significantly improve the data utility in anonymous trajectory data. Liu and Terzi [43] proposed k-degree anonymity for anonymizing social network, which requires that all vertices have at least \(k-1\) other vertices sharing the same degree, and gave an algorithm to ensure that all vertices satisfy k-degree anonymity by modifying the graph structure. Moreover, Casas-Roma et al. [8] devised an efficient algorithm for k-degree anonymity in large networks.

In this paper, we deal with static relational data with multiple records and single sensitive attribute. It is significant to study identity reservation for multiple records. Two privacy models EIRl-diversity and EIR\((\alpha , \beta )\)-anonymity are proposed to solve the disadvantage of IR (k, l)-anonymity and IR\((\alpha , \beta )\)-anonymity for identity reservation (i.e. they fail to prevent attribute disclosure). At present, many anonymization approaches use the generalization by predefined taxonomy tree, which restricts the generalized range and causes some unnecessary information loss. Therefore, Wang et al. [24] presented the set generalization and gave a clustering algorithm l-clustering to implement l-diversity. Inspired by the method, we present the heuristic greedy clustering algorithm DAnonyIR for achieving EIRl-diversity and EIR\((\alpha , \beta )\)-anonymity. Also, we can use DAnonyIR to anonymize database in order to make it satisfy IR (k, l)-anonymity and IR\((\alpha , \beta )\)-anonymity by calling different decision functions.

Our approach is different from l-clustering in the following two aspects. (1) Our approach considers the case of an individual with multiple records, so the definitions of some distances are different. We introduce our own concepts of the distance between two individuals, the distance between individual and equivalence class, and the distance between two equivalence classes by using different information metrics for numeric and categorical attributes. (2) Our approach is used to achieve EIRl-diversity, EIR\((\alpha , \beta )\)-anonymity, IR (k, l)-anonymity, and IR\((\alpha , \beta )\)-anonymity, while l-clustering is used for l-diversity. We need to set different decision functions for different privacy models. Experimental results have shown our DAnonyIR is superior to the existing GeneIR for multiple records with generalization by predefined taxonomy tree in terms of the data quality. Our approaches are only used to anonymize static relational datasets with multiple records and single sensitive attribute. In the next work, it will be interesting to extend our approaches to anonymize datasets with multiple sensitive attributes, dynamic datasets, data streams, and other data types.