KR102848186B1 - System for Anonymizing Transaction Data with Set Values and Method thereof - Google Patents

Abstract

The present invention relates to a system and method for anonymizing transaction data having a set value, and is a new technique that can guarantee strong privacy while minimizing information loss for transaction data having a set value. It basically adopts a top-down partitioning algorithm like the existing k-anonymity to optimize safety and CPU execution time, and improves the shortcomings of the existing k-anonymity by additionally reallocating transactions through a bottom-up tree search process after the partitioning process. Although the time for the bottom-up tree search is added compared to the existing k-anonymity, this time is a kind of compensation work that optimizes information loss for the remaining transactions after the final transaction is anonymized, and is insignificant compared to the overall time required compared to the existing k-anonymity algorithm. In terms of information loss, it aims to provide much better performance than any technique proposed to date, such as the existing k-anonymity or the HgHs technique.

Description

System for anonymizing transaction data with set values and method thereof

The present invention relates to a system and method for anonymizing transaction data in which each attribute value in a relational database has a set value.

Typically, structured data is organized as a dataset in a relational database. For example, each record contains individual data (often referred to as "microdata"), and each column contains attributes such as the individual's name, age, and address.

Semi-structured data exists in a variety of contexts, such as purchasing various products at a supermarket or describing a patient's various symptoms at a hospital. This type of data is generally referred to as semi-structured data, and data containing aggregate values is specifically called transaction data.

Meanwhile, many researchers have proposed solutions to the problem of anonymization in semi-structured transaction data.

For example, in the study of prior literature 1, 'M. Terrovitis, N. Mamoulis, and P. Kalnis, Privacy Preserving Anonymization of Set-valued Data. In: VLDB 2008' and prior literature 2, 'M. Terrovitis and D. Tsitsigkos, Amnesia, Institute for the Management of Information Systems, https://amnesia.openaire.eu/ (consulted in September 2020)', Manolis Terrovitis and Nikos Mamoulis observed that directly disclosing a database D can reveal the identity of a person involved in a specific transaction if the attacker has partial knowledge of a subset of the items purchased by that person.

Therefore, as a solution to this, we proposed k ^m -anonymity (aka 'global generalization'). That is, assuming that the attacker's maximum knowledge is at most m items of a particular transaction (out of a set of transaction records), we want to prevent him from distinguishing the transaction from the set of k published transactions in database D. Similarly, for any set of items less than m, there must be at least k transactions in the published database D' that contain this set. This definition of anonymity emphasizes that for set-valued data, an attacker can identify individuals using some of the sensitive set values that he knows in advance.

However, for example, in some cases, it may be impossible to predetermine a bound on the number of items an attacker can learn in a transaction. In this case, choosing a secure value for m itself is impossible. Another example occurs when some items in a set can be used to exclude certain transactions from being linked to individuals. For example, an attacker might know that only people over 65 typically purchase some items, and only people in a specific geographic area purchase other items. In such cases, k- ^m -anonymity cannot provide protection against the attack.

Meanwhile, in the papers of previous literature 4, 'Y. Xu, BCM Fung, K. Wang, AW-C. Fu, and J. Pei. Publishing sensitive transactions for itemset utility. In ICDM (2008)' and previous literature 5, 'Y. Xu, K. Wang, AWC Fu, and P.S. Yu. Anonymizing transaction databases for publication. In KDD (2008)', Y. Xu et al. proposed (h, k, p)-consistency, a more sophisticated privacy criterion for anonymizing set-valued data. (h, k, p)-consistency ensures that for any combination of p insensitive items, there are at least k transactions in the database containing these items, and at most h% of the transactions contain some sensitive items. That is, it provides flexibility in anonymization by modeling the attacker's prior knowledge using the parameter p. k ^m -anonymity can be viewed as a special case where h = 100% and p = m. However, this method suffers from high information loss due to the use of suppression techniques for relatively small distributions of all items to enhance security. We will provide examples of such cases in the next chapter. Furthermore, this model assumes the existence of quasi-identifiers and classifications for sensitive information, making it inapplicable to problems where this is not the case.

