# Anonymization of Quasi-Sensitive Attribute Sets in Aggregated Dataset

Authors: Yafan Li; Shuguang Yuan; Yulin Yuan; Chi Chen; Jing Yu
Journal: Security and Communication Networks
 (2022)

---

## Abstract

The widespread use of Internet of Things (IoT) and Data Fusion technologies make privacy protection an urgent problem to be solved. The aggregated datasets generated in these two scenarios face extra privacy disclosure. We define attribute sets with different sources in an aggregated dataset as quasi-sensitive attribute sets (QS sets). The QS set itself is not sensitive, but internal linking attacks may occur when two QS sets in an aggregated dataset are linked. In this paper, we propose a new privacy model, namely, the QS k-anonymity model. The QS k-anonymity model is effective in preventing internal linking attacks. We provide two algorithms for the QS k-anonymity model, the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm. We evaluate our algorithms on real datasets. The experimental results show that the Greedy QS k-anonymity algorithm has good data utility, the Efficient QS k-anonymity algorithm shows better efficiency, and both algorithms are well scalable.


---

## Body

## 1. Introduction

In recent years, with the emergence and development of technologies such as data mining and information sharing, more and more organizations are releasing large amounts of data for use, analysis, and research [1]. Thus, how to prevent the disclosure of sensitive information has become a major research hotspot. As an important part of data mining and information sharing, privacy-preserving data publishing (PPDP) [2] has attracted many scholars to conduct research on it since it was proposed. Researchers often refer to an organization that holds, anonymizes, and publishes data as a “data publisher,” and organizations that receive and use the data as “data analyzers.”Many studies have been proposed on anonymized data. Most of the current studies consider that the data publisher has a table in the form of explicit identifiers (EIs), quasi-identifiers (QIDs), sensitive attributes (SAs), and nonsensitive attributes (NSAs), where EIs are attributes that explicitly identify record owners (e.g. name and ID); QIDs are attributes that could be linked to external tables to identify the record owner [3]; SAs include sensitive information about individuals such as illness, salary, etc.; and NSAs contain all attributes except for the previous three types [4]. Most works assume that the four sets of attributes are disjoint. As the EIs are directly associated with the record owners with their sensitive information, they will be removed before the data are released for the privacy of the record owners. Even if the EIs are removed, the owner of the record can be re-identified by linking his or her QIDs to an external table. This attack is known as the linking attack [5]. To prevent linking attacks, the data publisher releases an anonymized table, including QIDs’, SAs, and NSAs, among which QIDs are the results of QIDs being anonymized.In the following paragraphs, we will give a brief introduction to k-anonymity and then describe the problems that will be discussed in this paper.K-anonymity is one of the most widely used anonymous methods of privacy protection [6]. The model requires that each record in the anonymized dataset is indistinguishable from at least k − 1 other records on the QIDs [7]. For example, Table 1 is an original table describing patient information, where Name is an EI; Age, Sex, and Zipcode are considered as QIDs; and Disease is considered as a SA. Table 2 shows the anonymized results obtained from Table 1 after 3-anonymity. Even if the data analyzers know Alex’s QID values, it is difficult to tell which of the first three records he is.Table 1
Patient table.
NameAgeSexZipcodeDiseaseAlex23Female17227FluBeth22Male17684HepatitisCarl25Male17657Broken armEllen49Female19336HangnailGlen50Male18814BronchitisHelen44Female18835FluTable 2
3-Anonymity.
AgeSexAddressDisease[22–25]Person[17227–17684]Flu[22–25]Person[17227–17684]Hepatitis[22–25]Person[17227–17684]Broken arm[44–50]Person[18814–19336]Hangnail[44–50]Person[18814–19336]Bronchitis[44–50]Person[18814–19336]FluHowever, multi-source data aggregation exists in IoT and Data Fusion scenarios. Considering the data aggregation process, the form of datasets in IoT and Data Fusion scenarios may be different from the form of datasets mentioned above. In this paper, we refer to the dataset formed by data aggregation in IoT and Data Fusion scenarios as anAggregatedDatasetAD. We discuss the simplest of these cases, where the aggregated dataset consists of data from two sources.We find that the two attribute sets that constitute an aggregated dataset are insensitive before aggregation, but there may exist linkability between these two attribute sets after aggregation, leading to attacks based on linkability. We refer to this attack as internal linking attacks, and such attribute sets as quasi-sensitive attribute sets (QS sets). We will describe the aggregated dataset and the internal linking attacks in detail in Section3.We classify the existing privacy-preserving methods based on k-anonymity into two categories. One is the conventional k-anonymity methods, including many classical anonymization methods and optimization algorithms [12–18]. They are more concerned with optimizing for the efficiency and utility of the algorithms. However, the impact of specific scenarios on the anonymity method is not taken into account. The other type of anonymization methods is scenario-based anonymization methods. Shi et al. [19] introduce “quasi-sensitive attributes” that can indirectly lead to the disclosure of sensitive information. Terrovitis et al. [20] argue that in some scenarios, some attributes are both QIDs and SAs. Sei et al. in [3] propose to treat QIDs as SAs and introduce the concept of “sensitive quasi-identifiers,” but this approach leads to reduced utility of the anonymized data. However, none of these methods takes into account the problem of internal linking attacks faced by aggregated datasets generated in IoT and Data Fusion scenarios.Our maincontributions are as follows:(1)
We identify a new privacy disclosure to aggregated datasets in IoT and Data Fusion scenarios. And, we propose internal linking attacks based on linkability faced by QS sets in aggregated datasets.(2)
We propose a new privacy model, namely,QSk-anonymity model, which can effectively defend against internal linking attacks faced by QS sets in aggregated datasets.(3)
We propose two simple and effective anonymization algorithms for the QS k-anonymity model.The Greedy QS k-anonymity algorithm: The Greedy QS k-anonymity algorithm uses a greedy heuristic to find and compute the Cartesian product of records, while achieving higher data utility by comparing information loss.The Efficient QS k-anonymity algorithm: The Efficient QS k-anonymity algorithm sorts the records in an aggregated dataset by the Hilbert transform, and then the algorithm traverses the dataset only once and calculates the Cartesian product of the records.(4)
We perform experiments on the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm in terms of data utility, efficiency, and scalability. Through a preliminary experimental evaluation, we demonstrate that our algorithms are practical and effective.Our main contributions are as follows: We discuss the methods related to k-anonymity model and the data utility metrics in Section2. We introduce the aggregated dataset and the internal linking attacks, while describing the motivation for our research in Section 3. Section 4 presents the novel privacy model and the design of our algorithms. Section 5 evaluates our approach based on experimental results. Finally, Section 6 concludes the paper and introduces the future work.


## 2. Related Works

### 2.1.k-Anonymity

Privacy is one of the most important issues in IoT and data fusion. In [21], a security and privacy algorithm for Unicode data is proposed in order to maintain privacy in the IoT ecosystem. In [22], the optimization of the generalization algorithm is achieved by generalizing quasi-identifiers with the same data type in the IoT data. In [23], Jiang, W. and Clifton, C. proposed a two-party framework that can generate k-anonymity data from two vertically split sources without disclosing the data from one site to the other. Or, in [24], k-anonymity for multi-source data is achieved by a semi-honest adversary model and a game-theoretic approach. Over the past decade, many approaches have been proposed to address privacy protection issues, and k-anonymity is one of the most prominent ways to protect privacy.Thek-anonymity model for privacy protection was first proposed by Samarati and Sweeney in 1998 [25], followed by Sweeney’s publication in 2002 [7] which brought k-anonymity to widespread attention in the academic community. Over the years, k-anonymity algorithms have been implemented through generalization, suppression, clustering, and microaggregation, with algorithms varying depending on the application domain (e.g. data mining, data publishing) or privacy and data utility needs [8].Among these algorithms, many methods achieve better anonymity through search strategies and optimization. For example, LeFevre et al. [12] achieved efficient full-domain k-anonymity algorithms through breadth-first search strategy and pruning strategy; they also proposed a multidimensional partitioning algorithm for k-anonymity in [13]. Liang and Samavi [14] proposed a k-anonymity optimization method. They proposed to express the k-anonymity optimization problem in a mathematical formulation and then found the equivalence class that minimized the information loss by an optimization solver. These methods do not rely on specific privacy-preserving scenarios and are generic anonymization algorithms that anonymize QIDs directly. Similar algorithms exist for [15–18].Some methods redefine the relationship between QIDs and SAs in the context of specific privacy protection scenarios. Shi et al. [19] introduced new attributes concept called “quasi-sensitive attributes,” which were not sensitive in themselves, but certain values or combinations of them might be associated with external knowledge, thus indirectly revealing sensitive information about individuals. Terrovitis et al. [20] proposed a k-anonymity algorithm based on a separation method that could be applied when some attributes were both QIDs and SAs. Sei et al. in [3] considered QIDs as SAs and proposed a new attribute named “sensitive quasi-identifiers,” and then they achieved the protection of private data by anonymization and reconstruction algorithms. However, this method is suitable for usage scenarios with high privacy requirements, and the utility of the data is reduced after anonymization.


### 2.2. Utility Metrics

Many researchers use certain well-designed metric functions to measure the quality of anonymized data. A metric function tends to examine the quality of anonymized data from a certain perspective. According to previous literature, the most common measures include the discernibility metric (DM) [9], which sums the squares of the cardinality of the equivalence classes; the classification metric (CM) [10], which requires a class label to classify the tuples; the normalized certainty penalty (NCP) [11], defined by the sum of the ranges of QIDs in each equivalence class; and the global certainty penalty (GCP) [26], which is a normalization of the sum of the NCP of all equivalence classes. However, according to observations, while the equivalence classes with few records are feasible, DM does not reflect the distribution of records in a dataset [27]. Furthermore, the CM is more suitable when the purpose of anonymized data is to train a classifier. Therefore, we chose NCP and GCP as the information loss metric functions for the privacy model in the later section, which can reflect the cardinality and spatial extent of each equivalence class. For a single numeric attribute Anum, the NCP of an equivalence class E is defined as follows:(1)NCPAnumE=EmaxAnum−minAnummaxU−minL,where the numerator represents the range of the attribute Anum in the equivalence class E, and maxU and minL are, respectively, the maximum and minimum allowed values for the attribute Anum. In addition, for a categorical attribute, which does not have natural order like numerical attributes, the NCP is defined through a taxonomy tree:(2)NCPAcatE=ElevelulevelAcat,where levelu denotes the height of the lowest parent node u of the value of the categorical attribute Acat in the equivalence class E and levelAcat denotes the height of the taxonomy tree of Acat. Thus, the NCP of an equivalence class E is defined as:(3)NCPE=∑i=1dNCPAi,where d denotes the number of attributes in the equivalence class E, and Ai represents the i-th attribute either numerical or categorical. NCP denotes the information loss of an equivalence class, while the information loss of the entire anonymized dataset is measured by GCP, which is defined as(4)GCPT=∑E∈TNCPEd·n,where n denotes the number of records in the original dataset. Obviously, a large GCP implies a high information loss of the anonymized dataset.