In the previous literature 6, 'Yeye He' and 'Jeffrey F. Naughton' proposed the k-anonymity technique, also called the 'local generalization' technique, to solve the problems suggested in the above studies in the paper 'Y. He and J. Naughton, Anonymization of Set-valued Data via Top-down Local Generalization. In: VLDB 2009 (2009)'.

This technique is defined as satisfying k-anonymity if each transaction is identical to at least k-1 other transactions. First, k ^m -anonymity protects an individual's privacy only when the attacker knows m or fewer items, whereas k-anonymity does not require a limit on the number of items that the attacker can know when there is no parameter m. In general, the smaller m of k ^m -anonymity, the weaker the privacy provided by k ^m -anonymity. However, k-anonymity guarantees stronger privacy than k ^m -anonymity. In addition, while k ^m -anonymity is a bottom-up approach, k-anonymity has the advantage of shorter CPU execution time than existing techniques because it uses a greedy partitioning (tree splitting) algorithm based on a top-down approach.

Here, the k-anonymity algorithm is basically used to determine which transactions should be grouped in the generalized hierarchical tree by using a top-down greedy partitioning algorithm.

Figure 1 illustrates a two-part anonymization (local generalization) and generalization tree hierarchy in the original database D. It begins by generalizing all transactions to the root level of the hierarchy. This creates anonymized partitions as long as there are at least k transactions in the database, since all transactions, after generalizing to the root, share the same representation ("ALL"). From this starting point, the initial partition is passed to the Anonymize routine, which subpartitions the current partition and recursively calls Anonymize on all resulting subpartitions. The partitioning process terminates when no further partitioning is possible.

The above k-anonymity basically adopts a top-down partitioning approach, so it has a disadvantage of significant information loss because it applies the same generalization only within the partitioned domain in the generalization tree structure of each transaction item, and especially for items with unique values. Junqiang Liu and Ke Wang pointed out the above shortcomings of k-anonymity in their paper 'J. Liu and K. Wang, Anonymizing Transaction Data by Integrating Suppression and Generalization, In: Zaki, M.J., Yu, J. X., Ravindran, B., and Pudi, V. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2010. Lecture Notes in Computer Science, vol 6118. Springer (2010)' and proposed a new technique, the HgHs (Heuristic generalization with Heuristic suppression) algorithm.

The above HgHs algorithm technique integrates the global generalization technique [1,2] and the total item deletion technique to strengthen k ^m -anonymity. The detailed algorithm consists of two steps: generalization cut and cut deletion scenario (SS). [Step 1] is an outer loop called 'full subtree generalization', which searches for the optimal cut with the least information loss in the generalization hierarchy tree. [Step 2] is an inner loop called total item suppression, which evaluates whether the k ^m -anonymity is satisfied in the subtree within the cut and deletes items that do not satisfy it.

The above HgHs technique finds the heuristic optimal cutting (tree splitting) point in the generalized tree structure and applies generalization and deletion techniques. Compared to the k-anonymity technique, it has less information loss, but has the disadvantage of very long CPU execution time.

1. M. Terrovitis, N. Mamoulis, and P. Kalnis, Privacy Preserving Anonymization of Set-valued Data. In: VLDB 2008 (2008) 2. M. Terrovitis and D. Tsitsigkos, Amnesia, Institute for the Management of Information Systems, https://amnesia.openaire.eu/ (consulted in September 2020) 3. M. Cunha, R. Mendes, and J. P. Vilela, A survey of privacy-preserving mechanisms for heterogeneous data types, Computer Science Review vol 41 (2021) 4. Y. Xu, B. C. M. Fung, K. Wang, A. W.-C. Fu, and J. Pei. Publishing sensitive transactions for itemset utility. In ICDM (2008) 5. Y. Xu, K. Wang, A. W. C. Fu, and P. S. Yu. Anonymizing transaction databases for publication. In K.D.D. (2008) 6. Y. He and J. Naughton, Anonymization of Set-valued Data via Top-down Local Generalization. In: VLDB 2009 (2009) 7. R. Agrawal and R. Srikant. Privacy-preserving data mining. In Proc. of ACM SIGMOD (2000) 8. J. Liu and K. Wang, Anonymizing Transaction Data by Integrating Suppression and Generalization, In: Zaki, M.J., Yu, J. X., Ravindran, B., and Pudi, V. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2010. Lecture Notes in Computer Science, vol 6118. Springer (2010)

Accordingly, the present invention aims to provide a novel anonymization system and method for transaction data having aggregate values, which can guarantee strong privacy while minimizing information loss, in order to improve the problems of the prior art. In addition, the present invention basically adopts a top-down partitioning algorithm, similar to the existing k-anonymity, to optimize security and CPU execution time, while simultaneously reallocating transactions through an additional bottom-up tree search process after the partitioning process, thereby improving the shortcomings of the existing k-anonymity. Although the time for the bottom-up tree search is additional compared to the existing k-anonymity, this time is a kind of compensation process that optimizes information loss for the remaining transactions after the final transaction is anonymized, and is insignificant compared to the overall time required compared to the existing k-anonymity algorithm. In terms of information loss, the present invention aims to provide a system and method for anonymizing transaction data having aggregate values, which exhibits far superior performance compared to any other technique proposed to date, such as the existing k-anonymity or the HgHs technique.

In order to achieve the object of the present invention, a system for anonymizing transaction data having a set value is provided, which collects transaction data containing personal information from a relational database and performs data anonymization through a central processing unit (CPU), and is characterized by comprising: an anonymization manager for assigning anonymization jobs to the collected transaction data; a central processing unit (CPU) for performing data anonymization for jobs assigned from the anonymization manager through an anonymization job scheduler; and a storage for storing and preserving anonymous transaction data for which anonymization has been completed in the central processing unit and providing the same to an authorized user terminal.

Here, the anonymization processing of the central processing unit is performed based on a top-down partitioning algorithm, and is characterized by reallocating transactions through a top-down tree search process thereafter.

A method for anonymizing transaction data having a set value to achieve the object of the present invention is characterized in that the method comprises: a first step in which transaction data including personal information is collected from a relational database through an anonymization manager, and a central processing unit (CPU) performs data anonymization, wherein the anonymization manager performs an anonymization job assignment for the transaction data collected from the relational database to a job scheduler; a second step in which the central processing unit performs anonymization for the job assigned to the job scheduler; and a third step in which the central processing unit stores anonymous transaction data, on which anonymization has been completed, in storage.

Here, the second process is characterized by comprising: a first step of constructing a generalized tree for transaction items to be processed and performing a partitioning process; a second step of sequentially selecting a first partition among the partitions divided in the first step; a third step of expanding the selected partition to lower nodes of the tree; a fourth step of assigning each transaction to the expanded partition; a fifth step of performing a balance partition (Balance_patrition()) routine to check whether the assigned transactions satisfy a pre-given k-anonymity privacy model; and a sixth step of performing a final partition (Final_partition()) routine to terminate anonymization processing after performing reprocessing on the remaining transactions in order to minimize information loss if the K-anonymity privacy model is satisfied as a result of the review in the fifth step.