## 2.1.k-Anonymity

Privacy is one of the most important issues in IoT and data fusion. In [21], a security and privacy algorithm for Unicode data is proposed in order to maintain privacy in the IoT ecosystem. In [22], the optimization of the generalization algorithm is achieved by generalizing quasi-identifiers with the same data type in the IoT data. In [23], Jiang, W. and Clifton, C. proposed a two-party framework that can generate k-anonymity data from two vertically split sources without disclosing the data from one site to the other. Or, in [24], k-anonymity for multi-source data is achieved by a semi-honest adversary model and a game-theoretic approach. Over the past decade, many approaches have been proposed to address privacy protection issues, and k-anonymity is one of the most prominent ways to protect privacy.Thek-anonymity model for privacy protection was first proposed by Samarati and Sweeney in 1998 [25], followed by Sweeney’s publication in 2002 [7] which brought k-anonymity to widespread attention in the academic community. Over the years, k-anonymity algorithms have been implemented through generalization, suppression, clustering, and microaggregation, with algorithms varying depending on the application domain (e.g. data mining, data publishing) or privacy and data utility needs [8].Among these algorithms, many methods achieve better anonymity through search strategies and optimization. For example, LeFevre et al. [12] achieved efficient full-domain k-anonymity algorithms through breadth-first search strategy and pruning strategy; they also proposed a multidimensional partitioning algorithm for k-anonymity in [13]. Liang and Samavi [14] proposed a k-anonymity optimization method. They proposed to express the k-anonymity optimization problem in a mathematical formulation and then found the equivalence class that minimized the information loss by an optimization solver. These methods do not rely on specific privacy-preserving scenarios and are generic anonymization algorithms that anonymize QIDs directly. Similar algorithms exist for [15–18].Some methods redefine the relationship between QIDs and SAs in the context of specific privacy protection scenarios. Shi et al. [19] introduced new attributes concept called “quasi-sensitive attributes,” which were not sensitive in themselves, but certain values or combinations of them might be associated with external knowledge, thus indirectly revealing sensitive information about individuals. Terrovitis et al. [20] proposed a k-anonymity algorithm based on a separation method that could be applied when some attributes were both QIDs and SAs. Sei et al. in [3] considered QIDs as SAs and proposed a new attribute named “sensitive quasi-identifiers,” and then they achieved the protection of private data by anonymization and reconstruction algorithms. However, this method is suitable for usage scenarios with high privacy requirements, and the utility of the data is reduced after anonymization.


## 2.2. Utility Metrics

Many researchers use certain well-designed metric functions to measure the quality of anonymized data. A metric function tends to examine the quality of anonymized data from a certain perspective. According to previous literature, the most common measures include the discernibility metric (DM) [9], which sums the squares of the cardinality of the equivalence classes; the classification metric (CM) [10], which requires a class label to classify the tuples; the normalized certainty penalty (NCP) [11], defined by the sum of the ranges of QIDs in each equivalence class; and the global certainty penalty (GCP) [26], which is a normalization of the sum of the NCP of all equivalence classes. However, according to observations, while the equivalence classes with few records are feasible, DM does not reflect the distribution of records in a dataset [27]. Furthermore, the CM is more suitable when the purpose of anonymized data is to train a classifier. Therefore, we chose NCP and GCP as the information loss metric functions for the privacy model in the later section, which can reflect the cardinality and spatial extent of each equivalence class. For a single numeric attribute Anum, the NCP of an equivalence class E is defined as follows:(1)NCPAnumE=EmaxAnum−minAnummaxU−minL,where the numerator represents the range of the attribute Anum in the equivalence class E, and maxU and minL are, respectively, the maximum and minimum allowed values for the attribute Anum. In addition, for a categorical attribute, which does not have natural order like numerical attributes, the NCP is defined through a taxonomy tree:(2)NCPAcatE=ElevelulevelAcat,where levelu denotes the height of the lowest parent node u of the value of the categorical attribute Acat in the equivalence class E and levelAcat denotes the height of the taxonomy tree of Acat. Thus, the NCP of an equivalence class E is defined as:(3)NCPE=∑i=1dNCPAi,where d denotes the number of attributes in the equivalence class E, and Ai represents the i-th attribute either numerical or categorical. NCP denotes the information loss of an equivalence class, while the information loss of the entire anonymized dataset is measured by GCP, which is defined as(4)GCPT=∑E∈TNCPEd·n,where n denotes the number of records in the original dataset. Obviously, a large GCP implies a high information loss of the anonymized dataset.


## 3. Challenges and Motivations

Aggregated datasets formed in IoT and Data Fusion scenarios may lead to new privacy disclosures. We first describe the formation of aggregated datasets.IoT: The IoT refers to a network that connects any object to the Internet through information sensing devices (e.g. sensors, mobile phones, etc.) according to an agreed protocol for intelligent identification, monitoring, and management [28]. Typically, the data collected through different information sensing devices may be used directly or aggregated first and then used. The latter may result in the disclosure of sensitive information.Data Fusion: Data Fusion is the process of cognition, synthesis, and judgment of multiple data. The data involved in fusion are often characterized by multiple sources, heterogeneity, and incompleteness. Data Fusion combines relevant information from multiple related databases to achieve higher accuracy and more specific inferences than using individual data alone [29]. But similarly, the aggregation of data from multiple sources can easily lead to the disclosure of sensitive information.We discuss the simplest case that exists in the above two scenarios, where the data in a dataset are sourced from two different information sensing devices or related databases. We classify the formation and publication of the aggregated dataset into three processes. In the data collection stage, two sets of data are collected from two different information sensing devices or related databases and stored in Dataset1 and Dataset2, respectively. In the data aggregation stage, the data in Dataset1 and the data in Dataset2 are aggregated to form the aggregated dataset which is to be published. In the data publishing stage, the aggregated dataset can be published directly or anonymized. We also describe the formation and publication of the aggregated dataset in Figure1, and the anonymized dataset is indicated within the dotted line in the diagram.Figure 1
Formation and publication of aggregated dataset.We focus on the anonymization of aggregated datasets. In the next section, we will describe the new privacy disclosure faced by aggregated datasets.


### 3.1. Extra Privacy Disclosure

In addition to the three privacy disclosures of membership disclosure, attribute disclosure, and identity disclosure already considered [30], we find a new privacy disclosure in the aggregated dataset. Consider an example in Figure 2. Figure 2(a) shows a dataset containing EI, QID, and NSA. The data in this dataset released with EI removed are able to provide vehicle information without causing privacy disclosure. Similarly, the data in Figure 2(b) released with EI removed are able to be used to count vehicle traffic information without causing privacy disclosure. Due to the need of statistics or analysis, sometimes the datasets need to be fused before use. Figure 2(c) shows the aggregated dataset after fusion by Dataset1 and Dataset2. The dataset is usually published with the EI removed, but even if the data publisher removes the license plate number when publishing the aggregated dataset, the data analyzer can still associate the vehicle information (registration date and color) from Dataset1 with the location information (latitude, longitude, and time) from Dataset2 to obtain additional sensitive information, such as inferring the specific license plate number, and thus leading to the disclosure of sensitive information.Figure 2
Vehicle dataset. (a) Dataset1. (b) Dataset2. (c) Aggregated dataset. (d) Anonymized dataset (2 anonymity).
(a)(b)(c)(d)The dataset in Figure2(c) is considered as an aggregated dataset. The aggregated dataset may cause privacy disclosure when released. And, the aggregated dataset is formed by combining two datasets that do not result in privacy disclosure when released separately. For example, the attribute set containing Registration date and Color in Figure 2(c) is not sensitive itself and does not cause privacy disclosure, but linking to other attribute sets in aggregated dataset will cause privacy disclosure. We refer to this attribute set as a quasi-sensitive attribute set (QS set), and the attributes in it are called quasi-sensitive attribute (QS attribute). Therefore, we believe that a simple aggregated dataset may consist of EI, two QS sets (QS1 and QS2), and NSA.A privacy disclosure based on linkability [31] may exist in aggregated dataset. Linkability means that a data analyzer can successfully distinguish whether two IOI (items of interest) are linked and gain new knowledge by linking two IOI, even if he or she does not know the actual identity of the subject of the linkable IOI. The definition of linkability is based on Pfitzmann and Hansen’s definition of unlinkability [32]. Linkability may lead to identification and inference. When a data analyzer links two IOI, the actual identity of the subject of the linkable IOI may be inferred from their links, leading to identification. In contrast to identification, inference is not limited to linking data belonging to the same person. Even if a data analyzer does not obtain the true identity corresponding to two IOI, he or she may infer relationships from certain related attributes (people with overlapping tracks, people who buy the same items, etc.) and try to generalize them, which may lead to privacy disclosure. The example in Figure 2 reflects the identification and inference that result from linkability. The attacks based on linkability are called internal linking attacks. Figure 3 illustrates the risk of privacy disclosure in aggregated dataset. Data analyzers are able to gain access to certain sensitive information by mining the information generated by the linkability of QS1 and QS2 in an aggregated dataset, posing new privacy disclosure.Figure 3
Disclosure risk of aggregated datasets.


### 3.2. Motivation

Based on the description of the aggregated dataset and its privacy disclosure in the above section, in this section we describe the motivation for our research. We first describe the additional knowledge available to the data analyzer: We assume that the data analyzer only can obtain some or all of the attribute values inQS1 or QS2 of a certain record in the aggregated dataset.Through the analysis in the previous section, aggregated datasets can be subject to sensitive information disclosure if they are not processed by privacy-preserving technologies. As we mentioned above, k-anonymity is one of the most widely used privacy-preserving methods in PPDP, but there are some limitations to the application of k-anonymity in aggregated datasets.Limitation of use scenarios: As we said, the purpose of k-anonymity is to prevent privacy disclosure caused by linking attacks, so it handles QIDs that can be linked to external tables for privacy protection purposes. But for the aggregated datasets that may be generated in the IoT and Data Fusion scenarios, the data analyzer is concerned with the additional knowledge that can be gained through the linkage between the QS1 and QS2. However, k-anonymity does not take into account the potential for internal linking attacks on aggregated datasets generated in IoT and Data Fusion scenarios.Unable to defend against internal linking attacks: Internal linking attacks are caused by the linkage between QS1 and QS2 in the aggregated dataset. The attributes in the QS set are QIDs in a dataset before aggregation. If the aggregated dataset is anonymized using the k-anonymity method, all attributes in QS1 and QS2 will be anonymized to eliminate linkability between the QS sets in the aggregated dataset. However, we find that although k-anonymity hopes to achieve the goal of eliminating linkability by generalizing the values of attributes in QS1 and QS2, in some cases, it still cannot eliminate linkability between QS1 and QS2 and thus cannot resist internal linkage attacks. For example, Figure 2(d) shows the anonymized dataset after 2-anonymity, where the shaded parts represent two equivalence classes, respectively. A data analyzer who knows that the registration date is 2018 and the color is black, is able to easily combine the exact location and time information of the vehicle (since it is not anonymized) to infer sensitive information such as the license plate number of the vehicle. This is because k-anonymity may be achieved by generalizing only some of the QIDs.In this case, we should consider how to eliminate the linkability betweenQS1 and QS2 in the aggregated dataset. Our proposed approach uses the QS k-anonymity to prevent data analyzer from mapping attribute values from one QS set to the other. Thereby, internal linkage attacks are effectively prevented.In addition, the main relevant symbols and descriptions involved in this paper are shown in Table3.Table 3
Symbol and description.
SymbolDescriptionADAggregated datasetAD∗Anonymized datasetkAnonymity requirementrRecords in the datasetQSiQS sets in an aggregated dataset,i∈1,2q,q1,q2Number of attributes in the attribute setsQSi,jThej-th attribute in the QSiRi,jThe set of thej-th attribute values in the QSi of the recordsCpi,RCartesian product ofRi,jCpi,RThe size of the Cartesian productAk, Bk, Ck, DkAttribute valuesn, NNumber of records and records set inADγ, CClustersℜ, ClustersSet of clustersDx,yThe distance between recordsx and ybestrBest recordbestCBest clusterHilbertHilbert transform functionNCP, GCPInformation loss metric function


## 3.1. Extra Privacy Disclosure

In addition to the three privacy disclosures of membership disclosure, attribute disclosure, and identity disclosure already considered [30], we find a new privacy disclosure in the aggregated dataset. Consider an example in Figure 2. Figure 2(a) shows a dataset containing EI, QID, and NSA. The data in this dataset released with EI removed are able to provide vehicle information without causing privacy disclosure. Similarly, the data in Figure 2(b) released with EI removed are able to be used to count vehicle traffic information without causing privacy disclosure. Due to the need of statistics or analysis, sometimes the datasets need to be fused before use. Figure 2(c) shows the aggregated dataset after fusion by Dataset1 and Dataset2. The dataset is usually published with the EI removed, but even if the data publisher removes the license plate number when publishing the aggregated dataset, the data analyzer can still associate the vehicle information (registration date and color) from Dataset1 with the location information (latitude, longitude, and time) from Dataset2 to obtain additional sensitive information, such as inferring the specific license plate number, and thus leading to the disclosure of sensitive information.Figure 2
Vehicle dataset. (a) Dataset1. (b) Dataset2. (c) Aggregated dataset. (d) Anonymized dataset (2 anonymity).
(a)(b)(c)(d)The dataset in Figure2(c) is considered as an aggregated dataset. The aggregated dataset may cause privacy disclosure when released. And, the aggregated dataset is formed by combining two datasets that do not result in privacy disclosure when released separately. For example, the attribute set containing Registration date and Color in Figure 2(c) is not sensitive itself and does not cause privacy disclosure, but linking to other attribute sets in aggregated dataset will cause privacy disclosure. We refer to this attribute set as a quasi-sensitive attribute set (QS set), and the attributes in it are called quasi-sensitive attribute (QS attribute). Therefore, we believe that a simple aggregated dataset may consist of EI, two QS sets (QS1 and QS2), and NSA.A privacy disclosure based on linkability [31] may exist in aggregated dataset. Linkability means that a data analyzer can successfully distinguish whether two IOI (items of interest) are linked and gain new knowledge by linking two IOI, even if he or she does not know the actual identity of the subject of the linkable IOI. The definition of linkability is based on Pfitzmann and Hansen’s definition of unlinkability [32]. Linkability may lead to identification and inference. When a data analyzer links two IOI, the actual identity of the subject of the linkable IOI may be inferred from their links, leading to identification. In contrast to identification, inference is not limited to linking data belonging to the same person. Even if a data analyzer does not obtain the true identity corresponding to two IOI, he or she may infer relationships from certain related attributes (people with overlapping tracks, people who buy the same items, etc.) and try to generalize them, which may lead to privacy disclosure. The example in Figure 2 reflects the identification and inference that result from linkability. The attacks based on linkability are called internal linking attacks. Figure 3 illustrates the risk of privacy disclosure in aggregated dataset. Data analyzers are able to gain access to certain sensitive information by mining the information generated by the linkability of QS1 and QS2 in an aggregated dataset, posing new privacy disclosure.Figure 3
Disclosure risk of aggregated datasets.


## 3.2. Motivation

Based on the description of the aggregated dataset and its privacy disclosure in the above section, in this section we describe the motivation for our research. We first describe the additional knowledge available to the data analyzer: We assume that the data analyzer only can obtain some or all of the attribute values inQS1 or QS2 of a certain record in the aggregated dataset.Through the analysis in the previous section, aggregated datasets can be subject to sensitive information disclosure if they are not processed by privacy-preserving technologies. As we mentioned above, k-anonymity is one of the most widely used privacy-preserving methods in PPDP, but there are some limitations to the application of k-anonymity in aggregated datasets.Limitation of use scenarios: As we said, the purpose of k-anonymity is to prevent privacy disclosure caused by linking attacks, so it handles QIDs that can be linked to external tables for privacy protection purposes. But for the aggregated datasets that may be generated in the IoT and Data Fusion scenarios, the data analyzer is concerned with the additional knowledge that can be gained through the linkage between the QS1 and QS2. However, k-anonymity does not take into account the potential for internal linking attacks on aggregated datasets generated in IoT and Data Fusion scenarios.Unable to defend against internal linking attacks: Internal linking attacks are caused by the linkage between QS1 and QS2 in the aggregated dataset. The attributes in the QS set are QIDs in a dataset before aggregation. If the aggregated dataset is anonymized using the k-anonymity method, all attributes in QS1 and QS2 will be anonymized to eliminate linkability between the QS sets in the aggregated dataset. However, we find that although k-anonymity hopes to achieve the goal of eliminating linkability by generalizing the values of attributes in QS1 and QS2, in some cases, it still cannot eliminate linkability between QS1 and QS2 and thus cannot resist internal linkage attacks. For example, Figure 2(d) shows the anonymized dataset after 2-anonymity, where the shaded parts represent two equivalence classes, respectively. A data analyzer who knows that the registration date is 2018 and the color is black, is able to easily combine the exact location and time information of the vehicle (since it is not anonymized) to infer sensitive information such as the license plate number of the vehicle. This is because k-anonymity may be achieved by generalizing only some of the QIDs.In this case, we should consider how to eliminate the linkability betweenQS1 and QS2 in the aggregated dataset. Our proposed approach uses the QS k-anonymity to prevent data analyzer from mapping attribute values from one QS set to the other. Thereby, internal linkage attacks are effectively prevented.In addition, the main relevant symbols and descriptions involved in this paper are shown in Table3.Table 3
Symbol and description.
SymbolDescriptionADAggregated datasetAD∗Anonymized datasetkAnonymity requirementrRecords in the datasetQSiQS sets in an aggregated dataset,i∈1,2q,q1,q2Number of attributes in the attribute setsQSi,jThej-th attribute in the QSiRi,jThe set of thej-th attribute values in the QSi of the recordsCpi,RCartesian product ofRi,jCpi,RThe size of the Cartesian productAk, Bk, Ck, DkAttribute valuesn, NNumber of records and records set inADγ, CClustersℜ, ClustersSet of clustersDx,yThe distance between recordsx and ybestrBest recordbestCBest clusterHilbertHilbert transform functionNCP, GCPInformation loss metric function


## 4. Models and Algorithms

To simplify our problem, we assume that there are only EIs and two QS sets (QS1 and QS2) in an aggregated dataset. In fact, in addition to the EIs and QS sets, the aggregated dataset also may contain NSAs.LetQS be the set of attributes in the aggregated dataset and q be the number of these attributes (i.e. q=QS). Let QS1 represent a QS set in the aggregated dataset and q1 be the number of attributes in the QS set (i.e. q1=QS1). Let QS2 denote the other QS set in the aggregated dataset, and q2 represent the number of attributes in this QS set (i.e. q2=QS2). Then we can obtain the following relation that QS1∪QS2=QS, QS1∩QS2=∅ and q1+q2=q.Then, we define some basic concepts and present our privacy model.


### 4.1. Basic Definition

Definition 1.
(Quasi-sensitive attribute set). An attribute set consisting of one or more attributes is a quasi-sensitive attribute set (QS set) if it is not sensitive itself but can be linked with other attribute sets to generate sensitive information. The attributes in the QS set are called quasi-sensitive attributes (QS attributes).Definition 2.
(Attack model). For a recordr in an aggregated dataset, we assume that the data analyzer may only obtain some or all of its attribute values in QS1 or QS2.
Since the two datasets forming the aggregated dataset may have been partially published before aggregation, the data analyzer may obtain some or all of the attribute values inQS1 or QS2. But if the data analyzer obtains all the attribute values of a record at the same time, any anonymous method will be meaningless.Definition 3.
(Aggregated Dataset). An aggregated dataset (AD) may consist of explicit identifiers (EIs), two QS sets (QS1 and QS2), and nonsensitive attributes (NSAs).
Figure1① shows the data aggregation process. The QS1 and QS2 in the aggregated dataset are derived from the QIDs in Dataset 1 and Dataset 2, respectively. As we mentioned in the previous section, the attributes in Dataset 1 and Dataset 2 do not cause privacy disclosure when they are published with EI removed. However, when they are aggregated to form an aggregate dataset, the aggregated dataset may face privacy disclosure risk even if the EI is removed.Definition 4.
(Linkability). Linkability occurs whenQS1 and QS2 in a dataset AD are linked and some extra knowledge is generated. Based on the linkability, a data analyzer is able to gain extra knowledge by linking QS1 and QS2 in AD, which may contain some sensitive information with privacy implications. We refer to attacks based on linkability as internal linking attacks.Definition 5.
(Anonymized Dataset). An anonymized datasetAD∗ may consist of QS1’, QS2’ and nonsensitive attributes (NSAs).
Figure1② shows the formation process of the anonymized dataset. The data publisher removes the EI before publishing the aggregated dataset, while anonymizing the QS sets to break the linkability between QS1’ and QS2’. Then the anonymized dataset is released for use by the data analyzer, as shown in process ③.
Our goal is to prevent internal linking attacks that may result in the disclosure of sensitive information, while making an effort to improve the utility of the anonymized dataset. Under this attack, according to our assumptions above, the data analyzer does not have access to the value of the attributes in bothQS1 and QS2 for a record in AD at the same time. Next, we will construct our privacy model based on this attack hypothesis.