In addition, the fifth step further includes a step of checking whether there is another partition to which the transaction (t) can be assigned within the partitioned partition if K-anonymity is not satisfied, and assigning the transaction (tj) to the partition until K-anonymity is satisfied; and a step of checking whether there is another partition to which the transaction (t) can be assigned within the partitioned partition if K-anonymity is not satisfied, and assigning the transaction (tj) to a waiting queue (WaitForQ, hereinafter referred to as 'WFQ') if there is no other partition to which the transaction (t) can be assigned within the partitioned partition; and if the K-anonymity check is satisfied, the first to fourth steps are repeatedly performed until there are no more nodes to be expanded, and if there are no more nodes to be expanded, a final queue routine (FinalQ_data()) is performed to store a final generalized candidate transaction and its partition in a separate final queue (hereinafter referred to as 'FinalQ').

In addition, the sixth step is characterized by performing a process of checking whether there is a partition that satisfies K-anonymity by matching the partitions stored in FinalQ with the partitions stored in WFQ while searching each partition stored in WFQ in a bottom-up manner, and if there is a partition that satisfies it, the transaction and partition are moved from WFQ to FinalQ.

The anonymization system and method for transaction data having a set value according to the present invention basically adopt a top-down partitioning algorithm similar to the conventional k-anonymity (local generalization) to optimize safety and central processing unit (CPU) execution time, while improving the shortcomings of the conventional k-anonymity by additionally reallocating transactions through a bottom-up tree search process after the partitioning process.

In addition, since the conventional k-anonymity basically adopts a top-down partitioning approach, it has a disadvantage of significant information loss because it applies the same generalization only within a partitioned domain and especially to items with unique values in the generalization tree structure of each transaction item. However, the present invention improves the disadvantages of the existing k-anonymity by reassigning transactions through an additional bottom-up tree search process after the top-down partitioning process.

Furthermore, although the time for the upward tree search is increased compared to the conventional k-anonymity, this time is a kind of compensation operation that optimizes the information loss for the remaining transactions after the final transaction is anonymized. Compared to the existing k-anonymity algorithm, the total required time is minimal, and it is expected to show a much higher processing time than the conventional HgHs algorithm technique. In contrast, in terms of information loss, it shows much better performance than any other technique proposed to date, such as the conventional k-anonymity or HgHs technique.

In addition, although it adopts the k-anonymity (local generalization) algorithm, it provides more usefulness to analysts when analyzing public data because it has less information loss compared to the HgHs algorithm. In terms of CPU execution time, it shows much faster performance than the HgHs algorithm, which basically adopts the breadth-first search approach, but it has the disadvantage of incurring additional cost because it has to go through the Final_partition() routine process compared to the k-anonymity (local generalization) algorithm. However, since this process is performed on some of the remaining transactions after the expansion of the hierarchical tree is completed, the execution time is not expected to be significantly high.

Meanwhile, in terms of security, it satisfies the security conditions of k-anonymity in the same way as k-anonymity (local generalization) and the HgHs algorithm, so it has the same performance. In addition, as mentioned in the introduction, this performance is much better than the existing 2- ^∞ anonymity (global generalization) and 2- ^∞ anonymity (deletion) algorithms. That is, k ^m -anonymity protects an individual's privacy only when the attacker knows m or fewer items, whereas ^k -anonymity does not require a limit on the number of items that the attacker can know when there is no parameter m. In general, the smaller m in k m -anonymity, the weaker the privacy provided by k ^m -anonymity. However, k-anonymity has the effect of guaranteeing stronger privacy than k ^m -anonymity.

Figure 1 is an example of a 2-anonymity (local generalization) and generalization tree hierarchy in the original database D according to the prior art.
Figure 2 is a configuration diagram of an anonymous processing system for transaction data having a set value according to an embodiment of the present invention.
Figure 3 is a flowchart of the entire process of anonymizing transaction data having a set value according to an embodiment of the present invention.
Figure 4 is a flowchart for the process of confirming anonymity review and transaction allocation in Figure 3 and the final partition routine.
Figures 5a to 5d show examples of applying the proposed algorithm to the original database D.
Figure 6 is a diagram showing the pseudocode of the proposed algorithm using top-down local generalization and bottom-up generalization hierarchical tree search.