### 4.2. Proposed Privacy Models

According to the property of the aggregated dataset we described, the internal linkage attack can occur with higher probability only when the data analyzer obtains the accurate values of all the attributes in theQS1 and QS2. Therefore, it follows that we define a new privacy model QS k-anonymity to defend against internal linking attacks.Definition 6.
(Equivalence Class). We define a set of records that contain all the same QS attribute values as an equivalence class.
For example, there are 2 equivalence classes in Figure2(d), where the records 1 and 3 form one equivalence class, the records 2 and 4 form the other equivalence class.Definition 7.
(QS k-anonymity). The anonymized datasetAD∗ satisfies QS k-anonymity if and only if for each record in AD∗, the probability of mapping QS attribute values from QS1 to QS2 while obtaining the exact value of all QS attributes in QS2 is less than 1/k, and the probability of mapping QS attribute values from QS2 to QS1 while obtaining the exact value of all QS attributes in QS1 is also less than 1/k.Example 1.
We still use the vehicle dataset mentioned above as an example. Figure4 represents an example of the QS 4-anonymity of Figure 2(c). In Figure 4, bold face indicates the original values. Note that this is for clarity only. Our proposed approach is to represent the anonymized dataset with the combined values of the attributes in the QS sets in order to satisfy QS 4 anonymity. In Figure 4, if a data analyzer knows that the registration date and color are 2013 and white, respectively, there are four possible combinations of location and time that he or she can know, which are 110/30,13:00, 110/30,21:00, 118/22,13:00, and 118/22,21:00. The probability that the data analyzer obtains the exact combination of location and time values is 1/4, as is the probability of being able to correctly infer from the attribute values in the QS1 and QS2.
We provide two specific implementation algorithms for the QS k-anonymity model, the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm. The Greedy QS k-anonymity algorithm is able to provide good data utility through greedy search, and the Efficient QS k-anonymity algorithm provides efficient algorithmic efficiency through Hilbert transform. We will describe the specific implementation algorithms in detail in the next section.Figure 4
The QS 4-anonymity of Figure2(c).


### 4.3. Algorithms

First, we describe the core method of the proposed algorithms. Then, two specific implementation algorithms are proposed to achieve QS k-anonymity while improving the utility of anonymized data as much as possible.LetQSi,j denote the j-th attribute in the QSii∈1,2. For QSi,j in record r, the data publisher extracts x−1 records from records other than r and creates the set Ri,j containing the extracted records and the original record r (If the same attribute value exists in the records, the value is only recorded once in Ri,j). Then, the data publisher calculates the Cartesian products Cpi,R of Ri,1,…,Ri,qi, respectively, and inserts each element of the Ri,j into the anonymized dataset. The value of x is taken such that Cpi,R is greater than or equal to the anonymity requirement k.Example 2.
Figure5(a) shows the original dataset containing QS1 and QS2, where each QS set contains two attributes with attribute values denoted by Ak, Bk, Ck, Dk, respectively. We assume that the values in Ak, Bk, Ck, and Dk are not the same. Figure 5(b) shows the anonymized dataset, assuming that anonymity requirement k=4. We select record r1 as the original record and select record r5 among the remaining records, and then generate R1,1=A1,A5, R1,2=B1,B5, R2,1=C1,C5, and R2,2=D1,D5 according to the anonymization algorithm. Therefore, for the attributes in QS1 and QS2, their Cartesian products are Cp1,R=A1,B1,A1,B5,A5,B1,A5,B5 and Cp2,R=C1,D1,C1,D5,C5,D1,C5,D5, respectively, of size Cp1,R=Cp2,R=4. Even if the data analyzer knows all the attribute values in one QS set QS1 or QS2 in r1, the data analyzer cannot specify the exact combination of attribute values in the other QS set with a probability greater than 1/4. Therefore the probability of the data analyzer making an accurate inference based on the QS1 and QS2 is also less than 1/4. For example, as shown in Figure 5(b), assuming that the data analyzer has access to the attribute values C8 and D8 in QS2. The data analyzer does not know which of A3,B3,A3,B8,A8,B3,A8,B8 is the corresponding combination of attribute values in QS1.
Because the size of the Cartesian product can be very large, the data publisher may generate an anonymized record in the “aggregated expression.” Figure5(b) shows the anonymized record in an aggregated expression. And, the shaded part represents the equivalence class. Next, we will give two specific algorithms for the implementation of QS k-anonymity.Figure 5
QS 4-anonymity by our proposed method. (a) Original dataset. (b) QS 4 anonymity.
(a)(b)


#### 4.3.1. Greedy Algorithm

We use a greedy algorithm to implement QS k-anonymity. We consider QS k-anonymity as a clustering problem. Thus, QS k-anonymity can be defined as follows:Definition 8.
(QS k-Anonymity Clustering). The QS k-anonymity clustering problem finds a set of clusters from the givenn records according to the QS1 and QS2 such that the size of the Cartesian product of the attribute values in each QS set in each cluster is at least kk≤n, and all clusters are formed in such a way that the current information loss is minimized.
LetN represent the set of n records in AD. Let Cpi,a denote the Cartesian product of attribute values in QSi in cluster a. Then, QS k-anonymity clustering ℜ=γ1,…,γm is denoted as:(1)
∪a=1,…mγa=N;(2)
∀a,b∈1,…,ma≠b,γa∩γb=∅;(3)
∀i∈1,2,a∈1,…,m,Cpi,a≥k;(4)
∑ℓ=1,…,mγℓ·MAXa,b=1,…,|γℓ|Drℓ,a,rℓ,b is minimized.
Hereγ represents the size of cluster γ, rℓ,a denotes the a-th record in cluster γℓ, and Dx,y denotes the distance between records x and y.Definition 9.
(Distance between two records). Letm and n represent the number of numerical and categorical attributes in the dataset, and raA represent the value of attribute A of record ra. We define the distance between two records r1 and r2 in the dataset as(5)Dr1,r2=∑i=1,…,mr1Ai−r2AiDi+∑j=1,…,nlevelujlevelAjcat,where Di represents the value domain of the attribute Ai, leveluj represents the height of the lowest parent node uj of the categorical attribute Ajcat in r1 and r2, and levelAjcat represents the height of the taxonomy tree of the categorical attribute Ajcat.
Several studies [33, 34] have shown that the optimal k-anonymity problem is an NP-hard problem. Therefore, to create a locally optimal solution for QS k-anonymity that is as close to the global optimal solution as possible, we employ a greedy approach. Figure 6 shows the main implementation of the Greedy QS k-anonymity algorithm, which is able to show the implementation of our algorithm in a more comprehensive way. The input to the algorithm is the original aggregated dataset AD and the anonymity requirement k. First, record r is randomly selected from AD, and then entered in the loop until AD=∅. Finally, Clusters is output, which contains all clusters that satisfy the anonymity requirement k. The loop process achieves finding the optimal clusters that satisfy the anonymity requirement k. And the detailed loop process will be described in the next paragraph.
Algorithm 1: The Greedy QS k-anonymity Algorithm.
Input:AD, kOutput: a set of clusters in each of which the size of Cartesian product of attributes in QS1 and QS2 is greater than or equal to k(1)
Clusters=∅, C=∅(2)
ifCp1,AD<k‖Cp2,AD<kthen(3)
returnAD(4)
end if(5)
r is a randomly selected record in AD(6)
whileAD≠∅do(7)
r= the furthest record from r(8)
C=r(9)
AD=AD−r(10)
whileCp1,C<k‖Cp2,C<kdo(11)
bestr←best_recordAD,C(12)
C=C∪bestr(13)
AD=AD−bestr(14)
end while(15)
Clusters=Clusters∪C(16)
ifCp1,AD<k‖Cp2,AD<kthen(17)
whileAD≠∅do(18)
r  = a random tuple in AD(19)
AD=AD−r(20)
bestC=best_clusterClusters,r(21)
bestC=bestC∪r(22)
end while(23)
end if(24)
end while(25)
returnClusters
The main algorithm is shown in Algorithm 1. Given a datasetAD and anonymity requirement k, we first judge whether AD satisfies the condition for starting anonymity (lines 2–4). We select a record r at random, then select the record farthest from r to add to cluster C (lines 7–8) and remove that record from dataset AD (line 9). Then, we traverse the dataset AD and select the record bestr that makes the smallest information loss to add to cluster C. Repeat this process (lines 10–14) until the size of Cartesian product of attribute values in the QS1 and QS2 in cluster C is greater than or equal to k. Then, we add cluster C to cluster Clusters. Repeat lines 7–15 until the size of the Cartesian product of attribute values in QS1 or QS2 for the remaining records is less than k. Then, we iterate over these remaining records, inserting each record into the cluster with the least incremental information loss (lines 16–23). We use NCP to compare the information loss of each cluster. The time complexity of the greedy QSk-anonymity algorithm is On2.
Due to the higher time complexity of the greedyQSk-anonymity algorithm, in practice, we can partition the original dataset AD. Dividing AD into multiple small datasets to be anonymized separately can effectively improve the efficiency of the algorithm. And, for the choice of the partitioning method, in order to minimize the information loss caused by partitioning, the clustering method can be used for partitioning. Firstly, the similar records in the original dataset are clustered and divided into smaller datasets, which are then anonymized using the greedy QSk-anonymity algorithm.Figure 6
The main implementation process of the Greedy QS k-anonymity algorithm.


#### 4.3.2. Efficient Algorithm

The Greedy QS k-anonymity algorithm has a higher time complexity and lower algorithm efficiency because it needs to continuously traverse the whole dataset. In this section, we implement an anonymization algorithm based on Hilbert curve, which can improve the efficiency of the algorithm effectively and try to guarantee the utility of the anonymized dataset at the same time.The Hilbert curve [35] is a well-known spatial mapping technique, and it is a continuous fractal capable of mapping every region in space to an integer. If two points are close in a multidimensional space, they will also be close in the Hilbert transform with high probability [27]. For example, Figure 7(a) shows the transformation of data from 2-D to 1-D. The dataset is completely ordered with respect to the 1-D Hilbert values.Figure 7
Multi-dimensional to 1-D mappings. (a) Hilbert curve. (b) Categorical attribute mapping.
(a)(b)In order to perform data mapping, a number must be assigned to each attribute value so that the attribute value can be sorted. For numerical attributes, we can use the attribute values directly due to their natural orderliness. For categorical attributes, each attribute value is assigned to a different integer based on the taxonomy tree. Figure7(b) shows a taxonomy tree. We consider that the information loss between child nodes with the same parent is low. For example, the NCPIndia,Japan=1/2, and their common parent is Europe. The NCPCambodia,England=1, and their common parent is Country. Therefore, when sorting the categorical attributes, we believe that the distance between attributes with the same parent node should be closer, as shown in Figure 7(b).To efficiently implement the QS k-anonymity method, we propose our anonymization algorithm based on Hilbert curves. Figure8 shows the main implementation process of the Efficient QS k-anonymity algorithm. The algorithm takes the original aggregated dataset AD and the anonymity requirement k as input. First, a Hilbert transform is performed on AD to obtain the ordered dataset D. Then, the loop is entered until D=∅. The final output Clusters, contains all clusters that satisfy the anonymity requirement k. The purpose of the loop process is to find the optimal clusters that satisfy the anonymity requirement k. We will describe the detailed loop process in the following:Figure 8
The main implementation process of the Efficient QS k-anonymity algorithm.Algorithm 2: The Efficient QS k-anonymity Algorithm.
Input:AD, kOutput: a set of clusters in each of which the size of Cartesian product of attributes in QS1 and QS2 is greater than or equal to k(1)
Clusters=C=∅(2)
ifCp1,AD<k‖Cp2,AD<kthen(3)
returnAD(4)
end if(5)
D←HilbertAD(6)
whileD≠∅do(7)
ifCp1,D≥k&Cp2,D≥kthen(8)
i=0(9)
whileCp1,C<k‖Cp2,C<kdo(10)
C=C∪ri, i=i+1(11)
end while(12)
D=D−C(13)
Clusters=Clusters∪C(14)
C=∅(15)
else(16)
whileD≠∅do(17)
r = a random tuple in D(18)
D=D−r(19)
bestC=best_clusterClusters,r(20)
bestC=bestC∪r(21)
end while(22)
end if(23)
end while(24)
returnClustersThe main algorithm is shown in Algorithm 2. We first judge whetherAD satisfies the condition for starting anonymity (lines 2–4). And then we implement the mapping from d-D to 1-D by Hilbert transform. As we mentioned before, two close points in the multidimensional space are also close in the Hilbert transform with high probability. Therefore, by the Hilbert transform process, we achieve the sorting of the records with d-D attributes in the dataset AD (line 5). Then, we iterate through the sorted dataset D and take the record ri from dataset D to cluster C (line 10) until the size of the Cartesian product of the attribute values in the QS1 and QS1 in cluster C is greater than or equal to k (lines 9–11). Then, we add cluster C to the cluster Clusters. Repeat lines 7–14 until the size of the Cartesian product of the attribute values in the QS1 or QS2 of the remaining records in D is less than k. Then, we iterate through these remaining records, inserting each record into the cluster with the least incremental information loss (lines 16–21). We still use NCP tso compare the information loss of each equivalence class. Finally, when representing the anonymized dataset, we sort the values of the attributes in each equivalence class in the Clusters in dictionary order, as shown in Figure 4.The time complexity of the Hilbert transform isOd for each record, so the algorithm is very efficient. Since the input dataset D is ordered after the Hilbert transform, our method only needs to scan the data once. Therefore, the I/O cost is linear.


## 4.1. Basic Definition

Definition 1.
(Quasi-sensitive attribute set). An attribute set consisting of one or more attributes is a quasi-sensitive attribute set (QS set) if it is not sensitive itself but can be linked with other attribute sets to generate sensitive information. The attributes in the QS set are called quasi-sensitive attributes (QS attributes).Definition 2.
(Attack model). For a recordr in an aggregated dataset, we assume that the data analyzer may only obtain some or all of its attribute values in QS1 or QS2.
Since the two datasets forming the aggregated dataset may have been partially published before aggregation, the data analyzer may obtain some or all of the attribute values inQS1 or QS2. But if the data analyzer obtains all the attribute values of a record at the same time, any anonymous method will be meaningless.Definition 3.
(Aggregated Dataset). An aggregated dataset (AD) may consist of explicit identifiers (EIs), two QS sets (QS1 and QS2), and nonsensitive attributes (NSAs).
Figure1① shows the data aggregation process. The QS1 and QS2 in the aggregated dataset are derived from the QIDs in Dataset 1 and Dataset 2, respectively. As we mentioned in the previous section, the attributes in Dataset 1 and Dataset 2 do not cause privacy disclosure when they are published with EI removed. However, when they are aggregated to form an aggregate dataset, the aggregated dataset may face privacy disclosure risk even if the EI is removed.Definition 4.
(Linkability). Linkability occurs whenQS1 and QS2 in a dataset AD are linked and some extra knowledge is generated. Based on the linkability, a data analyzer is able to gain extra knowledge by linking QS1 and QS2 in AD, which may contain some sensitive information with privacy implications. We refer to attacks based on linkability as internal linking attacks.Definition 5.
(Anonymized Dataset). An anonymized datasetAD∗ may consist of QS1’, QS2’ and nonsensitive attributes (NSAs).
Figure1② shows the formation process of the anonymized dataset. The data publisher removes the EI before publishing the aggregated dataset, while anonymizing the QS sets to break the linkability between QS1’ and QS2’. Then the anonymized dataset is released for use by the data analyzer, as shown in process ③.
Our goal is to prevent internal linking attacks that may result in the disclosure of sensitive information, while making an effort to improve the utility of the anonymized dataset. Under this attack, according to our assumptions above, the data analyzer does not have access to the value of the attributes in bothQS1 and QS2 for a record in AD at the same time. Next, we will construct our privacy model based on this attack hypothesis.


## 4.2. Proposed Privacy Models

According to the property of the aggregated dataset we described, the internal linkage attack can occur with higher probability only when the data analyzer obtains the accurate values of all the attributes in theQS1 and QS2. Therefore, it follows that we define a new privacy model QS k-anonymity to defend against internal linking attacks.Definition 6.
(Equivalence Class). We define a set of records that contain all the same QS attribute values as an equivalence class.
For example, there are 2 equivalence classes in Figure2(d), where the records 1 and 3 form one equivalence class, the records 2 and 4 form the other equivalence class.Definition 7.
(QS k-anonymity). The anonymized datasetAD∗ satisfies QS k-anonymity if and only if for each record in AD∗, the probability of mapping QS attribute values from QS1 to QS2 while obtaining the exact value of all QS attributes in QS2 is less than 1/k, and the probability of mapping QS attribute values from QS2 to QS1 while obtaining the exact value of all QS attributes in QS1 is also less than 1/k.Example 1.
We still use the vehicle dataset mentioned above as an example. Figure4 represents an example of the QS 4-anonymity of Figure 2(c). In Figure 4, bold face indicates the original values. Note that this is for clarity only. Our proposed approach is to represent the anonymized dataset with the combined values of the attributes in the QS sets in order to satisfy QS 4 anonymity. In Figure 4, if a data analyzer knows that the registration date and color are 2013 and white, respectively, there are four possible combinations of location and time that he or she can know, which are 110/30,13:00, 110/30,21:00, 118/22,13:00, and 118/22,21:00. The probability that the data analyzer obtains the exact combination of location and time values is 1/4, as is the probability of being able to correctly infer from the attribute values in the QS1 and QS2.
We provide two specific implementation algorithms for the QS k-anonymity model, the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm. The Greedy QS k-anonymity algorithm is able to provide good data utility through greedy search, and the Efficient QS k-anonymity algorithm provides efficient algorithmic efficiency through Hilbert transform. We will describe the specific implementation algorithms in detail in the next section.Figure 4
The QS 4-anonymity of Figure2(c).


## 4.3. Algorithms

First, we describe the core method of the proposed algorithms. Then, two specific implementation algorithms are proposed to achieve QS k-anonymity while improving the utility of anonymized data as much as possible.LetQSi,j denote the j-th attribute in the QSii∈1,2. For QSi,j in record r, the data publisher extracts x−1 records from records other than r and creates the set Ri,j containing the extracted records and the original record r (If the same attribute value exists in the records, the value is only recorded once in Ri,j). Then, the data publisher calculates the Cartesian products Cpi,R of Ri,1,…,Ri,qi, respectively, and inserts each element of the Ri,j into the anonymized dataset. The value of x is taken such that Cpi,R is greater than or equal to the anonymity requirement k.Example 2.
Figure5(a) shows the original dataset containing QS1 and QS2, where each QS set contains two attributes with attribute values denoted by Ak, Bk, Ck, Dk, respectively. We assume that the values in Ak, Bk, Ck, and Dk are not the same. Figure 5(b) shows the anonymized dataset, assuming that anonymity requirement k=4. We select record r1 as the original record and select record r5 among the remaining records, and then generate R1,1=A1,A5, R1,2=B1,B5, R2,1=C1,C5, and R2,2=D1,D5 according to the anonymization algorithm. Therefore, for the attributes in QS1 and QS2, their Cartesian products are Cp1,R=A1,B1,A1,B5,A5,B1,A5,B5 and Cp2,R=C1,D1,C1,D5,C5,D1,C5,D5, respectively, of size Cp1,R=Cp2,R=4. Even if the data analyzer knows all the attribute values in one QS set QS1 or QS2 in r1, the data analyzer cannot specify the exact combination of attribute values in the other QS set with a probability greater than 1/4. Therefore the probability of the data analyzer making an accurate inference based on the QS1 and QS2 is also less than 1/4. For example, as shown in Figure 5(b), assuming that the data analyzer has access to the attribute values C8 and D8 in QS2. The data analyzer does not know which of A3,B3,A3,B8,A8,B3,A8,B8 is the corresponding combination of attribute values in QS1.
Because the size of the Cartesian product can be very large, the data publisher may generate an anonymized record in the “aggregated expression.” Figure5(b) shows the anonymized record in an aggregated expression. And, the shaded part represents the equivalence class. Next, we will give two specific algorithms for the implementation of QS k-anonymity.Figure 5
QS 4-anonymity by our proposed method. (a) Original dataset. (b) QS 4 anonymity.
(a)(b)