The features and effects of the present invention described above will become more apparent through the following detailed description with reference to the attached drawings, so that a person having ordinary skill in the art to which the present invention pertains can easily implement the technical idea of the present invention.

The present invention may be modified in various ways and may take many forms, and specific embodiments are exemplified and described in detail herein.

However, this is not intended to limit the present invention to a specific disclosure form, and it should be understood that it includes all modifications, equivalents, or substitutes included in the spirit and technical scope of the present invention.

The terminology used in this application is for the purpose of describing specific embodiments only and is not intended to limit the present invention.

Hereinafter, a system and method for anonymous processing of transaction data having a set value according to a preferred embodiment of the present invention will be described in detail with reference to the attached drawings.

FIG. 2 is a configuration diagram of an anonymization system for transaction data having a set value according to an embodiment of the present invention, comprising an operating system (OS) including an anonymization manager (111) and an anonymization web screen (112) that collects transaction data containing personal information from source data and provides the anonymous data to a user terminal (140), a central processing unit (CPU) (120) that performs data anonymization for a job assigned by the anonymization manager (111) by each anonymization job scheduler (121) (Node #1, ..., Node #N), and a storage (130) that stores and preserves anonymous transaction data that has been anonymized in the central processing unit (120) and provides the same to an authorized user terminal (140).

The operation of the anonymization system for transaction data having a set value according to an embodiment of the present invention configured in this manner is described in detail as follows.

First, the present invention basically adopts the top-down partitioning algorithm, which is the same as the existing k-anonymity (local generalization), to optimize the safety and the execution time of the central processing unit (120), and at the same time, improves the shortcomings of the existing k-anonymity by additionally reallocating transactions through a bottom-up tree search process after the partitioning process. Since the existing k-anonymity basically adopts the top-down partitioning approach, it has the disadvantage of a large loss of information because the same generalization is applied only within a partitioned domain in the generalization tree structure of each transaction item, and especially for items with unique values. However, the present invention improves the shortcomings of the existing k-anonymity by additionally reallocating transactions through a bottom-up tree search process after the top-down partitioning process.

Referring to FIG. 2, the anonymous processing manager (111) of the operating system (OS) (111) collects transaction data containing personal information from source data, and assigns an anonymous processing job to the anonymous processing job scheduler (121) of the central processing unit (120) through the anonymous processing manager (111), so that the central processing unit (120) performs anonymous processing on the assigned job.

Anonymous transaction data that has been anonymized in the central processing unit (120) is stored and kept in the storage (130) (transaction data #1 to #N).

When an anonymous transaction data request is received from the user terminal (140) to which access is permitted, the transaction data stored in the storage (130) is retrieved and provided to the user terminal (140) through the anonymous processing web screen (112).

The above-mentioned anonymization processing procedure first performs anonymization job assignment to anonymization job scheduler (121) through the anonymization processing manager (111), and then performs anonymization processing for the assigned job through the anonymization processing manager (111) and the central processing unit (120).

FIG. 3 is a flowchart illustrating the entire process of anonymizing transaction data having a set value according to an embodiment of the present invention. Referring to this, the central processing unit (120) sequentially performs the anonymizing process for each step as follows.

1) [Anonymize(partition)]: A partition (dividing a tree into buckets) process (S110) constructs a generalized tree for transaction items to be processed and performs a partition process (tree splitting).

2) [Pick_node()]: Partition selection process (S120), sequentially selecting from the first partition among the divided partitions.

3) [Expand_node()]: This is a tree expansion (drill-down) process (S130), which expands the selected partition into the lower nodes of the tree.

4) [Distribute_data()]: Assigns transactions to partitions (buckets) in the process (S140), each transaction is assigned to an extended partition.

5) [Balance_partition()]: This is a K-anonymity review and transaction allocation confirmation process (S150). It checks whether the allocated transactions satisfy the k-anonymity privacy model given in advance. If satisfied, the allocated transactions are finally confirmed and move on to the '[Final_partition()]' process (S160) described below. If not satisfied, move on to the tree expansion process (S130).