### 4.3.1. Greedy Algorithm

We use a greedy algorithm to implement QS k-anonymity. We consider QS k-anonymity as a clustering problem. Thus, QS k-anonymity can be defined as follows:Definition 8.
(QS k-Anonymity Clustering). The QS k-anonymity clustering problem finds a set of clusters from the givenn records according to the QS1 and QS2 such that the size of the Cartesian product of the attribute values in each QS set in each cluster is at least kk≤n, and all clusters are formed in such a way that the current information loss is minimized.
LetN represent the set of n records in AD. Let Cpi,a denote the Cartesian product of attribute values in QSi in cluster a. Then, QS k-anonymity clustering ℜ=γ1,…,γm is denoted as:(1)
∪a=1,…mγa=N;(2)
∀a,b∈1,…,ma≠b,γa∩γb=∅;(3)
∀i∈1,2,a∈1,…,m,Cpi,a≥k;(4)
∑ℓ=1,…,mγℓ·MAXa,b=1,…,|γℓ|Drℓ,a,rℓ,b is minimized.
Hereγ represents the size of cluster γ, rℓ,a denotes the a-th record in cluster γℓ, and Dx,y denotes the distance between records x and y.Definition 9.
(Distance between two records). Letm and n represent the number of numerical and categorical attributes in the dataset, and raA represent the value of attribute A of record ra. We define the distance between two records r1 and r2 in the dataset as(5)Dr1,r2=∑i=1,…,mr1Ai−r2AiDi+∑j=1,…,nlevelujlevelAjcat,where Di represents the value domain of the attribute Ai, leveluj represents the height of the lowest parent node uj of the categorical attribute Ajcat in r1 and r2, and levelAjcat represents the height of the taxonomy tree of the categorical attribute Ajcat.
Several studies [33, 34] have shown that the optimal k-anonymity problem is an NP-hard problem. Therefore, to create a locally optimal solution for QS k-anonymity that is as close to the global optimal solution as possible, we employ a greedy approach. Figure 6 shows the main implementation of the Greedy QS k-anonymity algorithm, which is able to show the implementation of our algorithm in a more comprehensive way. The input to the algorithm is the original aggregated dataset AD and the anonymity requirement k. First, record r is randomly selected from AD, and then entered in the loop until AD=∅. Finally, Clusters is output, which contains all clusters that satisfy the anonymity requirement k. The loop process achieves finding the optimal clusters that satisfy the anonymity requirement k. And the detailed loop process will be described in the next paragraph.
Algorithm 1: The Greedy QS k-anonymity Algorithm.
Input:AD, kOutput: a set of clusters in each of which the size of Cartesian product of attributes in QS1 and QS2 is greater than or equal to k(1)
Clusters=∅, C=∅(2)
ifCp1,AD<k‖Cp2,AD<kthen(3)
returnAD(4)
end if(5)
r is a randomly selected record in AD(6)
whileAD≠∅do(7)
r= the furthest record from r(8)
C=r(9)
AD=AD−r(10)
whileCp1,C<k‖Cp2,C<kdo(11)
bestr←best_recordAD,C(12)
C=C∪bestr(13)
AD=AD−bestr(14)
end while(15)
Clusters=Clusters∪C(16)
ifCp1,AD<k‖Cp2,AD<kthen(17)
whileAD≠∅do(18)
r  = a random tuple in AD(19)
AD=AD−r(20)
bestC=best_clusterClusters,r(21)
bestC=bestC∪r(22)
end while(23)
end if(24)
end while(25)
returnClusters
The main algorithm is shown in Algorithm 1. Given a datasetAD and anonymity requirement k, we first judge whether AD satisfies the condition for starting anonymity (lines 2–4). We select a record r at random, then select the record farthest from r to add to cluster C (lines 7–8) and remove that record from dataset AD (line 9). Then, we traverse the dataset AD and select the record bestr that makes the smallest information loss to add to cluster C. Repeat this process (lines 10–14) until the size of Cartesian product of attribute values in the QS1 and QS2 in cluster C is greater than or equal to k. Then, we add cluster C to cluster Clusters. Repeat lines 7–15 until the size of the Cartesian product of attribute values in QS1 or QS2 for the remaining records is less than k. Then, we iterate over these remaining records, inserting each record into the cluster with the least incremental information loss (lines 16–23). We use NCP to compare the information loss of each cluster. The time complexity of the greedy QSk-anonymity algorithm is On2.
Due to the higher time complexity of the greedyQSk-anonymity algorithm, in practice, we can partition the original dataset AD. Dividing AD into multiple small datasets to be anonymized separately can effectively improve the efficiency of the algorithm. And, for the choice of the partitioning method, in order to minimize the information loss caused by partitioning, the clustering method can be used for partitioning. Firstly, the similar records in the original dataset are clustered and divided into smaller datasets, which are then anonymized using the greedy QSk-anonymity algorithm.Figure 6
The main implementation process of the Greedy QS k-anonymity algorithm.


### 4.3.2. Efficient Algorithm

The Greedy QS k-anonymity algorithm has a higher time complexity and lower algorithm efficiency because it needs to continuously traverse the whole dataset. In this section, we implement an anonymization algorithm based on Hilbert curve, which can improve the efficiency of the algorithm effectively and try to guarantee the utility of the anonymized dataset at the same time.The Hilbert curve [35] is a well-known spatial mapping technique, and it is a continuous fractal capable of mapping every region in space to an integer. If two points are close in a multidimensional space, they will also be close in the Hilbert transform with high probability [27]. For example, Figure 7(a) shows the transformation of data from 2-D to 1-D. The dataset is completely ordered with respect to the 1-D Hilbert values.Figure 7
Multi-dimensional to 1-D mappings. (a) Hilbert curve. (b) Categorical attribute mapping.
(a)(b)In order to perform data mapping, a number must be assigned to each attribute value so that the attribute value can be sorted. For numerical attributes, we can use the attribute values directly due to their natural orderliness. For categorical attributes, each attribute value is assigned to a different integer based on the taxonomy tree. Figure7(b) shows a taxonomy tree. We consider that the information loss between child nodes with the same parent is low. For example, the NCPIndia,Japan=1/2, and their common parent is Europe. The NCPCambodia,England=1, and their common parent is Country. Therefore, when sorting the categorical attributes, we believe that the distance between attributes with the same parent node should be closer, as shown in Figure 7(b).To efficiently implement the QS k-anonymity method, we propose our anonymization algorithm based on Hilbert curves. Figure8 shows the main implementation process of the Efficient QS k-anonymity algorithm. The algorithm takes the original aggregated dataset AD and the anonymity requirement k as input. First, a Hilbert transform is performed on AD to obtain the ordered dataset D. Then, the loop is entered until D=∅. The final output Clusters, contains all clusters that satisfy the anonymity requirement k. The purpose of the loop process is to find the optimal clusters that satisfy the anonymity requirement k. We will describe the detailed loop process in the following:Figure 8
The main implementation process of the Efficient QS k-anonymity algorithm.Algorithm 2: The Efficient QS k-anonymity Algorithm.
Input:AD, kOutput: a set of clusters in each of which the size of Cartesian product of attributes in QS1 and QS2 is greater than or equal to k(1)
Clusters=C=∅(2)
ifCp1,AD<k‖Cp2,AD<kthen(3)
returnAD(4)
end if(5)
D←HilbertAD(6)
whileD≠∅do(7)
ifCp1,D≥k&Cp2,D≥kthen(8)
i=0(9)
whileCp1,C<k‖Cp2,C<kdo(10)
C=C∪ri, i=i+1(11)
end while(12)
D=D−C(13)
Clusters=Clusters∪C(14)
C=∅(15)
else(16)
whileD≠∅do(17)
r = a random tuple in D(18)
D=D−r(19)
bestC=best_clusterClusters,r(20)
bestC=bestC∪r(21)
end while(22)
end if(23)
end while(24)
returnClustersThe main algorithm is shown in Algorithm 2. We first judge whetherAD satisfies the condition for starting anonymity (lines 2–4). And then we implement the mapping from d-D to 1-D by Hilbert transform. As we mentioned before, two close points in the multidimensional space are also close in the Hilbert transform with high probability. Therefore, by the Hilbert transform process, we achieve the sorting of the records with d-D attributes in the dataset AD (line 5). Then, we iterate through the sorted dataset D and take the record ri from dataset D to cluster C (line 10) until the size of the Cartesian product of the attribute values in the QS1 and QS1 in cluster C is greater than or equal to k (lines 9–11). Then, we add cluster C to the cluster Clusters. Repeat lines 7–14 until the size of the Cartesian product of the attribute values in the QS1 or QS2 of the remaining records in D is less than k. Then, we iterate through these remaining records, inserting each record into the cluster with the least incremental information loss (lines 16–21). We still use NCP tso compare the information loss of each equivalence class. Finally, when representing the anonymized dataset, we sort the values of the attributes in each equivalence class in the Clusters in dictionary order, as shown in Figure 4.The time complexity of the Hilbert transform isOd for each record, so the algorithm is very efficient. Since the input dataset D is ordered after the Hilbert transform, our method only needs to scan the data once. Therefore, the I/O cost is linear.


## 4.3.1. Greedy Algorithm

We use a greedy algorithm to implement QS k-anonymity. We consider QS k-anonymity as a clustering problem. Thus, QS k-anonymity can be defined as follows:Definition 8.
(QS k-Anonymity Clustering). The QS k-anonymity clustering problem finds a set of clusters from the givenn records according to the QS1 and QS2 such that the size of the Cartesian product of the attribute values in each QS set in each cluster is at least kk≤n, and all clusters are formed in such a way that the current information loss is minimized.
LetN represent the set of n records in AD. Let Cpi,a denote the Cartesian product of attribute values in QSi in cluster a. Then, QS k-anonymity clustering ℜ=γ1,…,γm is denoted as:(1)
∪a=1,…mγa=N;(2)
∀a,b∈1,…,ma≠b,γa∩γb=∅;(3)
∀i∈1,2,a∈1,…,m,Cpi,a≥k;(4)
∑ℓ=1,…,mγℓ·MAXa,b=1,…,|γℓ|Drℓ,a,rℓ,b is minimized.
Hereγ represents the size of cluster γ, rℓ,a denotes the a-th record in cluster γℓ, and Dx,y denotes the distance between records x and y.Definition 9.
(Distance between two records). Letm and n represent the number of numerical and categorical attributes in the dataset, and raA represent the value of attribute A of record ra. We define the distance between two records r1 and r2 in the dataset as(5)Dr1,r2=∑i=1,…,mr1Ai−r2AiDi+∑j=1,…,nlevelujlevelAjcat,where Di represents the value domain of the attribute Ai, leveluj represents the height of the lowest parent node uj of the categorical attribute Ajcat in r1 and r2, and levelAjcat represents the height of the taxonomy tree of the categorical attribute Ajcat.
Several studies [33, 34] have shown that the optimal k-anonymity problem is an NP-hard problem. Therefore, to create a locally optimal solution for QS k-anonymity that is as close to the global optimal solution as possible, we employ a greedy approach. Figure 6 shows the main implementation of the Greedy QS k-anonymity algorithm, which is able to show the implementation of our algorithm in a more comprehensive way. The input to the algorithm is the original aggregated dataset AD and the anonymity requirement k. First, record r is randomly selected from AD, and then entered in the loop until AD=∅. Finally, Clusters is output, which contains all clusters that satisfy the anonymity requirement k. The loop process achieves finding the optimal clusters that satisfy the anonymity requirement k. And the detailed loop process will be described in the next paragraph.
Algorithm 1: The Greedy QS k-anonymity Algorithm.
Input:AD, kOutput: a set of clusters in each of which the size of Cartesian product of attributes in QS1 and QS2 is greater than or equal to k(1)
Clusters=∅, C=∅(2)
ifCp1,AD<k‖Cp2,AD<kthen(3)
returnAD(4)
end if(5)
r is a randomly selected record in AD(6)
whileAD≠∅do(7)
r= the furthest record from r(8)
C=r(9)
AD=AD−r(10)
whileCp1,C<k‖Cp2,C<kdo(11)
bestr←best_recordAD,C(12)
C=C∪bestr(13)
AD=AD−bestr(14)
end while(15)
Clusters=Clusters∪C(16)
ifCp1,AD<k‖Cp2,AD<kthen(17)
whileAD≠∅do(18)
r  = a random tuple in AD(19)
AD=AD−r(20)
bestC=best_clusterClusters,r(21)
bestC=bestC∪r(22)
end while(23)
end if(24)
end while(25)
returnClusters
The main algorithm is shown in Algorithm 1. Given a datasetAD and anonymity requirement k, we first judge whether AD satisfies the condition for starting anonymity (lines 2–4). We select a record r at random, then select the record farthest from r to add to cluster C (lines 7–8) and remove that record from dataset AD (line 9). Then, we traverse the dataset AD and select the record bestr that makes the smallest information loss to add to cluster C. Repeat this process (lines 10–14) until the size of Cartesian product of attribute values in the QS1 and QS2 in cluster C is greater than or equal to k. Then, we add cluster C to cluster Clusters. Repeat lines 7–15 until the size of the Cartesian product of attribute values in QS1 or QS2 for the remaining records is less than k. Then, we iterate over these remaining records, inserting each record into the cluster with the least incremental information loss (lines 16–23). We use NCP to compare the information loss of each cluster. The time complexity of the greedy QSk-anonymity algorithm is On2.
Due to the higher time complexity of the greedyQSk-anonymity algorithm, in practice, we can partition the original dataset AD. Dividing AD into multiple small datasets to be anonymized separately can effectively improve the efficiency of the algorithm. And, for the choice of the partitioning method, in order to minimize the information loss caused by partitioning, the clustering method can be used for partitioning. Firstly, the similar records in the original dataset are clustered and divided into smaller datasets, which are then anonymized using the greedy QSk-anonymity algorithm.Figure 6
The main implementation process of the Greedy QS k-anonymity algorithm.


## 4.3.2. Efficient Algorithm

The Greedy QS k-anonymity algorithm has a higher time complexity and lower algorithm efficiency because it needs to continuously traverse the whole dataset. In this section, we implement an anonymization algorithm based on Hilbert curve, which can improve the efficiency of the algorithm effectively and try to guarantee the utility of the anonymized dataset at the same time.The Hilbert curve [35] is a well-known spatial mapping technique, and it is a continuous fractal capable of mapping every region in space to an integer. If two points are close in a multidimensional space, they will also be close in the Hilbert transform with high probability [27]. For example, Figure 7(a) shows the transformation of data from 2-D to 1-D. The dataset is completely ordered with respect to the 1-D Hilbert values.Figure 7
Multi-dimensional to 1-D mappings. (a) Hilbert curve. (b) Categorical attribute mapping.
(a)(b)In order to perform data mapping, a number must be assigned to each attribute value so that the attribute value can be sorted. For numerical attributes, we can use the attribute values directly due to their natural orderliness. For categorical attributes, each attribute value is assigned to a different integer based on the taxonomy tree. Figure7(b) shows a taxonomy tree. We consider that the information loss between child nodes with the same parent is low. For example, the NCPIndia,Japan=1/2, and their common parent is Europe. The NCPCambodia,England=1, and their common parent is Country. Therefore, when sorting the categorical attributes, we believe that the distance between attributes with the same parent node should be closer, as shown in Figure 7(b).To efficiently implement the QS k-anonymity method, we propose our anonymization algorithm based on Hilbert curves. Figure8 shows the main implementation process of the Efficient QS k-anonymity algorithm. The algorithm takes the original aggregated dataset AD and the anonymity requirement k as input. First, a Hilbert transform is performed on AD to obtain the ordered dataset D. Then, the loop is entered until D=∅. The final output Clusters, contains all clusters that satisfy the anonymity requirement k. The purpose of the loop process is to find the optimal clusters that satisfy the anonymity requirement k. We will describe the detailed loop process in the following:Figure 8
The main implementation process of the Efficient QS k-anonymity algorithm.Algorithm 2: The Efficient QS k-anonymity Algorithm.
Input:AD, kOutput: a set of clusters in each of which the size of Cartesian product of attributes in QS1 and QS2 is greater than or equal to k(1)
Clusters=C=∅(2)
ifCp1,AD<k‖Cp2,AD<kthen(3)
returnAD(4)
end if(5)
D←HilbertAD(6)
whileD≠∅do(7)
ifCp1,D≥k&Cp2,D≥kthen(8)
i=0(9)
whileCp1,C<k‖Cp2,C<kdo(10)
C=C∪ri, i=i+1(11)
end while(12)
D=D−C(13)
Clusters=Clusters∪C(14)
C=∅(15)
else(16)
whileD≠∅do(17)
r = a random tuple in D(18)
D=D−r(19)
bestC=best_clusterClusters,r(20)
bestC=bestC∪r(21)
end while(22)
end if(23)
end while(24)
returnClustersThe main algorithm is shown in Algorithm 2. We first judge whetherAD satisfies the condition for starting anonymity (lines 2–4). And then we implement the mapping from d-D to 1-D by Hilbert transform. As we mentioned before, two close points in the multidimensional space are also close in the Hilbert transform with high probability. Therefore, by the Hilbert transform process, we achieve the sorting of the records with d-D attributes in the dataset AD (line 5). Then, we iterate through the sorted dataset D and take the record ri from dataset D to cluster C (line 10) until the size of the Cartesian product of the attribute values in the QS1 and QS1 in cluster C is greater than or equal to k (lines 9–11). Then, we add cluster C to the cluster Clusters. Repeat lines 7–14 until the size of the Cartesian product of the attribute values in the QS1 or QS2 of the remaining records in D is less than k. Then, we iterate through these remaining records, inserting each record into the cluster with the least incremental information loss (lines 16–21). We still use NCP tso compare the information loss of each equivalence class. Finally, when representing the anonymized dataset, we sort the values of the attributes in each equivalence class in the Clusters in dictionary order, as shown in Figure 4.The time complexity of the Hilbert transform isOd for each record, so the algorithm is very efficient. Since the input dataset D is ordered after the Hilbert transform, our method only needs to scan the data once. Therefore, the I/O cost is linear.


## 5. Experimental Evaluation

In this section, we present the experimental evaluation of our practical algorithms in terms of data utility, efficiency, and scalability. In Section5.1, we describe the dataset used for the experiments and the experimental environment setup. In Section 5.2, we provide the experimental results of our algorithms in terms of data utility and efficiency. In Section 5.3, we perform experiments on the scalability of our algorithms.


### 5.1. Experimental Setup

#### 5.1.1. Dataset

We evaluated our proposed two algorithms in the publicly available dataset. For our experiments, we used the Adult dataset from the UC Irvine Machine Learning Repository [36]. The dataset includes 32561 records and 14 attributes. And 8 attributes in the Adult dataset were used in our experiment.For QS k-anonymity, we considered {age, workclass, occupation, race} as attribute setQS1 and {education-num, marital-status, gender, native-country} as attribute set QS2. We considered age and education-num as numerical attributes, while the other six attributes were considered as categorical attributes.


#### 5.1.2. Experimental Environment

The experiments were conducted on a machine equipped with a 2.30 GHz Intel(R) Core(TM) i7 processor with 16 GB RAM. The operating system on the machine was Microsoft Windows 10, and the implementation was built and run on IntelliJ IDEA 2021.2. The programming language we used is Java and the JDK version is 8.


### 5.2. Data Utility and Efficiency

In this section, we report the experimental results of the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm in terms of data utility and execution efficiency.Figure9(a) shows the variation of information loss with increasing k values for the two algorithms (The Greedy QS k-anonymity and The Efficient QS k-anonymity). We use the GCP to measure the information loss of the anonymized dataset. The higher the GCP, the greater the information loss. As shown in the figure, for all k values, the Greedy QS k-anonymity algorithm results in the lowest GCP. Meanwhile, the information loss of the two algorithms increases with the increase of the k values. The reason that the Greedy QS k-anonymity algorithm outperforms the Efficient QS k-anonymity algorithm in terms of data utility is that the Greedy QS k-anonymity algorithm traverses the dataset to find the optimal record based on the NCP.Figure 9
Variation of information loss and execution time with the value ofk. (a) Information loss. (b) Execution time.
(a)(b)We also measured the execution time of the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm under differentk values. The results are shown in Figure 9(b). The execution time of the Greedy QS k-anonymity algorithm is higher than that of the Efficient QS k-anonymity algorithm, but we believe that the QS k-anonymity algorithm is still acceptable in practice because the anonymization process is usually considered as an offline process. Moreover, we can see that the execution time of the Efficient QS k-anonymity algorithm gradually decreases as the value of k increases. This is because the increase in the value of k leads to a decrease in the number of equivalence classes, and thus saves the time to compute the information loss of the equivalent classes. For the Greedy QS k-anonymity algorithm, the increase in the value of k leads to the increase in the size of the equivalence class, thus increasing the time to calculate the information loss of the equivalence class in each round.