6) [Sub partition()]: If there is still no satisfactory partition at this time, save the state and move to sub partition [Sub partition()] (S170) to select the next partition (S120).

7) [Final_partition()]: In the final partition process (S160), in order to minimize information loss in the K-anonymity review and transaction allocation confirmation process (S150), a reprocessing process (replacing with generalized values starting from the partition with the least information loss) is performed on the partitions that were not satisfied until the end, thereby allocating all transactions to all partitions, thereby ending the anonymization process.

Through each of the above processes, anonymous transaction data that has been anonymized is stored and preserved in storage (130).

Referring to FIG. 4, the K-anonymity review and transaction allocation confirmation process [Balance_partition()] (S150) and the final partition [Final_partition()] (S160) are described in more detail as follows.

First, in the Balance_partition() routine (S150), if there are no more nodes to drill down to, that is, expand the generalized hierarchy tree, the FinalQ_data() routine (S160) is performed to store the final generalized candidate transaction and its partition in a separate FinalQ.

And, if there is no other partition to which the transaction can be assigned within the partition divided during the drill-down process through the Balance_partition() routine (S150), the WaitForQ_data() routine is performed to store the final drill-down partition and the transaction in a separate WFQ (WaitForQ).

Next, it moves to the [Final_partition()] routine (S160), which searches each partition stored in WFQ in a bottom-up manner and additionally checks whether there is a partition that satisfies k-anonymity by matching it with the partition stored in FinalQ.

If there is a partition that satisfies this process, the transaction and partition are moved from WFQ to FinalQ, otherwise they move to the next step.

The final step is to generalize the partitions remaining in the WFQ (only the partitions immediately below the root remain) from the partition with the least information loss to the root, which is the upper level, and repeat this process until k-anonymity is satisfied, sending the transactions and partitions in the WFQ to the FinalQ. At this time, the transactions in the FinalQ are finally made public.

Figure 5 shows an example of applying the proposed algorithm to the original database D in Table 1 below. The detailed description is as follows with reference to this.

Here, Table 1 compares existing anonymization techniques in transaction database D, and in Table 1, the '*' sign indicates deletion, and the proposed algorithm is an algorithm according to the present invention.

In FIGS. 5a to 5d, rounds 1 to 6 are a process of searching the root of the generalized hierarchical tree in a top-down manner using the Anonymize(partition) routine in FIG. 6 to find the optimal partition that satisfies k=2 anonymity.

Round 1 starts from the root T of the tree, splits the nodes in the hierarchy immediately below T, and then assigns transactions t1 to t8 to each partition. (Figure 3, S110)

In Round 2, the top-down search is repeated again, expanding the nodes to the lower layers. For each partition [P, Q], either [P, J, M] or [H, K Q] can be selected (Figure 3, S120).

At this time, for the assigned transactions t2, t3, t4, and t5, the NCP, which is information loss, is measured among [Q] <- [J, M] and [P] <- [H, K], and the partition with the smaller value, that is, the partition with the smaller information loss, is drilled down (expanded) to [P, J, M]. (Fig. 3, S130)

Also, for each partition [H, K] drilled down (expanded) in the same way as in the first round, the transaction of t1 is assigned, and for [P, J, M], the transactions of t2, t3, t4, and t5 are assigned. (Fig. 3, S140)

In Round 3, the same process as Round 2 is repeated to expand [H, K] -> [H, c, d], but since it does not satisfy the k=2 anonymity requirement, it rolls back to the upper layer, and the upper layer partitions are tested to see if they satisfy the k=2 anonymity requirement. At this point, since no more partitions satisfy the k=2 anonymity requirement, the partition [H, c, d] stops expanding and is stored in the waiting queue (WFQ) along with the corresponding transaction t1 (Figure 4, S150).

In the 4th round, expansion occurs again for [P, J, M] to [P, J], [P, M], [P, J, M] (Fig. 3, S140), and in the same way as in the 1st round, transactions t2 and t5 are assigned to each partition [P, J] and transactions t3 and t4 are assigned to [P, J, M]. (Fig. 4, S150)

In the 5th round, the expansion occurs again from [P, J] -> [P, f, g] to [P, J, M] -> [K, J, M] (Fig. 3, S140), and the final [P, f, g]: t2, t5 satisfies K=2 anonymity and is stored in FinalQ: {[P, f, g]: t2, t5} (Fig. 4, S150).

In the 6th round, the same expansion process as in the 5th round is repeated until the partition [K,f,M]: t3, t4 satisfies the K=2 anonymity and is stored in FinalQ: {[K,f,M]: t3, t4}. After that, there are no more nodes to expand, so the Anonymize(partition) routine is terminated. (Fig. 4, S150)

From the 7th round to the last 11th round, the Final_partition() routine goes through two major processes (Fig. 4, S160).

Referring to Figure 4, the first process is to roll back the hierarchical tree in a bottom-up manner for the remaining WFQ partitions (and transactions assigned to the partitions) that no longer have 2-anonymity matching, compare them with the partitions in the existing FinalQ, and move the partitions that have 2-anonymity matching from WFQ to FinalQ.

If this process fails due to a mismatch, it moves to the next step. The second step is to generalize the remaining WFQ partitions (and the transactions assigned to them) from the partition with the lowest information loss to the upper layer one by one, and search for partitions (and the transactions assigned to them) that satisfy k=2 anonymity. If they are satisfied, it moves from WFQ to FinalQ.

In the 7th round, first, the remaining partitions [e,i], [e], [i] are no longer splittable and do not satisfy the k=2 anonymity, so they are all sent to the WFQ. Then, the Final_partition() routine is executed to roll back each partition of the WFQ and search for a transaction that satisfies the k=2 anonymity by matching it with the partition of the FinalQ.

In the 8th round, partition [P]: t1 satisfies k=2 anonymity, so partition [P]: t1 is assigned to FinalQ and removed from WFQ.

In the 9th round, among the remaining transactions (t6, t7, t8) in the WFQ, among [e]: t7, [i]: t8 with the smallest NCP, [e]:t7 is assigned to T, and among the other transactions, [e,i] that have [e] is updated to [T,i] in the WFQ.

In the 10th round, we check whether the partitions ([T,i], [T], [i]) remaining in the WFQ satisfy k=2 anonymity. At this time, partitions {[T,i]: t6, [T]: t7, [i]: t8} all satisfy k=2 anonymity, so all of these partitions are assigned to FinalQ and removed from WFQ. In the final 11th round, since WFQ is empty, the Final_partition() routine is terminated and the values in FinalQ are output and finally made public.

Thus, the present invention fundamentally adopts the conventional K-anonymity (local generalization) algorithm, but compared to the K-anonymity (local generalization) or HgHs algorithms, it exhibits less information loss, providing greater utility to analysts when analyzing public data. In terms of CPU execution time, it demonstrates significantly faster performance than the HgHs algorithm, which fundamentally adopts a breadth-first search approach.

On the other hand, compared to the k-anonymity (local generalization) algorithm, there is a disadvantage in that it requires an additional Final_partition() routine process, which incurs additional costs. However, since the Final_partition() routine process is performed on some of the remaining transactions after the expansion of the hierarchical tree has already been completed, it is expected that the execution time will not be significantly high.

Meanwhile, in terms of security, it satisfies the security conditions of K-anonymity in the same way as the conventional K-anonymity (local generalization) and HgHs algorithm, and thus has the same performance.

Moreover, this performance has much better security than the conventional 2- ^∞ anonymity (global generalization) and 2- ^∞ anonymity (deletion) algorithms. That is, k ^m -anonymity protects an individual's privacy only when the attacker knows no more than m items, whereas k-anonymity does not require a limit on the number of items that the attacker can know when there is no parameter m.