### 5.3. Scalability

In this section, we examine the scalability of the algorithms. We discuss the data utility and execution time of the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm under different number of attributes and different number of records.We first measure the impact of changes in the attribute setsQS1 and QS2 on the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm in terms of data utility and execution time when k = 4. Figure 10 shows the attributes in QS1 and QS2 at the time of measurement. Figure 11 shows the results of our experiments. Again, the Greedy QS k-anonymity algorithm consistently outperforms the Efficient QS k-anonymity algorithm in terms of data utility, but the Efficient QS k-anonymity algorithm has the advantage of short execution time. We also find that for both the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm, the information loss in the anonymized dataset tends to decrease with increasing attribute values. This is because the k value constrains the size of the Cartesian product of the attributes in QS1 and QS2. Thus, for QS k-anonymity, the more attributes in QS1 and QS2, the easier it is to satisfy the constraint k on the size of the Cartesian product when anonymized, and the smaller the average equivalence class size formed, the lower the information loss after anonymization. Furthermore, in Figure 11(b), we can see that for the Greedy QS k-anonymity algorithm, the execution time of the algorithm tends to decrease with the increase in the number of attributes. This is because the increase in attributes enables the clusters to satisfy the anonymity requirement k faster and thus reduces the time to compute the information lost per round. For the Efficient QS k-anonymity algorithm, the execution time of the algorithm increases with the number of attributes. This is because the increase in the number of attributes increases the time for the algorithm to compute the information loss.Figure 10
The attributes inQS1 and QS2.Figure 11
Variation of information loss and execution time with the number of attributes. (a) Information loss (k = 4). (b) Execution time (k = 4).
(a)(b)In addition, different attributes in the QS sets have different effects on the data utility and execution time of the algorithms. Therefore, for the experiments on the number of attributes, we obtain only a trend, but there may be fluctuations in the data utility and execution time of the algorithms in the change of the number of attributes.Figure12 shows the data utility and execution time behaviors of the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm for various dataset cardinalities (for k = 4). For this experiment, we use the subsets of Adult dataset with different sizes. As shown in the figure, the information loss of both algorithms increases almost linearly with the size of the datasets. The greedy QS k-anonymity algorithm introduces the lowest information loss for any size of dataset. Although the Greedy QS k-anonymity algorithm is slower than the Efficient QS k-anonymity algorithm, we believe that the time overhead is still acceptable in most cases, considering that it provides better data utility.Figure 12
Variation of information loss and execution time with the number of records. (a) Information loss (k = 4). (b) Execution time (k = 4).
(a)(b)


## 5.1. Experimental Setup

### 5.1.1. Dataset

We evaluated our proposed two algorithms in the publicly available dataset. For our experiments, we used the Adult dataset from the UC Irvine Machine Learning Repository [36]. The dataset includes 32561 records and 14 attributes. And 8 attributes in the Adult dataset were used in our experiment.For QS k-anonymity, we considered {age, workclass, occupation, race} as attribute setQS1 and {education-num, marital-status, gender, native-country} as attribute set QS2. We considered age and education-num as numerical attributes, while the other six attributes were considered as categorical attributes.


### 5.1.2. Experimental Environment

The experiments were conducted on a machine equipped with a 2.30 GHz Intel(R) Core(TM) i7 processor with 16 GB RAM. The operating system on the machine was Microsoft Windows 10, and the implementation was built and run on IntelliJ IDEA 2021.2. The programming language we used is Java and the JDK version is 8.


## 5.1.1. Dataset

We evaluated our proposed two algorithms in the publicly available dataset. For our experiments, we used the Adult dataset from the UC Irvine Machine Learning Repository [36]. The dataset includes 32561 records and 14 attributes. And 8 attributes in the Adult dataset were used in our experiment.For QS k-anonymity, we considered {age, workclass, occupation, race} as attribute setQS1 and {education-num, marital-status, gender, native-country} as attribute set QS2. We considered age and education-num as numerical attributes, while the other six attributes were considered as categorical attributes.


## 5.1.2. Experimental Environment

The experiments were conducted on a machine equipped with a 2.30 GHz Intel(R) Core(TM) i7 processor with 16 GB RAM. The operating system on the machine was Microsoft Windows 10, and the implementation was built and run on IntelliJ IDEA 2021.2. The programming language we used is Java and the JDK version is 8.


## 5.2. Data Utility and Efficiency

In this section, we report the experimental results of the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm in terms of data utility and execution efficiency.Figure9(a) shows the variation of information loss with increasing k values for the two algorithms (The Greedy QS k-anonymity and The Efficient QS k-anonymity). We use the GCP to measure the information loss of the anonymized dataset. The higher the GCP, the greater the information loss. As shown in the figure, for all k values, the Greedy QS k-anonymity algorithm results in the lowest GCP. Meanwhile, the information loss of the two algorithms increases with the increase of the k values. The reason that the Greedy QS k-anonymity algorithm outperforms the Efficient QS k-anonymity algorithm in terms of data utility is that the Greedy QS k-anonymity algorithm traverses the dataset to find the optimal record based on the NCP.Figure 9
Variation of information loss and execution time with the value ofk. (a) Information loss. (b) Execution time.
(a)(b)We also measured the execution time of the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm under differentk values. The results are shown in Figure 9(b). The execution time of the Greedy QS k-anonymity algorithm is higher than that of the Efficient QS k-anonymity algorithm, but we believe that the QS k-anonymity algorithm is still acceptable in practice because the anonymization process is usually considered as an offline process. Moreover, we can see that the execution time of the Efficient QS k-anonymity algorithm gradually decreases as the value of k increases. This is because the increase in the value of k leads to a decrease in the number of equivalence classes, and thus saves the time to compute the information loss of the equivalent classes. For the Greedy QS k-anonymity algorithm, the increase in the value of k leads to the increase in the size of the equivalence class, thus increasing the time to calculate the information loss of the equivalence class in each round.


## 5.3. Scalability

In this section, we examine the scalability of the algorithms. We discuss the data utility and execution time of the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm under different number of attributes and different number of records.We first measure the impact of changes in the attribute setsQS1 and QS2 on the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm in terms of data utility and execution time when k = 4. Figure 10 shows the attributes in QS1 and QS2 at the time of measurement. Figure 11 shows the results of our experiments. Again, the Greedy QS k-anonymity algorithm consistently outperforms the Efficient QS k-anonymity algorithm in terms of data utility, but the Efficient QS k-anonymity algorithm has the advantage of short execution time. We also find that for both the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm, the information loss in the anonymized dataset tends to decrease with increasing attribute values. This is because the k value constrains the size of the Cartesian product of the attributes in QS1 and QS2. Thus, for QS k-anonymity, the more attributes in QS1 and QS2, the easier it is to satisfy the constraint k on the size of the Cartesian product when anonymized, and the smaller the average equivalence class size formed, the lower the information loss after anonymization. Furthermore, in Figure 11(b), we can see that for the Greedy QS k-anonymity algorithm, the execution time of the algorithm tends to decrease with the increase in the number of attributes. This is because the increase in attributes enables the clusters to satisfy the anonymity requirement k faster and thus reduces the time to compute the information lost per round. For the Efficient QS k-anonymity algorithm, the execution time of the algorithm increases with the number of attributes. This is because the increase in the number of attributes increases the time for the algorithm to compute the information loss.Figure 10
The attributes inQS1 and QS2.Figure 11
Variation of information loss and execution time with the number of attributes. (a) Information loss (k = 4). (b) Execution time (k = 4).
(a)(b)In addition, different attributes in the QS sets have different effects on the data utility and execution time of the algorithms. Therefore, for the experiments on the number of attributes, we obtain only a trend, but there may be fluctuations in the data utility and execution time of the algorithms in the change of the number of attributes.Figure12 shows the data utility and execution time behaviors of the Greedy QS k-anonymity algorithm and the Efficient QS k-anonymity algorithm for various dataset cardinalities (for k = 4). For this experiment, we use the subsets of Adult dataset with different sizes. As shown in the figure, the information loss of both algorithms increases almost linearly with the size of the datasets. The greedy QS k-anonymity algorithm introduces the lowest information loss for any size of dataset. Although the Greedy QS k-anonymity algorithm is slower than the Efficient QS k-anonymity algorithm, we believe that the time overhead is still acceptable in most cases, considering that it provides better data utility.Figure 12
Variation of information loss and execution time with the number of records. (a) Information loss (k = 4). (b) Execution time (k = 4).
(a)(b)


## 6. Conclusion and Future Work

Thek-anonymity model has been extensively studied for privacy protection. The aggregated datasets formed in IoT and Data Fusion scenarios are exposed to a new attack, the internal linking attack. And, the k-anonymity model cannot defend against the internal linking attacks. We assume that there are two QS sets in an aggregated dataset which do not cause privacy disclosure when published separately but may cause privacy problems when linked to each other. We propose a new privacy model, namely, QS k-anonymity, and anonymization algorithms that can handle QS sets to prevent internal linking attacks. Through experiments on the real dataset, we demonstrate that our proposed approach is effective.Our study focuses on aggregated datasets in the IoT and Data Fusion scenarios. In the current existing work, we assume that the data in the aggregated dataset comes from two information sensing devices or related databases, respectively. And, we discuss the internal linking attacks faced by the aggregated dataset under this assumption. However, in many situations, the data in an aggregated dataset may be from multiple sources due to the complexity of the application scenario. Our proposed QS k-anonymity model and implementation algorithms are able to prevent internal linking attacks on the aggregated dataset, which is formed by data from two sources. However, the aggregated dataset from multiple sources has not been discussed in this paper yet.In our future work, we plan to analyze the internal linking attacks on the aggregated dataset, which consists of data from multiple sources, while optimizing our QS k-anonymity model and algorithms to prevent internal linking attacks on aggregated datasets from multiple sources.



---

*Source: 9721817-2022-04-29.xml*