In general, the smaller the m of k ^m -anonymity, the weaker the privacy provided by k ^m -anonymity, but k-anonymity guarantees stronger privacy than k ^m -anonymity.

As described above, although the anonymization system and method for transaction data having a set value according to an embodiment of the present invention has been described by limited embodiments and drawings, it is not limited to these embodiments, and it is obvious that various modifications and variations can be made within the scope of the technical idea of the present invention and the equivalent scope of the patent claims to be described below by a person having ordinary skill in the art to which the present invention pertains.

110: Operating System Department 111: Anonymous Processing Manager
112: Anonymous web screen 120: Central processing unit
121: Anonymous processing job scheduler 130: Storage
140: User terminal

Claims (11)

delete delete delete In a method for anonymizing transaction data having a set value, in which transaction data containing personal information is collected from source data through an anonymization manager and data anonymization is performed through a central processing unit (CPU),
The above-mentioned anonymization manager performs a first process of assigning anonymization jobs to a job scheduler for transaction data collected from the above-mentioned source data;
The central processing unit performs a second process of anonymous processing for a job assigned to the job scheduler; and
A third process of storing anonymous transaction data, anonymized in the central processing unit, in a transaction database;
The anonymization process of the second step is performed based on a top-down partitioning algorithm, and then transactions are reallocated through a top-down tree search process.
The above second process
Step 1: Construct a generalization tree for the transaction items to be processed and perform a partitioning process;
Step 2: sequentially selecting the first partition from among the partitions divided in the above step 1;
Step 3: extending the selected partition to the lower nodes of the tree;
Step 4: Assigning each transaction to the extended partition;
Step 5: performing a balance partition (Balance_patrition()) routine to check whether the allocated transactions satisfy a pre-given k-anonymity privacy model; and
A method for anonymizing transaction data having a set value, characterized by including a step 6 of performing a final partition (Final_partition()) routine to terminate anonymization after reprocessing the remaining transactions to minimize information loss if the K-anonymity privacy model is satisfied as a result of the review in the above step 5. delete delete In paragraph 4,
A method for anonymizing transaction data having a set value, characterized in that the fifth step further includes a step of checking whether there is another partition to which the transaction (t) can be assigned within the divided partition if K-anonymity is not satisfied, and assigning the transaction (tj) to the partition until K-anonymity is satisfied. In paragraph 4,
A method for anonymizing transaction data having a set value, characterized in that the above 5th step further includes a step of checking whether there is another partition to which the transaction (t) can be assigned within the partitioned partition if K-anonymity is not satisfied, and if there is no other partition to which the transaction (t) can be assigned within the partitioned partition, assigning the transaction (tj) to a waiting queue (WaitForQ, hereinafter referred to as 'WFQ'). In paragraph 4,
If the K-anonymity check is satisfied in the above step 5, steps 1 to 4 are repeated until there are no more nodes to expand.
A method for anonymizing transaction data having a set value, characterized in that when there are no more nodes to be expanded, a final queue routine (FinalQ_data()) is performed to store a final generalized type of candidate transaction and its partition in a separate final queue (FinalQ). In paragraph 4,
The above 6th step is a method for anonymizing transaction data having a set value, characterized in that it performs a process of checking whether there is a partition that satisfies K-anonymity by matching the partitions stored in FinalQ with the partitions stored in WFQ while searching each partition stored in WFQ in a bottom-up manner, and if there is a satisfying partition, the transaction and partition are moved from WFQ to FinalQ. In Article 10,
A method for anonymizing transaction data having a set value, characterized in that transactions and partitions of WFQ are repeatedly sent to FinalQ by generalizing from the partition with the least information loss among the partitions remaining in the above WFQ to the root, which is the upper level, until K-anonymity is satisfied.