JP2016053829A - Information processing method, program, and information processing device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To efficiently derive a condition for minimizing a decrease in an information amount and abstracting information.SOLUTION: An information processing method includes retrieval processing for retrieving a minimal origin satisfying anonymity based on a prescribed condition in a first bundle defined on the basis of an order relation for abstracting classifications more with a combination of a plurality of classifications for dividing attribute values which can be taken by a plurality of object attributes as a first origin, and reference point derivation processing for deriving a new reference point on the basis of a minimal traverse of a complementary set of second origins corresponding to the retrieved minimal origin in a second bundle in which an inclusion relation of the second origins is defined as an order relation with each subset of a finite set defined on the basis of the number of divisions in each object attribute as the second origin, executes retrieval processing based on the new reference point and reference point derivation processing based on a result of the retrieval processing until a new reference point is not derived any more, and outputs a combination of divisions indicated by each of a series of retrieved minimal origins.SELECTED DRAWING: Figure 1

Description

  The present disclosure relates to an information processing method, a program, and an information processing apparatus.

  In recent years, with the development of networks and various sensors, the means for collecting various information has been diversified, and the information collected is diverse. Various information collected by such collecting means can be used in various businesses. It is utilized. In recent years, for example, by utilizing a technique called data mining, information that is not clearly shown only by individual data and is difficult to derive is extracted from a set of a plurality of data such as a database. It is also possible.

US Patent Application Publication No. 2010/0332537

  On the other hand, the collected information includes information that can identify an individual, and may require protection of the privacy of the individual. In response to such issues, it is possible to improve anonymity by abstracting various collected information and protect personal privacy, but the amount of information decreases with the abstraction of information, and data The usefulness of may be impaired.

  Therefore, the present disclosure proposes an information processing method, a program, and an information processing apparatus that can efficiently derive a condition for abstracting information while minimizing a decrease in the amount of information.

  According to the present disclosure, each attribute value that can be taken by the target attribute is gradually increased by using at least two or more attributes among the plurality of attributes of the table including a plurality of records including the plurality of attributes as the target attribute. Among the first bundles defined based on the order relation that makes the classification more abstract, with each combination between the two or more target attributes as a first element of a plurality of classifications to be abstracted When the table is abstracted based on the classification corresponding to each of the first elements, the first element that satisfies anonymity based on a predetermined condition is used as a reference point between the records of the table. Performing a search process for searching for a minimal element satisfying the anonymity, and each subset of a finite set defined based on the number of classifications for each target attribute as a second element, Among the second bundles defined as the order relation of the second original inclusion relation, the second original complement set previously associated with the searched minimal element is specified, and Performing a reference point derivation process for deriving a first element satisfying the anonymity among the first elements corresponding to each of the minimum crossings as the new reference point, and a processor is specified. The search process based on the new reference point and the reference point derivation process based on the minimal element searched by the search process are executed until the new reference point is not derived, and a series of searched There is provided an information processing method for outputting a combination of the classifications indicated by each of the minimal elements as a candidate for a condition for abstracting the table.

  Further, according to the present disclosure, each attribute value that can be taken by the target attribute is set to the computer with at least two or more attributes among the plurality of attributes of the table including a plurality of records including the plurality of attributes. A first bundle defined based on an order relationship that makes the classification more abstract, with each combination between the two or more target attributes as a first element of a plurality of classifications that are classified so as to be more abstract When the table is abstracted based on the classification corresponding to each of the first elements, the first element satisfying anonymity based on a predetermined condition between the records of the table is a reference point. As a second element, a search process for searching for a minimal element satisfying the anonymity and each subset of a finite set defined based on the number of classifications for each target attribute, Among the second bundles that define the original inclusion relation as the order relation, specify the second original complement that is associated in advance with the searched minimal element, and each minimal traversal of the complement A reference point deriving process for deriving the first element satisfying the anonymity among the first elements corresponding to the new reference point as the new reference point, and based on the specified new reference point The classification indicated by each of the searched series of minimal elements, wherein a search process and the reference point derivation process based on the minimal element searched by the search process are executed until the new reference point is not derived. Is provided as a candidate for a condition for abstracting the table.

  Further, according to the present disclosure, at least two or more attributes of the plurality of attributes of the table including a plurality of records including a plurality of attributes are set as target attributes, and each attribute value that can be taken by the target attribute is abstracted in stages. Of the first bundle defined based on the order relationship that makes the classification more abstract, with each combination between the two or more target attributes as a first element of a plurality of classifications that are classified to be When the table is abstracted based on the classification corresponding to each of the first elements, the first element satisfying anonymity based on a predetermined condition is used as a reference point between the records of the table. A minimal element search unit that executes a search process for searching for a minimal element that satisfies anonymity, and each subset of a finite set defined based on the number of classifications for each target attribute as a second element, Among the second bundles defined as the order relation of the second original inclusion relation, the second original complement set previously associated with the searched minimal element is specified, and A reference point deriving unit that executes a reference point deriving process for deriving a first element satisfying the anonymity as a new reference point among the first elements corresponding to each of the minimum crossings, and the specified new The search process based on the reference point and the reference point derivation process based on the minimal element searched by the search process are searched based on the results executed until the new reference point is not derived. There is provided an information processing apparatus comprising: an output unit that outputs the combination of classifications indicated by each of a series of the minimal elements as a candidate for a condition for abstracting the table.

  As described above, according to the present disclosure, there is provided an information processing method, a program, and an information processing apparatus capable of efficiently deriving a condition for abstracting information while minimizing a decrease in the amount of information. Provided.

  Note that the above effects are not necessarily limited, and any of the effects shown in the present specification, or other effects that can be grasped from the present specification, together with or in place of the above effects. May be played.

1 illustrates an example of a schematic system configuration of an information processing system to which an information processing apparatus according to an embodiment of the present disclosure is applied. It is explanatory drawing for demonstrating an example of a structure of a table. It is explanatory drawing for demonstrating the outline | summary of the process which produces | generates the table which improved more anonymity by generalizing the attribute value of the one part attribute of a table. It is explanatory drawing for demonstrating (k, t) -anonymity. It is explanatory drawing for demonstrating the generalization hierarchy of an attribute. It is explanatory drawing for demonstrating the generalization hierarchy of an attribute. It is explanatory drawing for demonstrating the bundle which consists of generalization strategies. It is explanatory drawing for demonstrating a hypergraph and crossing. It is explanatory drawing for demonstrating a hypergraph and crossing. It is an explanatory view for explaining an example of a functional configuration of the information processing apparatus according to the embodiment. It is explanatory drawing for demonstrating an example of the process which generalizes the attribute value of the attribute used as object. It is an example of the process result of the process which generalizes the attribute value of the attribute which becomes object based on the generalization strategy designated as an input and the generalization hierarchy of the said attribute. It is explanatory drawing for demonstrating an example of the process which determines whether a desired generalization strategy is a generalization strategy which can satisfy | fill (k, t) -anonymity. It is the figure shown about an example of the correspondence between the bundle | flux which consists of a generalization strategy, and the bundle | flux induced | guided | derived from a discrete set. It is explanatory drawing for demonstrating an example of the process which converts the element of the bundle which consists of a generalization strategy into the element of the bundle induced | guided | derived from a discrete set. It is explanatory drawing for demonstrating an example of the process which converts the element of the bundle which consists of a generalization strategy into the element of the bundle induced | guided | derived from a discrete set. It is explanatory drawing for demonstrating an example of the process which converts the element of the bundle | flux induced | guided | derived from a discrete set into the element of the bundle | flux which consists of a generalization strategy. It is explanatory drawing for demonstrating an example of the process which searches for the minimal element which satisfy | fills (k, t) -anonymity from each generalized node in the bundle | flux which consists of generalization strategies. It is explanatory drawing for demonstrating an example of the process which searches for the minimal element which satisfy | fills (k, t) -anonymity from each generalized node in the bundle | flux which consists of generalization strategies. It is explanatory drawing for demonstrating an example of the flow of a series of processes of an analysis part. It is explanatory drawing for demonstrating an example of the flow of a series of processes of an analysis part. It is explanatory drawing for demonstrating an example of the process of a control | reference point deriving part. It is explanatory drawing for demonstrating an example of the process of a control | reference point deriving part. It is explanatory drawing for demonstrating an example of the process of a control | reference point deriving part. It is explanatory drawing for demonstrating an example of a process of the local minimum element search part. It is explanatory drawing for demonstrating an example of the process result of a local minimum element search part. It is explanatory drawing for demonstrating the computational complexity of the process by the information processing apparatus which concerns on the embodiment. 10 is an explanatory diagram for describing an example of a flow of a series of processes of an analysis unit according to Modification 1. FIG. 10 is an explanatory diagram for describing an example of a flow of a series of processes of an analysis unit according to Modification 1. FIG. It is explanatory drawing for demonstrating an example of the information processing system which concerns on the modification 2. FIG. It is explanatory drawing for demonstrating an example of the information processing system which concerns on the modification 2. FIG. It is the figure which showed an example of the hardware constitutions of the information processing apparatus which concerns on the embodiment.

  Hereinafter, preferred embodiments of the present disclosure will be described in detail with reference to the accompanying drawings. In addition, in this specification and drawing, about the component which has the substantially same function structure, duplication description is abbreviate | omitted by attaching | subjecting the same code | symbol.

The description will be made in the following order.
1. Overview 2. Definition of terms 2.1. (K, t) -anonymity 2.2. Generalized hierarchy of attributes 2.3. Generalization strategy 2.4. 2. Hypergraph and crossing Functional configuration Processing 4.1. Generalization of attribute values 4.2. (K, t) -anonymity determination 4.3. Original transformation 4.4. Search for local minimum 4.5. 4. Flow of a series of processes Calculation amount Modification 6.1. Modification 1: Reduction of processing load related to search for generalization strategy 6.2. Modification 2: Example of system configuration 7. Hardware configuration Summary

<1. Overview>
First, with reference to FIG. 1, an example of the information processing system 1 to which the information processing apparatus 10 according to the embodiment of the present disclosure is applied will be described, and the problems of the information processing apparatus 10 according to the present embodiment will be organized. . FIG. 1 shows an example of a schematic system configuration of an information processing system 1 to which an information processing apparatus 10 according to the present embodiment is applied.

  As illustrated in FIG. 1, the information processing system 1 includes, for example, a DB (database) 50 in which various types of data are stored, a DB server 70, one or more clients 80, an information processing apparatus 10, and an administrator terminal 30. And generalized DB40. The information processing system 1 may include an analysis server 60 that refers to the generalized DB 40.

  The DB 50 corresponds to a so-called relational database, and includes a table d10 including a plurality of records with data including a plurality of attributes as records. For example, FIG. 2 is an explanatory diagram for explaining an example of the configuration of the table d10 included in the DB 50. The table d10 shown in FIG. 2 shows an example of the table d10 for managing the patient's medical history as data, and manages information on the patient's age, sex, illness, etc. for each patient. .

  In FIG. 2, reference symbol d <b> 11 indicates “attribute” and corresponds to an item indicating a feature included in each piece of data (“record” to be described later). Reference sign d13 indicates an “attribute value” and corresponds to a specific value taken by the attribute d11. Reference numeral d15 is a “record”, and includes a set of attribute values d13 corresponding to the attributes d11. A record is sometimes called a row or a tuple.

  The table d10 is a set of records d15. In this description, as shown in FIG. 2, the table d10 is formed by forming a record d15 with the attribute value d13 for each attribute d11 as a column, and arranging the record d15 in the row direction. To do. That is, the table d10 is expressed by listing each record d15 as a column vector of attribute values d13 for each attribute d11.

  In this description, the attribute d11 is classified into an identifier d111, a quasi-identifier d113, and a sensitive attribute d115 in order to make the characteristics of the information processing apparatus 10 according to the present embodiment easier to understand.

  The identifier d111 is an attribute for uniquely specifying each record d15, and a specific example is a primary key. A specific example of the identifier d111 is a so-called ID (identifier) such as an account ID or a service ID.

  The sensitive attribute d115 corresponds to, for example, an attribute that is considered to determine the characteristics of the table d10. As a specific example, as shown in FIG. 2, in the case of the table d10 that manages the patient's medical history as data, the attribute d11 indicating the patient's “disease” characterizes the table d10 (characterized by the table d10). Attribute) and corresponds to the sensitive attribute d115.

  Although it is difficult to identify each record d15 by itself, the quasi-identifier d113 is an attribute that can uniquely identify each record d15 by combining with other attributes d11 or can narrow down a specific record d15. Show. In the example shown in FIG. 2, the attributes indicating “age” and “gender” indicated by the reference signs d113a and d113b can be narrowed down by combining these attributes to narrow down target patients (individuals). It corresponds to the identifier d113.

  The DB server 70 is a server for referring to or updating the DB 50. In addition, the client 80 is a terminal for referring to or updating data in the DB 50 by accessing the DB server 70 via the network n1.

  The information processing device 10 generalizes (abstracts) the attribute values d13 of some of the attributes d11 for at least some of the tables d10 included in the DB 50, thereby increasing anonymity. d30 is generated.

  For example, FIG. 3 is an explanatory diagram for explaining an outline of processing for generating a table d30 with higher anonymity by generalizing (abstracting) attribute values d13 of some attributes d11 of the table d10. It is. In this description, in order to make the processing of the information processing apparatus 10 easy to understand, a case where the table d10 is a table for managing so-called personal information of a user, such as the table d10 shown in FIG. 2, will be described as an example. . Further, it is assumed that the sensitive attribute d115 indicates the attribute d11 related to the privacy of the individual, and the quasi-identifier d113 is the attribute d11 that can specify the individual.

  Specifically, in the example illustrated in FIG. 3, the information processing apparatus 10 generalizes (abstracts) the attribute values of the attributes d113a and d113b indicating “age” and “sex” in the table d10.

  For example, the information processing apparatus 10 generalizes the attribute value d15 of the attribute d113a by classifying the attribute value d15 of the attribute d113a indicating the age into attribute values indicating the generation such as teens or twenties. The anonymity of the attribute value indicating is increased.

  Specifically, the definition area of the attribute value of the attribute d113a indicating the age is {0, 1,..., 125}, the generation definition area {under 10 years old, teens, 20s,. , 100 years old or older}, the information processing apparatus 10 associates attribute values 0 to 9 indicating age with attribute values indicating less than 10 years old. Similarly, the information processing apparatus 10 associates attribute values 10 to 19 indicating age with attribute values indicating teenagers.

  That is, in the example illustrated in FIG. 3, the information processing apparatus 10 associates 20 to 29 with the attribute value [20, 29] indicating the 20s among the attribute values of the attribute d113a, and 30 to 39 indicates the 30s. Is associated with the attribute value [30, 39] indicating the anonymity of the attribute value indicating the age.

  Similarly, the information processing apparatus 10 uses the attribute value {male, female, unregistered} of the attribute d113b indicating gender as to whether or not information indicating gender is registered (that is, the registration status of information indicating gender). The attribute value {registered, unregistered} is indicated. Specifically, the information processing apparatus 10 associates “male” and “female” among the attribute values of the attribute d113b with the attribute value “registration” indicating that information indicating sex is registered, Anonymity of attribute values indicating gender is increased.

  With such generalization, for example, records with “ID” “1” to “2” and records with “ID” “3” to “4” are changed to “age” and It becomes difficult to identify based on the attribute of “sex”.

  On the other hand, the record whose “ID” is “7” is in the 40s even if the attribute values of the attributes d113a and d113b indicating “age” and “sex” are generalized, and the sex information is Since no other record exists, it can be uniquely identified. The same applies to the record whose “ID” is “8”. Therefore, the information processing apparatus 10 deletes the above-described uniquely identifiable records in the table d30 whose attribute values are generalized within a range equal to or less than the predetermined number of records.

  With such a configuration, even if any record in the table d30 is extracted and identification of the patient corresponding to the record is attempted, it becomes difficult to narrow down the possibility of the corresponding patient to less than two ways, and the anonymity Is secured.

  Here, in the example of the table d10 shown in FIG. 3, when a malicious third party can identify an individual based on “age” and “gender”, the target record can be uniquely identified. . Therefore, a malicious third party specifies a record corresponding to a specific individual from the table d10 based on the information of “age” and “gender”, and based on the specified record, the “disease” of the individual You will get new information. Note that specifying a record corresponding to a specific individual from the table based on known information such as “age” and “gender” may be referred to as “re-identification” hereinafter.

  On the other hand, as shown in the table d30, even if any record is extracted, if there is another record in which the record and "age" and "gender" overlap, the malicious third party It becomes difficult to uniquely identify an individual based on “age” and “gender”. That is, it can be seen that the anonymity of the table d30 is higher than that of the table d10.

  As described above, the information processing apparatus 10 generates a table d30 with higher anonymity by generalizing (abstracting) attribute values d13 of some attributes d11 with respect to the table d10. Then, the information processing apparatus 10 outputs the generated table d30 to the generalized DB 40. The generalized DB 40 is a configuration for managing the table d30 generated by the information processing apparatus 10.

  In this description, in order to make the configuration of the information processing system 1 easier to understand, the DB 50 and the generalized DB 40 are described as separate configurations. However, the configuration is not necessarily limited to such a configuration. As a specific example, the DB 50 and the generalized DB 40 may be configured as one DB, and the table d10 and the table d30 generated based on the table d10 may be managed in the DB.

  The administrator terminal 30 is an example of an interface for the administrator of the so-called DB 50 or generalized DB 40 to operate the information processing apparatus 10.

  The DB server 70 may be configured to refer to the table d30 in the generalized DB 40. Further, the analysis server 60 analyzes the information in the table d30 stored in the generalized DB 40 by using, for example, a technique such as data mining, and the analysis result is sent to the client 80 via the network n11. It may be output.

  Heretofore, an example of a schematic system configuration of the information processing system 1 to which the information processing apparatus 10 according to the present embodiment is applied has been described with reference to FIG.

  As described above, the information processing apparatus 10 generalizes the attribute values d13 of some attributes d11 for at least some tables d10 included in the DB 50, and deletes some records as necessary. Thus, the table d30 with higher anonymity is generated.

  In addition, the anonymity tends to be higher as the attribute value is more generalized. On the other hand, by generalizing attribute values, each attribute value that was previously identified is collected as the same attribute value, so the information for identifying individual records is impaired, and information The amount decreases. Therefore, as the attribute value becomes more general, the usefulness of the data tends to be impaired.

  In addition, as the maximum number of records to be deleted increases, anonymity tends to become higher. On the other hand, it goes without saying that deletion of a record leads to a decrease in the amount of information, and as the number of records to be deleted increases, the amount of information further decreases. That is, as the maximum value of the number of records to be deleted increases, there is a higher possibility that the range of the population is more restricted, and the usefulness of data may be further impaired.

  Thus, the guarantee of anonymity and the usefulness as data are in a trade-off relationship. Therefore, a condition for abstracting attribute values that satisfies anonymity based on a predetermined condition (to be described later, (k, t) -anonymity) and can minimize a decrease in the amount of information. It is desirable to specify.

  On the other hand, when anonymity is ensured by generalizing the attribute value d13 for a plurality of attributes d11, to what extent the attribute d11 is generalized (that is, how much the level of generalization is set) ) Whether the anonymity based on a predetermined condition is secured depends on the data in the table d10 (that is, each record d15). Therefore, it is possible to estimate in advance the amount of calculation for specifying the conditions for abstracting attribute values that can satisfy anonymity based on predetermined conditions and minimize the decrease in the amount of information. It was difficult.

  Further, as the number of attributes d11 to be generalized increases, the number of combinations of generalization levels among a plurality of attributes d11 increases. From these characteristics, it is possible to efficiently derive conditions for abstracting attribute values that can satisfy anonymity based on a predetermined condition and can minimize a decrease in the amount of information. A mechanism is required.

  Therefore, as the information processing apparatus 10 according to the present embodiment, a condition for abstracting attribute values that satisfies anonymity based on a predetermined condition and can minimize a reduction in the amount of information is efficiently used. We propose a mechanism that can be derived well. Hereinafter, the information processing apparatus 10 according to the present embodiment will be described in more detail.

<2. Definition of terms>
In describing details of the information processing apparatus 10 according to the present embodiment, first, definitions of terms used in the present description are summarized below.

[2.1. (K, t) -anonymity]
In this section, (k, t) -anonymity, which is a condition for anonymity, will be described with reference to FIG. FIG. 4 is an explanatory diagram for explaining (k, t) -anonymity. In the example shown in FIG. 4, as in FIG. 3, the table d10 for managing the patient's medical history as data is generalized with the attribute values of the “age” and “sex” attributes d113a and d113b. The case where the table d30 which raised anonymity is produced | generated is shown.

  In FIG. 4, reference symbols d351 to d355 indicate sets in which the attribute value combinations between the attributes are equal when the attribute values of the “age” and “sex” attributes d113a and d113b are generalized. In the following description, a set having the same combination of attribute values between attributes may be referred to as an “equivalent class”. For example, in the equivalence class d351, the attribute value of the attribute d313a indicating “age” is “[20, 29]” indicating “20's”, and the attribute value of the attribute d313b indicating “sex” indicates gender. A set of “registration” indicating that information is registered is shown. Similarly, in the equivalent class d353, the attribute value of the attribute d313a indicating “age” is “[30, 39]” indicating “30's”, and the attribute value of the attribute d313b indicating “sex” is gender. A set of “unregistered” indicating that the indicated information is not registered is shown.

  Here, when an arbitrary equivalent class is extracted from the table, if the number of records of the equivalent class is k or more in any case, the table indicates “k-anonymity”. Satisfy. That is, for a table that satisfies k-anonymity, it is difficult to narrow down candidates for re-identification to less than k, no matter which record in the table is re-identified.

  Even when the table does not satisfy k-anonymity, it may be possible to satisfy k-anonymity by deleting all records whose number of records in the equivalent class is less than k. In this way, by deleting records in a range where the number of records is equal to or less than t, the case where k-anonymity can be satisfied is expressed as “(k, t) -anonymity ((k, t) -Anonymity)”. "

  As a specific example, whether or not the tables d10 and d30 satisfy (2, 2) -anonymity with k = 2 and t = 2 in the example illustrated in FIG. 4 will be described below.

  For example, in the table d10, the attribute value of the attribute d113a indicating “age” is different. Therefore, for example, when re-identification is attempted for a record whose “age” is “29” and “sex” is “female”, the record whose “ID” is “2” is uniquely identified. The same applies to other records. That is, it can be seen that the table d10 does not satisfy 2-anonymity.

  Further, in the table d10, when focusing on the attributes d113a and d113b of the “age” and “gender”, there is no other record having the same combination of attribute values between the attributes. That is, the table d10 does not satisfy 2-anonymity even if records are deleted in a range where the number of records is 2 or less. That is, the table d10 does not satisfy (2, 2) -anonymity.

  On the other hand, the table d30 satisfies (2, 2) -anonymity. Specifically, since the table d30 includes equivalence classes d354 and d353 having the number of records of less than 2, 2-anonymity is not satisfied. However, by deleting records corresponding to the equivalent classes d354 and d353 having the number of records less than 2, the table d30 after the record deletion satisfies 2-anonymity. At this time, since the number of records corresponding to the equivalent classes d354 and d353 is 2 (that is, 2 or less), the table d30 satisfies (2, 2) -anonymity.

  The anonymity condition (k, t) -anonymity has been described above with reference to FIG.

[2.2. Generalized hierarchy of attributes]
Next, a generalized hierarchy of attributes will be described with reference to FIGS. 5 and 6 are explanatory diagrams for explaining a generalized hierarchy of attributes.

  Here, “attribute generalization hierarchy” means the generalization correspondence between the attribute value before generalization and the attribute value after generalization when attribute values are generalized step by step for one attribute The relationship is shown in a hierarchical structure (so-called tree structure).

  For example, FIG. 5 illustrates an example of an attribute generalization hierarchy for generalizing (abstracting) the attribute value of the attribute d113a indicating “age” in the table d10 illustrated in FIG. In the following, the attribute generalization hierarchy for generalizing (abstracting) the attribute d113a shown in FIG. 5, that is, the generalization hierarchy of the attribute d113a will be described as “attribute generalization hierarchy d21”. There is.

  In the example shown in FIG. 5, the attribute value d13 of the attribute d113a indicating “age” is generalized in two stages. In FIG. 5, reference symbol d22 indicates the height of each layer in the attribute generalization layer d21 when the attribute value d13 of the attribute indicating “age” is generalized stepwise. Hereinafter, the height of each layer may be described as a “generalization level”.

  In FIG. 5, reference symbol d <b> 210 indicates a series of attribute values that can be taken by the attribute indicating “age”, that is, a hierarchy corresponding to the attribute value indicated by the domain {0, 1, 2,. Is shown. Note that in the attribute generalization layer d21 shown in FIG. 5, a series of attribute values that can be taken by the attribute indicating “age”, that is, the generalization level of the attribute value layer d210 that has not been generalized is set to “0”. Is set.

  The reference sign d211 indicates the “generation” when the attribute value indicating the “age” indicated in the hierarchy d210 is generalized to be classified into the attribute value indicating the “generation”. The hierarchy corresponding to the attribute value is shown. In the example shown in FIG. 5, the definition area of the attribute value indicating “generation” is indicated by {under 10 years old, 10s, 20s,..., 90s, over 100 years}.

  In the example illustrated in FIG. 5, the attribute values “0” to “9” in the hierarchy d210 are associated with the attribute value “[0, 9]” indicating “under 10 years” in the hierarchy d211. That is, the attribute generalization hierarchy d21 indicates that the attribute values “0” to “9” in the hierarchy d210 are generalized to the attribute values “[0, 9]” in the hierarchy d211. Similarly, the attribute values “10” to “19” in the hierarchy d210 are generalized to the attribute value “[10, 19]” indicating “10th generation” in the hierarchy d211. Note that, in the attribute generalization layer d21 shown in FIG. 5, the generalization level of the layer d211 is set to “1”.

  Reference numeral d212 indicates a hierarchy corresponding to the attribute value when the attribute value indicating "generation" indicated by the hierarchy d211 is further classified into a generalized attribute value. In the attribute generalization hierarchy d21 shown in FIG. 5, the hierarchy d212 indicates attribute values when each age is not identified, and the definition area is {[0, 125]}. That is, when the attribute value of the hierarchy d211 is generalized to the attribute value of the hierarchy d212, any attribute value of the hierarchy d211 is generalized to the attribute value “[0, 125]” of the hierarchy d212. In the attribute generalization hierarchy d21 shown in FIG. 5, the generalization level of the hierarchy d212 is set to “2”.

  In this way, the attribute generalization hierarchy d21 is configured such that the higher the generalization hierarchy, the higher the hierarchy (that is, the higher the generalization level).

  Similarly, FIG. 6 shows an example of an attribute generalization hierarchy for generalizing (abstracting) the attribute value of the attribute d113b indicating “sex” in the table d10 shown in FIG. In the following, the attribute generalization hierarchy for generalizing (abstracting) the attribute d113b shown in FIG. 5, that is, the generalization hierarchy of the attribute d113b is described as “attribute generalization hierarchy d23”. There is.

  In the example shown in FIG. 6, the attribute value d13 of the attribute d113b indicating “sex” is generalized in two stages. In FIG. 6, reference numeral d24 indicates the height (that is, the generalization level) of each hierarchy in the attribute generalization hierarchy d23 when the attribute value d13 of the attribute indicating “gender” is generalized stepwise. ing.

  In FIG. 6, a reference symbol d <b> 230 indicates a hierarchy corresponding to a series of attribute values that can be taken by the attribute indicating “gender”, that is, the attribute value indicated in the domain {male, female, unregistered}. Note that in the attribute generalization layer d23 shown in FIG. 6, a series of attribute values that can be taken by the attribute indicating “gender”, that is, the generalization level of the attribute value layer d230 that has not been generalized is set to “0”. Is set.

  Further, the reference sign d231 is obtained by generalizing a series of attribute values indicating the “sex” indicated in the hierarchy d230 to be classified into attribute values indicating the “registration status of information indicating sex”. A hierarchy corresponding to the attribute value is shown. In the example shown in FIG. 5, the definition area of the attribute value indicating “registration status of information indicating gender” is indicated by {registered, unregistered}.

  In the example illustrated in FIG. 6, the attribute values “male” and “female” in the hierarchy d210 are associated with the attribute value “registration” indicating that “information indicating sex” is registered in the hierarchy d231. Yes. That is, the attribute generalization hierarchy d23 indicates that the attribute values “male” and “female” in the hierarchy d230 are generalized to the attribute value “registration” in the hierarchy d231. Similarly, the attribute value “unregistered” in the hierarchy d230 is associated with the attribute value “unregistered” indicating that “information indicating gender is not registered” in the hierarchy d231. Note that in the attribute generalization layer d23 shown in FIG. 6, the generalization level of the layer d231 is set to “1”.

  Reference numeral d232 indicates a hierarchy corresponding to the attribute value when the attribute value indicating the “registration status of information indicating gender” indicated in the hierarchy d231 is further classified into a generalized attribute value. Yes. In addition, in the attribute generalization hierarchy d23 shown in FIG. 6, the hierarchy d232 shows the attribute value when the gender is not identified, and the gender of each patient is unknown by setting the definition area to {unknown}. It shows the case where it is handled as a certain thing. That is, when the attribute value of the hierarchy d231 is generalized to the attribute value of the hierarchy d232, any attribute value of the hierarchy d231 is generalized to the attribute value “unknown” of the hierarchy d232. Note that in the attribute generalization hierarchy d23 shown in FIG. 6, the generalization level of the hierarchy d232 is set to “2”.

  Note that the attribute generalization hierarchy d23 is set so that the higher the generalization level is, the higher the hierarchy becomes higher (that is, the generalization level is the same as the attribute generalization hierarchy d21 described with reference to FIG. 5). Configured to be higher).

  The attribute generalization hierarchy has been described above with reference to FIGS. 5 and 6.

[2.3. Generalization strategy]
Next, an example of a generalization strategy for generalizing the table d10 will be described. As described with reference to FIG. 5 and FIG. 6, when a generalization hierarchy is given for each of a plurality of attributes, a difference in which generalization is performed for each attribute (that is, for each attribute) There are a plurality of generalization methods depending on the combination of the height of the generalization hierarchy of attributes.

For example, in the example shown in FIGS. 5 and 6, the height of the generalized hierarchy of the attribute d113a indicating “age” is 0 (age), 1 (generation), 2 (no distinction), and indicates “sex”. The height of the generalized hierarchy of the attribute d113b is 0 (gender), 1 (registration status), 2 (unknown (no distinction)). Here, the height of the generalization hierarchy of attributes d113a indicating "age" _{v 1,} the height of the generalization hierarchy of attributes d113b indicating "sex" in the case of the _{v 2, [v 1, v} 2] The combinations are [0, 0], [0, 1],..., [2, 1], [2, 2]. As described above, the combination of the heights of the generalization hierarchies of the attributes to be generalized may be described as “Generalization Strategy” in this description.

  For example, when the generalization strategy [1, 2] is applied, the attribute value of the attribute d113a indicating “age” is generalized to the attribute value indicating “generation” having a height of “1”. The attribute value of the attribute d113b indicating “” is generalized to an attribute value indicating “unknown (no distinction)” having a height of “2”. As described above, each generalization strategy indicates an index for generalizing the attribute values of the attributes d113a and d113b indicating “age” and “sex” in the table d10.

Here, a generalization strategy a and any one of the elements of the generalization strategy a (that is, the height of the generalization hierarchy of any one attribute) are increased by 1 (that is, The magnitude relationship of the generalization strategy b (generalized for one layer) is assumed to be a <b. As a specific example, the generalization strategies [1,1] and [1,2] have a relationship of [1,1] <[1,2]. Similarly, the generalization strategies [1,2] and [2,2] have a relationship of [1,2] <[2,2]. On the other hand, no magnitude relationship is defined between the generalization strategies [1,2] and [2,1]. Such a magnitude relationship is defined as an order relationship, and a series of generalization strategies [v ₁ , v ₂ ] = [0, 0], [0, 1],..., [2, 1], [2, 2], the generalization strategy [v ₁ , v ₂ ] forms a lattice. Hereinafter, this bundle may be referred to as a “bundle composed of generalization strategies”.

For example, FIG. 7 is an explanatory diagram for explaining a bundle of generalization strategies. FIG. 7 is based on the generalization strategy [v ₁ , v ₂ ] defined based on the generalization hierarchy of the attributes d113a and d113b indicating “age” and “sex” shown in FIG. 5 and FIG. Shows an example of a bundle of generalization strategies.

Further, in this description, for a bundle <L, ≦> in which a partial order relation is defined, a function q that satisfies the properties shown in (Condition 1) and (Condition 2) below is expressed as a bundle <L, ≦>. Called the query function.
(Condition 1) q: L → {0,1}; mapping to a Boolean value with a set of bundles as a domain (Condition 2) For any a, bεL, if a ≦ (≧) b Q (a) ≦ (≧) q (b)

Further, when a bundle <L, ≦> in which a partial order is defined and the above-described query function q are given, elements satisfying (Condition 3) and (Condition 4) shown below (ie, generalization) Strategy) a = [v ₁ , v ₂ ] is called a minimal element.
(Condition 3) q (a) = 1
(Condition 4) q (b) = 0 for any a> bεL

For example, in the example shown in FIG. 7, the generalization strategies [2, 2], [2, 1], [1, 2], [1, 1], [2, 0] are based on the query function q, ((V ₁ , v ₂ )) = 1 is satisfied. Further, the generalization strategies [0, 2], [0, 1], [1, 0], [0, 0] satisfy q ((v ₁ , v ₂ )) = 0 based on the query function q. . At this time, the reference sign d50 has a boundary between an element satisfying q ((v ₁ , v ₂ )) = 1 (that is, a generalized strategy) and an element satisfying q ((v ₁ , v ₂ )) = 0. The elements [1, 1] and [2, 0] are the minimal elements.

  The example of the generalization strategy for generalizing the table d10 and the example of the bundle composed of the generalization strategy have been described above with reference to FIG.

[2.4. Hypergraph and crossing]
Next, the hypergraph and the crossing will be described with reference to FIGS. 8 and 9 are explanatory diagrams for explaining the hypergraph and the crossing.

  In describing the hypergraph, first, a graph (V, E) including a vertex set V and an edge E connecting two vertices in the set V will be described with reference to FIG. For example, in the example shown in FIG. 8, V = {1, 2, 3, 4, 5}, E = {{1, 4}, {1, 5}, {2, 3}, {2, 4}, The graph (V, E) which becomes {4, 5}} is shown. Here, for example, the edge E = {1, 4} indicates an edge connecting the vertex “1” and the vertex “4”. Similarly, an edge E = {2, 3} indicates an edge connecting the vertex “2” and the vertex “3”.

  On the other hand, a graph obtained by generalizing the edge E of the graph (V, E) shown in FIG. 8 into a hyper edge H connecting two or more vertices is called a hyper graph (V, H). FIG. 9 shows an example of the hypergraph (V, H). For example, in the example shown in FIG. 9, V = {1, 2, 3, 4, 5}, H = {{1, 2, 4}, {1, 5}, {2, 3, 5}, {1 , 4, 5}}, a hypergraph (V, H) is shown. Here, for example, the hyper edge H = {1, 2, 4} indicates a hyper edge connecting the vertex “1”, the vertex “2”, and the vertex “4”. Similarly, the hyper edge H = {1, 5} indicates a hyper edge connecting the vertex “1” and the vertex “5”.

  Next, crossing will be described with reference to FIG. A subset of V that shares at least part with any hyperedge of the hypergraph (V, H) is called “crossing”. In addition, a crossing that does not become a crossing if any element is removed is called a “minimal crossing”.

  For example, in the example shown in FIG. 9, the subset {1, 2, 4} of V has hyperedges H = {{1, 2, 4}, {1, 5}, {2, 3, 5}, { 1, 4, 5}} shares a part and corresponds to crossing. Further, the subset {1, 2} obtained by removing the element “4” from the subset {1, 2, 4} is a hyper edge H = {{1, 2, 4}, {1, 5}, {2 , 3, 5} and {1, 4, 5}} share a part. This shows that the subset {1, 2, 4} is not a minimal crossing.

  Further, the subset {1, 2} of V corresponds to the crossing as described above. However, if any one of the elements “1” and “2” is removed, the hyper edge H = {{1, 2, 4}, { 1, 5}, {2, 3, 5}, and {1, 4, 5}} are not shared in part. From this, the subset {1, 2} corresponds to the minimum crossing. Similarly, the subset {1, 5} of V is also a minimal crossing.

  The hypergraph and the crossing have been described above with reference to FIGS. 8 and 9.

<3. Functional configuration>
Next, an example of a functional configuration of the information processing apparatus 10 according to the present embodiment will be described with reference to FIG. FIG. 10 is an explanatory diagram for describing an example of a functional configuration of the information processing apparatus 10 according to the present embodiment.

  As illustrated in FIG. 10, the information processing apparatus 10 includes a DB information acquisition unit 11, a DB information output unit 12, a hierarchy information acquisition unit 13, an analysis unit 14, an analysis result output unit 15, and a generalized condition acquisition. Unit 16, DB information conversion unit 17, and conversion result output unit 18.

  The DB information acquisition unit 11 acquires, from the DB 50, information on the table d10 to be processed (that is, data defining the table, such as attribute definition information and each record) among the tables included in the DB 50. . Note that the table d10 to be processed is a table serving as input information for generating a table d30 with higher anonymity by generalizing (abstracting) attribute values of some attributes. Yes. The DB information acquisition unit 11 outputs the acquired information of the table d10 to each of the DB information output unit 12, the analysis unit 14, and the DB information conversion unit 17. The DB information acquisition unit 11 holds or stores the acquired information of the table d10 in a storage unit (not shown), so that the information of the table is indirectly stored in the DB information output unit 12 via the storage unit. The data may be output to each of the analysis unit 14 and the DB information conversion unit 17.

  The DB information output unit 12 acquires information on the table d10 to be processed from the DB information acquisition unit 11, and presents the acquired information on the table d10 to the administrator via the administrator terminal 30. Thereby, the administrator defines the attribute to be generalized (abstracted) of the attribute value and the attribute generalization hierarchy for generalizing (abstracting) the attribute value of the attribute in the table d10. It becomes possible to do.

  The hierarchy information acquisition unit 13 is information indicating attributes to be generalized (abstracted) of attribute values specified by the administrator via the administrator terminal 30 among the attributes of the table d10 to be processed. And information indicating the generalized hierarchy of each attribute are acquired from the administrator terminal 30. Then, the hierarchy information acquisition unit 13 outputs to the analysis unit 14 information indicating an attribute that is a target of generalization (abstraction) of the acquired attribute value and information indicating a generalization hierarchy of each attribute.

  Further, the hierarchy information acquisition unit 13 may acquire information indicating anonymity conditions specified by the administrator via the administrator terminal 30 from the administrator terminal 30. Note that the information indicating the condition of anonymity is, for example, (k, t) -anonymity condition, the threshold value k of the number of records included in the equivalence class for satisfying k-anonymity, and deletion This corresponds to the maximum value t of the number of records to be recorded. Then, the hierarchy information acquisition unit 13 outputs information indicating the condition of anonymity acquired from the administrator terminal 30 to the analysis unit 14.

  Note that the acquisition source of the information indicating the anonymity condition is not necessarily limited to the administrator terminal 30. As a specific example, the hierarchical information acquisition unit 13 acquires information indicating anonymity conditions stored in advance in a storage unit (not shown) in the information processing apparatus 10, and the acquired information is analyzed by the analysis unit 14. May be output.

  The analysis unit 14 acquires information on the table d10 to be processed from the DB information acquisition unit 11. Further, the analysis unit 14 receives information indicating an attribute that is a target of generalization (abstraction) of the attribute value from among the attributes of the table d10 to be processed from the hierarchy information acquisition unit 13, and general information of each of the attributes. Information indicating the hierarchization hierarchy. Further, the analysis unit 14 acquires information indicating anonymity conditions from the hierarchy information acquisition unit 13.

  The analysis unit 14 further increases the anonymity of the table d10 based on the information indicating the attribute to be generalized (abstracted) of the acquired attribute value and the information indicating the generalized hierarchy of each attribute. A generalization strategy (that is, a combination of the heights of the generalization hierarchies of each attribute) for conversion into the table d30 is defined. In addition, the generalization strategy specified by this is equivalent to the combination of each classification for classifying the attribute values so that the attribute values of each target attribute are more generalized (abstracted). To do. And the analysis part 14 extracts the generalization strategy which can satisfy | fill the acquired anonymity conditions and can suppress the reduction | decrease in an information amount to the minimum among each predetermined generalization strategy.

  Therefore, the configuration and operation of the analysis unit 14 described above will be described in detail below. As shown in FIG. 10, the analysis unit 14 includes an analysis data generation unit 141, a local minimum search unit 143, and a reference point derivation unit 145.

  The analysis data generation unit 141 extracts a combination of heights of the generalized hierarchies of each attribute based on the information indicating the generalized hierarchies of the attributes to be generalized (abstracted) of the attribute values. Specify the combination as a generalization strategy.

  Then, the analysis data generation unit 141 is based on each predetermined generalization strategy, and the order relation (in other words, the generalization hierarchy of each attribute that each generalization strategy has as an element is more generalized (in other words, abstracted). And a bundle of generalization strategies based on an order relation that abstracts the classification of each attribute. At this time, the analysis data generation unit 141 increases, for example, one generalized strategy a and any one element of the generalized strategy a by 1 (that is, generalized by one layer) ) Define a bundle of generalization strategies based on an order relationship in which the magnitude relation of the generalization strategy b is a <b.

  As a specific example, the analysis data generation unit 141 includes the generalization strategy shown in FIG. 7 from the generalization hierarchy of attributes corresponding to “age” and “gender” shown in FIGS. 5 and 6. A bundle will be defined. In the following, the element in the bundle composed of generalization strategies may be described as “generalized node”. Further, hereinafter, a case will be described as an example in which processing is performed on a bundle composed of the attribute generalization hierarchy shown in FIGS. 5 and 6 and the generalization strategy shown in FIG.

  Note that a bundle composed of generalization strategies corresponds to an example of a “first bundle”. Further, each element in a bundle composed of generalized strategies, that is, a generalized strategy defined based on a combination of heights of generalized hierarchies of each attribute corresponds to an example of “first element”.

  The minimal element search unit 143 is a generalization capable of satisfying the acquired anonymity condition (that is, (k, t) -anonymity) among the generalized nodes in the bundle composed of the predetermined generalization strategies. Search for the minimal element corresponding to the strategy. Note that the generalized strategy that can satisfy (k, t) -anonymity is that when the table d10 is generalized (abstracted) based on the generalized strategy, the generalized table d30 is ( k, t) —denote a generalization strategy that can satisfy anonymity.

  Specifically, the minimal element search unit 143 is a generalized strategy in which a generalized strategy corresponding to a generalized node in a bundle of predetermined generalized strategies can satisfy (k, t) -anonymity. Is determined as a query function q. In the following, an element corresponding to a generalized strategy that can satisfy (k, t) -anonymity (that is, a generalized node) is simply referred to as “element satisfying (k, t) -anonymity”. May be described.

  Then, the minimal element search unit 143 uses, as a reference point, any element (generalized node) that satisfies (k, t) -anonymity in a bundle of predetermined generalized strategies. A minimal element satisfying (k, t) -anonymity is searched for in a direction to make at least one of them more specific.

  Specifically, the minimal element search unit 143 uses any element among the original elements (that is, the height of the generalized hierarchy) confirmed to satisfy (k, t) -anonymity. It shifts in the direction which materializes, and it is determined whether the element after the said shift is an element which satisfies (k, t) -anonymity. Then, when the element after the shift satisfies (k, t) -anonymity, the minimal element search unit 143 shifts one of the elements in a direction that further embodies, and the element after the shift becomes (k, t t)-If anonymity is not satisfied, shift any element in the direction of generalization (abstraction). Thus, the minimal element search unit 143 shifts any element and sequentially executes a process of determining whether the element after the shift satisfies (k, t) -anonymity, k, t) —search for a minimal element satisfying anonymity.

  The search method is not particularly limited as long as the minimum element search unit 143 can search for a minimum element satisfying (k, t) -anonymity. As a specific example, the local minimum search unit 143 may search for a local minimum satisfying (k, t) -anonymity based on a so-called binary search.

  Moreover, the generalization strategy which shows the combination of the classification (generalization hierarchy) which generalizes (abstracts) the attribute value of each attribute most can satisfy (k, t) -anonymity. Therefore, the generalized node corresponding to the generalization strategy can be a reference point when searching for a minimal element that satisfies (k, t) -anonymity. As a specific example, it corresponds to the generalization strategy when the height of the generalization hierarchy of the attribute corresponding to each of “age” and “gender” shown in FIGS. 5 and 6 is set to “2” respectively. The generalized node (that is, the generalized node indicated by (2, 2) in FIG. 7) can be a reference point when searching for a minimal element that satisfies (k, t) -anonymity.

  As described above, the minimum element search unit 143 searches for a minimum element that satisfies (k, t) -anonymity from a bundle of generalization strategies, and holds information on the searched minimum element. Further, the minimal element search unit 143 notifies the reference point deriving unit 145 of the search result of the minimal element that satisfies (k, t) -anonymity.

  The reference point deriving unit 145 acquires a search result of a minimal element satisfying (k, t) -anonymity from the minimal element searching unit 143. The reference point deriving unit 145 determines (k, t) among the generalized nodes that have not been searched by the minimal element search unit 143 in a bundle of predetermined generalization strategies based on the obtained search result of the minimal element. )-A generalized node that satisfies anonymity is derived, and the derived generalized node is output to the local minimum search unit 143 as a new reference point candidate.

  In response to the output of this new reference point candidate, the local minimum search unit 143 searches for a local minimum satisfying (k, t) -anonymity using the candidate as a reference point, and uses the search result as a reference. The data is output to the point deriving unit 145.

  The minimum element search unit 143 searches for a minimum element satisfying (k, t) -anonymity, and the reference point deriving unit 145 derives a new reference point candidate based on the search result. Details will be described later.

  As described above, the local minimum element search unit 143 operates in cooperation with the reference point deriving unit 145 until the reference point deriving unit 145 no longer extracts a new reference point candidate (k, t). -Search for and maintain a minimal element that satisfies anonymity. Then, the minimal element search unit 143 generates a generalized strategy corresponding to each of the stored series of minimal elements (that is, the searched series of (k, t) -minimum elements satisfying anonymity), and the analysis result output unit 15 is output.

  The analysis result output unit 15 acquires a generalization strategy corresponding to each of a series of minimum elements searched by the minimum element search unit 143 from the minimum element search unit 143. The analysis result output unit 15 then generalizes (abstracts) the table d10 so that the acquired series of generalization strategies satisfy (k, t) -anonymity (ie, generalization strategy). To the administrator via the administrator terminal 30 as candidates. Note that the conditions presented at this time, that is, the table d10 is generalized so that the generalization strategy corresponding to each of the searched series of minimal elements satisfies the previously specified (k, t) -anonymity, and This corresponds to a generalization strategy that can minimize the decrease in the amount of information.

  The generalization condition acquisition unit 16 generalizes (abstracts) the table d10 based on the generalization strategy specified by the administrator via the administrator terminal 30 among the series of generalization strategies defined by the analysis unit 14. ) Is acquired from the administrator terminal 30. The conditions for generalizing (abstracting) the table d10 are information indicating a classification for generalizing (abstracting) attribute values of each attribute based on the generalization strategy specified by the administrator. , (K, t) —corresponds to information indicating anonymity conditions. Hereinafter, a condition for generalizing (abstracting) the table d10 may be referred to as “generalization condition for the table d10”.

  Then, the generalization condition acquisition unit 16 outputs information indicating the generalization condition of the acquired table d10 to the DB information conversion unit 17.

  The DB information conversion unit 17 acquires information on the table d10 to be processed from the DB information acquisition unit 11. Also, the DB information conversion unit 17 acquires information indicating the generalization condition of the table d10 from the DB information conversion unit 17.

  The DB information conversion unit 17 improves the anonymity of the information of the table d10 by generalizing the attribute value of the target attribute in the table d10 based on the information indicating the generalization condition of the table d10. Is converted into information of the table d30.

  Specifically, the DB information conversion unit 17 associates the attribute value of the attribute to be generalized with the attribute value in the classification specified as the generalization condition in the table d10, thereby obtaining the attribute value of the attribute. Generalize. For example, the DB information conversion unit 17 abstracts the attribute value of the attribute indicating the age by associating the attribute value of the attribute indicating the age with the attribute value indicating the generation.

  Further, the DB information conversion unit 17 determines that the number of equivalent class records is k from the table d10 in which the attribute values are abstracted based on the (k, t) -anonymity condition specified as the generalization condition of the table d10. Records that are less than the number of records are deleted within a range where the number of records is t or less. As described above, the DB information conversion unit 17 converts the information in the table d10 into information in the table d30 with higher anonymity.

  Then, the DB information conversion unit 17 outputs the information of the table d30 generated by converting the information of the table d10 to the generalized DB 40 via the conversion result output unit 18. The conversion result output unit 18 corresponds to an interface for outputting the information of the table d30 generated by the DB information conversion unit 17 to the generalized DB 40.

  Heretofore, an example of the functional configuration of the information processing apparatus 10 according to the present embodiment has been described with reference to FIG.

<4. Processing>
Next, with regard to the flow of a series of processes of the information processing apparatus 10, in particular, the process of the analysis unit 14, that is, the process of deriving generalization strategy candidates for generalizing (abstracting) the table d10 to be processed. This will be described in more detail with a focus on. In this description, as the processing of the analysis unit 14, first, “generalization of attribute value”, “(k, t) -anonymity determination”, “original conversion”, and “minimum element search” are performed. Each of the partial processes will be described, and then “a series of process flows (that is, an overall process flow)” will be described.

[4.1. Generalization of attribute values]
First, referring to FIG. 11, the process of generalizing the attribute value of the target attribute among the records in the table d10 based on the generalization strategy specified as input and the generalization hierarchy of the attribute. An example will be described. FIG. 11 is an explanatory diagram for explaining an example of the process of generalizing the attribute value of the target attribute, and is a diagram schematically showing the algorithm of the process in a so-called program code format. In the example shown in FIG. 11, some information is abstracted for easy understanding of the processing flow, and is not necessarily shown in a format that can be compiled based on a compiler of a specific programming language.

The “getFrequentSets” function shown in FIG. 11 takes as input a generalization strategy (that is, a generalized node) indicated by variables v = (v ₁ , v ₂ ,..., V _n ) and a variable T. The table d10 to be processed and the information indicating the generalized hierarchy of each attribute indicated by the variables (H ₁ , H ₂ ,..., H _n ) are acquired.

Note that each of (v ₁ , v ₂ ,..., V _n ) corresponds to a different attribute, and the height of the generalized hierarchy specified for each attribute (in other words, the attribute value of the attribute) , Classification for generalization). Similarly, (H ₁ , H ₂ ,..., H _n ) correspond to mutually different attributes, and indicate generalized hierarchies of the respective attributes. For example, H _i (v _i ) indicates a hierarchy (classification) whose height corresponds to v _i among the generalized hierarchies of the i-th attribute.

Specifically, the “getFrequentSets” function shown in FIG. 11 assigns each record r of the table T acquired as an input to the equivalence class. At this time, when the attribute value of each attribute of the record r is r _i , the function replaces the value d _i when generalized to the attribute (classification) of the height v _i in the generalization hierarchy of the attribute. Thus, the equivalence class to which each record r is to be assigned is specified.

More specifically, the “getFrequentSets” function is a combination of values satisfying the attribute value r _i ∈d _i ∈ H _i (v _i ) for an arbitrary height v _i for each record r in the table T. = (D ₁ , d ₂ ,..., D _n ) is specified. The function assigns each record r to an equivalence class corresponding to the value combination d according to the specified value combination d. As described above, the function generates a set F ′ of equivalence classes to which each record r is assigned, and outputs the generated set F ′.

  For example, FIG. 12 illustrates an example of a processing result of a process of generalizing an attribute value of a target attribute based on a generalization strategy specified as an input and a generalization hierarchy of the attribute. The example illustrated in FIG. 12 illustrates an example in which the attribute values of the attributes d113a and d113b indicating “age” and “sex” in the table d10 illustrated in FIG. 2 are generalized. In the example shown in FIG. 12, in order to generalize the attribute values of the attributes d113a and d113b, the attribute generalization hierarchy shown in FIGS. 5 and 6 is used, and the height of each generalization hierarchy is set to “ Each attribute value is generalized based on the generalized node (1, 1) set to “1”.

  That is, in the example shown in FIG. 12, the “getFrequentSets” function outputs the equivalence classes d351 to d355 to which the records of the table d10 are assigned as the set F ′.

  As described above, with reference to FIGS. 11 and 12, the attribute value of the target attribute among the records in the table d10 is generalized based on the generalization strategy specified as input and the generalization hierarchy of the attribute. An example of the processing to be performed has been described.

[4.2. (K, t)-Determination of Anonymity]
Next, an example of processing for determining whether or not a desired generalization strategy is a generalization strategy that can satisfy (k, t) -anonymity will be described with reference to FIG. FIG. 13 is an explanatory diagram for explaining an example of processing for determining whether or not a desired generalization strategy is a generalization strategy that can satisfy (k, t) -anonymity. It is the figure which presented the algorithm typically in the form of what is called a program code. In the example shown in FIG. 13, some information is abstracted for easy understanding of the processing flow, and is not necessarily shown in a format that can be compiled based on a compiler of a specific programming language.

The “kAnonymityCheck” function shown in FIG. 13 has, as inputs, a generalization strategy (that is, a generalized node) indicated by variables v = (v ₁ , v ₂ ,..., V _n ), and (k, t)-Anonymity threshold (ie, k and t), table d10 to be processed indicated by variable T, and each indicated by variable (H ₁ , H ₂ ,..., H _n ) Get information indicating the generalized hierarchy of attributes. The definitions of (v ₁ , v ₂ ,..., V _n ) and (H ₁ , H ₂ ,..., H _n ) generalize the attribute values described above with reference to FIG. This is the same as the case of the “getFrequentSets” function.

  Specifically, the “kAnonymityCheck” function shown in FIG. 13 assigns each record r of the table T acquired as an input to an equivalence class based on the generalization strategy v acquired as an input. The process of assigning each record r to the equivalence class corresponds to the “getFrequentSets” function described above with reference to FIG.

  In addition, the “kAnonymityCheck” function determines, for each equivalent class to which each record r is assigned, whether or not the number of records is greater than or equal to the threshold value k acquired as an input, and the size of the equivalent class with which the number of records is less than k (equivalent Count the original number of classes) c. The function outputs “True” when the size c of the equivalent class in which the number of recorded records is less than k is equal to or smaller than the threshold value t acquired as an input, and when it exceeds the threshold value t. Outputs "False".

  The example of the process for determining whether or not the desired generalization strategy is a generalization strategy that can satisfy (k, t) -anonymity has been described above with reference to FIG.

[4.3. Original conversion]
As described above, the reference point deriving unit 145 of the information processing apparatus 10 is based on the search result of the minimal element satisfying (k, t) -anonymity searched by the minimal element searching unit 143 from the bundle of generalization strategies. In addition, a generalized node satisfying (k, t) -anonymity is specified as a new reference point candidate. At this time, the reference point deriving unit 145 defines a bundle derived from the discrete set based on the number of classifications that generalize the attribute values of each attribute (in other words, the height of the generalization hierarchy of each attribute). A new reference point candidate is specified by transforming the element between the bundle formed by the conversion strategy and the bundle derived from the discrete set.

  Therefore, in this section, first, a bundle derived from a discrete set based on the number of classifications that generalizes the attribute values of each attribute will be described with reference to FIG. 14, and then refer to FIGS. An example of processing related to the original conversion will be described. In the following, a bundle derived from a discrete set based on the number of classifications that generalizes the attribute values of each attribute may be simply referred to as a “bundle derived from the discrete set”.

  Note that a bundle derived from a discrete set refers to a 冪 set B ([[] when a 冪 set of a finite set [n]: = {1, 2,..., N} is B ([n]). n]) corresponds to a bundle <B ([n]), ⊆> defined as a partial order relationship.

  For example, FIG. 14 is a diagram showing an example of a correspondence relationship between a bundle composed of a generalization strategy and a bundle derived from a discrete set, and shows an original correspondence relationship between each bundle. The example shown in FIG. 14 shows an example in which a bundle (see FIG. 7) composed of generalization strategies based on the attribute generalization hierarchy shown in FIGS. 5 and 6 is applied.

  In the example shown in FIG. 14, the number of classifications that generalize the attribute values of each attribute (in other words, the generalized hierarchy of each attribute, excluding the hierarchy of height “0” indicating the attribute value itself). Based on each subset of a finite set (discrete set) defined on the basis of the order, the bundle derived from the discrete set is defined by using the inclusion relation between the subsets as an order relationship. Specifically, based on each subset of a set of positive integers that maximizes the sum of the number of classifications that generalize the attribute values of each attribute, the inclusion relationship between the subsets is an order relationship. Thus, a bundle derived from a discrete set is defined.

  In the example shown in FIG. 14, among the positive integer finite sets {1, 2, 3, 4} of bundles derived from the discrete sets, the finite sets {1, 2, 3 based on the elements “1” and “2” are used. 2} represents the respective classifications (namely, generalized hierarchies) indicated by the heights “0” to “2” of the attributes indicating the age shown in FIG.

  Specifically, the classification of height “0” in the generalized hierarchy of attributes indicating age (that is, the attribute value itself) is a subset of positive integers {1, 2} in a bundle derived from a discrete set. Indicated by Further, the classification of the attribute indicating the age with the height “1” in the generalized hierarchy is represented by a positive integer subset {1} in the bundle derived from the discrete set. In addition, the classification of the attribute indicating the age at the height “2” in the generalized hierarchy is represented by a positive integer subset {} (that is, an empty set) in a bundle derived from the discrete set.

  Similarly, in the example shown in FIG. 14, among the positive integer finite sets {1, 2, 3, 4} of bundles derived from the discrete sets, the finite set {3 based on the elements “3” and “4” , 4} represents the respective classifications (namely, generalized hierarchies) indicated by the attribute heights “0” to “2” indicating the gender shown in FIG.

  Specifically, the classification of the attribute indicating gender having a height of “0” in the generalized hierarchy (that is, the attribute value itself) is a subset of positive integers {3,4} in a bundle derived from the discrete set. Indicated by In addition, the classification of the attribute indicating sex by the height “1” in the generalized hierarchy is represented by a positive integer subset {3} in a bundle derived from the discrete set. In addition, the classification of the attribute indicating gender with the height “2” in the generalized hierarchy is represented by a positive integer subset {} (that is, an empty set) in a bundle derived from the discrete set.

  That is, for each of the plurality of classifications corresponding to each attribute, the more specific the classification is, the more elements among the elements corresponding to the plurality of consecutive positive integers associated with the attribute are the values. Are associated with subsets added sequentially starting with smaller elements.

  At this time, the maximum element (2, 2) of the bundle composed of the generalization strategy is associated with the minimum {} (ie, empty set) of the bundle derived from the discrete set, and the bundle composed of the generalization strategy. Is associated with the maximum element {1, 2, 3, 4} of the bundle derived from the discrete set.

  By defining a bundle derived from a discrete set as described above, each element of the bundle consisting of the generalized hierarchy (that is, a generalized node) is associated with the element of the bundle derived from the discrete set. It is done.

  As a specific example, in the example illustrated in FIG. 14, a generalized node (0, 1) of a bundle composed of a generalization strategy is associated with a bundle element {1, 2, 3} derived from a discrete set. . Similarly, a bundle generalization node (2, 1) consisting of a generalization strategy is associated with a bundle element {3} derived from a discrete set.

  Based on the above configuration, an example of processing for converting one bundle element into another bundle element between a bundle consisting of a generalized strategy and a bundle derived from a discrete set will be described below. To do.

  First, with reference to FIGS. 14 and 15, an example of processing for converting a bundle element (that is, a generalized node) composed of a generalization strategy into a bundle element derived from a discrete set will be described. FIG. 15 is an explanatory diagram for explaining an example of a process for converting a bundle element composed of a generalization strategy into a bundle element derived from a discrete set. The algorithm of the process is expressed in a so-called program code format. It is the figure shown typically. Note that the example shown in FIG. 15 abstracts a part of information for easy understanding of the flow of processing, and is not necessarily shown in a format that can be compiled based on a compiler of a specific programming language.

The “set” function shown in FIG. 15 has, as inputs, a generalized node indicated by variables v = (v ₁ , v ₂ ,..., V _n ), and (h ₁ , h ₂ ,. , H _n ), the information indicating the maximum value of the generalized hierarchy height of each attribute is acquired. The definition of (v ₁ , v ₂ ,..., V _n ) is the same as that of the “getFrequentSets” function for generalizing attribute values described above with reference to FIG. Each of (h ₁ , h ₂ ,..., H _n ) corresponds to a different attribute and indicates the maximum height of the generalized hierarchy of each attribute. That is, h _i indicates the maximum value of the generalized hierarchy of the i-th attribute.

  The “set” function shown in FIG. 15 is based on the correspondence between the bundle element composed of the generalized strategy shown in FIG. 14 and the bundle element derived from the discrete set, and the minimum element of the bundle composed of the generalized strategy ( When 0,0) is input, the maximum element {1, 2, 3, 4} of bundles derived from the discrete set is output. Similarly, this function outputs the minimum {} of bundles derived from a discrete set when the maximum element (2, 2) of bundles composed of generalization strategies is input.

  Further, attention is paid to a case where an element obtained by adding an element corresponding to at least one of the attributes to the minimum element of a bundle composed of generalization strategies is used as an input of the “set” function. In this case, from the set corresponding to the largest element of the bundle derived from the discrete set, the same function is the element with the larger value among the elements corresponding to the attribute added with the value in the generalized node. The element corresponding to the subset deleted by the addition is output.

  As a specific example, the element corresponding to the attribute indicating sex is added to the minimum element (0, 0) of the bundle consisting of the generalization strategy (that is, the attribute is generalized only by one level). Focus on the generalized node (0, 1). In this case, in the set {1, 2, 3, 4} corresponding to the maximum element of the bundle derived from the discrete set, the elements “3” and “4” correspond to the attribute indicating gender. Yes. Therefore, the “set” function is a subset {1, 2, 3} obtained by deleting only one larger element from the elements “3” and “4” from the set {1, 2, 3, 4}. Is output as an element corresponding to the generalized node (0, 1).

  As another example, the element corresponding to the attribute indicating age is added to the minimum element (0, 0) of the bundle consisting of the generalization strategy (that is, the attribute is generalized by only two stages). Note the generalized node (2, 0). In this case, in the set {1, 2, 3, 4} corresponding to the maximum element of the bundle derived from the discrete set, the elements “1” and “2” correspond to the attribute indicating the age. Yes. Therefore, the “set” function corresponds to the subset {3, 4} in which only two larger elements of the elements “1” and “2” are deleted from the set {1, 2, 3, 4}. Is output as an element corresponding to the generalized node (2, 0).

As described above, the “set” function is the generalized node v acquired as an input based on the correspondence between the bundle elements formed by the generalization strategy shown in FIG. 14 and the bundle elements derived from the discrete set. Is converted into a bundle element V = {a ₁ , a ₂ ,...

  As described above, with reference to FIGS. 14 and 15, an example of processing for converting a bundle element (that is, a generalized node) including a generalization strategy into a bundle element derived from a discrete set has been described.

  Next, an example of processing for converting a bundle element derived from a discrete set into a bundle element (ie, a generalized node) composed of a generalization strategy will be described with reference to FIGS. FIGS. 16 and 17 are explanatory diagrams for explaining an example of processing for converting a bundle element derived from a discrete set into a bundle element (ie, a generalized node) including a generalization strategy. FIG. 17 is a diagram schematically showing the algorithm of the processing in a so-called program code format. Note that the example shown in FIG. 17 abstracts a part of information for easy understanding of the flow of processing, and is not necessarily shown in a format that can be compiled based on a compiler of a specific programming language.

  First, with reference to FIG. 16, an outline of processing for converting a bundle element derived from a discrete set into a bundle element (ie, a generalized node) composed of a generalization strategy will be described. As can be seen with reference to FIG. 14, all the bundle elements derived from the discrete set when the bundle elements formed by the generalization strategy and the bundle elements derived from the discrete set are associated one-to-one. On the other hand, a bundle element made up of a generalization strategy is not always associated.

  As a specific example, when a bundle element composed of a generalization strategy is converted into a bundle element derived from a discrete set by the above-described “set” function, for example, a subset { Elements corresponding to 1, 2, 4} and elements corresponding to the subset {1, 4} are not output. Therefore, even if the inverse transformation of the “set” function is performed, it is not always possible to transform all the elements of the bundle derived from the discrete set into the elements of the bundle consisting of the generalization strategy.

  In view of the above situation, the “vec” function shown in FIG. 17 converts all elements of a bundle derived from a discrete set into any element (that is, a generalized node) in a bundle composed of a generalization strategy. Provide the matching algorithm. The details of the “vec” function for converting a bundle element derived from a discrete set into a bundle element consisting of a generalization strategy (ie, a generalized node) will be described below with reference to FIG. .

The “vec” function shown in FIG. 17 has, as inputs, a bundle element derived from a discrete set indicated by a variable V = {a ₁ , a ₂ ,...}, (H ₁ , h ₂ , .., H _n ), information indicating the maximum value of the height of the generalized hierarchy of each attribute is acquired. Note that the definition of (h ₁ , h ₂ ,..., H _n ) is to convert a bundle element composed of the generalization strategy described above with reference to FIG. 15 into a bundle element derived from a discrete set. This is the same as the case of the “set” function.

  The “vec” function is a bundle derived from a discrete set that is associated with a bundle generalized node consisting of a generalization strategy by the “set” function. Map to one of the original. Specifically, in the finite set of positive integers indicated by the element acquired as input (that is, a subset of the finite set {1, 2, 3, 4}), the function is applied to the element associated with each attribute. When attention is paid to other elements that are lower in value than the element, the other elements are interpolated to correspond to other elements.

  For example, in FIG. 16, attention is paid to the elements indicated by the finite set {2, 3} among the bundle elements derived from the discrete set. As described above, in the bundle derived from the discrete set shown in FIG. 14 and FIG. 16, the attribute indicating the age is represented by a subset of the finite set {1, 2} based on the elements “1” and “2”. Classification is shown. That is, when focusing on the finite set {2, 3}, it is understood that the element associated with the attribute indicating age is “2” and the element “1” indicating a value lower than the element is missing. . In this case, the “vec” function interpolates the element “1” corresponding to the attribute indicating age with respect to the finite set {2, 3}.

  Further, in the bundle source derived from the discrete set shown in FIGS. 14 and 16, the attribute classification indicating sex is determined by the subset of the finite set {3, 4} based on the elements “3” and “4”. Indicated. That is, when focusing on the finite set {2, 3}, the element associated with the attribute indicating gender is “3”, and there is no element indicating a value lower than that element. In this case, the “vec” function does not newly supplement the element corresponding to the attribute indicating sex with respect to the finite set {2, 3}.

  As described above, in the bundle derived from the discrete set, the “vec” function replaces the element indicated by the finite set {2, 3} with the other set indicated by the finite set {1, 2, 3}. Map to the original. In the bundle derived from the discrete set, the element indicated by the finite set {1, 2, 3} is a bundle generalized node (0, 1) consisting of a generalization strategy as shown in FIGS. ). That is, the “vec” function associates the finite set {2, 3} with the finite set {1, 2, 3} by interpolating elements, so that in the bundle derived from the discrete set, the finite set {2, 3} The indicated element is transformed into a bundle of generalized nodes (0, 1) consisting of generalization strategies.

  As another example, in FIG. 16, attention is paid to elements indicated by a finite set {1, 4} among bundle elements derived from a discrete set. In this case, the element associated with the attribute indicating age is “1”, and there is no element indicating a value lower than that element. In this case, the “vec” function does not newly interpolate an element corresponding to the attribute indicating age for the finite set {1, 4}.

  Further, when focusing on the finite set {1, 4}, it is understood that the element associated with the attribute indicating gender is “4” and the element “3” indicating a value lower than the element is missing. . In this case, the “vec” function interpolates the element “3” corresponding to the attribute indicating sex with respect to the finite set {1, 4}.

  As described above, in the bundle derived from the discrete set, the “vec” function replaces the element represented by the finite set {1, 4} with the other represented by the finite set {1, 3, 4}. Map to the original. Note that in a bundle derived from a discrete set, an element represented by a finite set {1, 3, 4} is a bundle generalized node (1,0) consisting of a generalization strategy as shown in FIGS. ). In other words, the “vec” function associates the finite set {1, 4} with the finite set {1, 3, 4} by interpolating elements, so that in the bundle derived from the discrete set, the finite set {1, 4} The indicated element is transformed into a bundle of generalized nodes (1, 0) consisting of generalization strategies.

  Similarly, in a bundle derived from a discrete set, each element indicated by a finite set {1, 2, 4}, {2, 3, 4}, {2, 4} is represented by a finite set {1, 2, , 3, 4}. In the bundle derived from the discrete set, the element indicated by the finite set {1, 2, 3, 4} is a bundle generalized node (0) as shown in FIG. 14 and FIG. , 9). That is, the “vec” function generalizes each element represented by a finite set {1, 2, 4}, {2, 3, 4}, {2, 4} in a bundle derived from a discrete set. Convert to a bundle of generalized nodes (0, 0) consisting of strategies.

As described above, as shown in FIG. 16, the “vec” function uses a bundle element V = {a ₁ , a ₂ ,... Is converted into a generalized node v = (v ₁ , v ₂ ,..., V _n ).

  As described above, with reference to FIGS. 16 and 17, an example of processing for converting a bundle element derived from a discrete set into a bundle element (that is, a generalized node) including a generalization strategy has been described.

[4.4. Search for local minimum]
Next, referring to FIG. 18 and FIG. 19, the local minimum search unit 143 of the analysis unit 14 described above satisfies the minimum satisfying (k, t) -anonymity from each generalized node in the bundle composed of the generalization strategy. An example of a process for searching for an element will be described. 18 and 19 are explanatory diagrams for explaining an example of processing for searching for a minimal element satisfying (k, t) -anonymity from each generalized node in a bundle composed of generalization strategies.

  First, referring to FIG. 18, an “AMSS (A Most Specific Sentences)” function for searching for a minimal element satisfying (k, t) −anonymity from each generalized node in a bundle composed of generalization strategies. The flow of processing will be described. FIG. 18 is a diagram schematically showing the algorithm of the processing in a so-called program code format. In the example shown in FIG. 18, some information is abstracted for easy understanding of the processing flow, and is not necessarily shown in a format that can be compiled based on a compiler of a specific programming language.

The “AMSS” function shown in FIG. 18 has a generalized node satisfying (k, t) -anonymity represented by variables v = (v ₁ , v ₂ ,..., V _n ) as inputs, A table d10 to be processed indicated by the variable T and information indicating the generalized hierarchy of each attribute indicated by the variables (H ₁ , H ₂ ,..., H _n ) are acquired. The definitions of (v ₁ , v ₂ ,..., V _n ) and (H ₁ , H ₂ ,..., H _n ) generalize the attribute values described above with reference to FIG. This is the same as the case of the “getFrequentSets” function.

  As described above as the operation of the minimal element search unit 143, the “AMSS” function is at least any of the bundles (generalized nodes) satisfying (k, t) -anonymity in the bundle composed of generalized strategies. A minimal element that satisfies (k, t) -anonymity is searched for in a direction to further embody such an element.

  Specifically, the “AMSS” function is a criterion for searching for a generalized node v that satisfies (k, t) -anonymity specified as an input, and a minimal element that satisfies (k, t) -anonymity. Set as a point. Then, the function is shifted in a direction to make one of the elements more specific among the original elements (that is, the height of the generalized hierarchy) confirmed to satisfy (k, t) -anonymity. And determine whether or not the element after the shift satisfies (k, t) -anonymity. For the determination of (k, t) -anonymity, the “kAnonymityCheck” function described above with reference to FIG. 13 may be used.

  Then, when the element after the shift satisfies (k, t) -anonymity, the “AMSS” function shifts any element in a direction to further embody, and the element after the shift becomes (k, t )-If anonymity is not satisfied, shift any element in the direction of generalization (abstraction). As described above, the same function sequentially shifts any element and sequentially determines whether the element after the shift satisfies (k, t) -anonymity. )-Search for a minimal element that satisfies anonymity.

  In the example shown in FIG. 18, the “AMSS” function uses a so-called binary search method for searching for a minimal element satisfying (k, t) -anonymity.

  Here, referring to FIG. 19, based on the “AMSS” function shown in FIG. 18, the minimum element search unit 143 specifically describes the process related to the search for the minimum element satisfying (k, t) -anonymity. A specific example will be described. In the example shown in FIG. 19, a bundle (see FIG. 7) composed of generalization strategies based on the attribute generalization hierarchy shown in FIGS. 5 and 6 is applied, and the maximum element (2, 2) is used as a reference point. An example is shown. Note that a boundary d50 shown in FIG. 19 indicates an original boundary that satisfies (k, t) -anonymity and an original boundary that does not satisfy (k, t) -anonymity, and the maximum element side ( That is, each element on the lower side of the drawing corresponds to an element satisfying (k, t) -anonymity. Of course, it goes without saying that each element on the minimum element side (that is, the upper side of the drawing) from the boundary d50 corresponds to an element that does not satisfy (k, t) -anonymity.

  In the example illustrated in FIG. 19, the local minimum search unit 143 first shifts the element corresponding to the age attribute to a more specific direction (that is, a direction of lowering the height of the generalization strategy). In other words, the local minimum search unit 143 shifts the element corresponding to the age attribute from the generalized node (2, 2) to a more specific direction (k, t) of the generalized node (1, 2). -Determine anonymity. Here, it is assumed that the generalized node (1, 2) satisfies (k, t) -anonymity.

  Since the generalized node (1, 2) satisfies (k, t) -anonymity, the local minimum search unit 143 more specificizes the element corresponding to the age attribute from the generalized node (1, 2). The (k, t) -anonymity of the generalized node (0, 2) shifted in the direction to be determined is determined. Here, it is assumed that the generalized node (0, 2) does not satisfy (k, t) -anonymity.

  Since the generalized node (0, 2) does not satisfy (k, t) -anonymity, the local minimum search unit 143 more specifically identifies the element corresponding to the gender attribute from the generalized node (1, 2). The (k, t) -anonymity of the generalized node (1, 1) shifted in the direction to be converted is determined. Here, it is assumed that the generalized node (1, 1) satisfies (k, t) -anonymity.

  Since the generalized node (1, 1) satisfies (k, t) -anonymity, the local minimum search unit 143 more specificizes the element corresponding to the gender attribute from the generalized node (1, 1). The (k, t) -anonymity of the generalized node (1, 0) shifted in the direction to be determined is determined. Here, it is assumed that the generalized node (1, 0) does not satisfy (k, t) -anonymity.

  Note that it is already determined that the generalized node (0, 1) does not satisfy (k, t) -anonymity based on the determination result of the generalized node (0, 2). This is because the generalized node (0, 1) corresponds to a generalized node further embodying elements corresponding to the age attribute among the generalized nodes (0, 2). Specifically, the generalized node that does not satisfy (k, t) -anonymity, and another generalized node that is further specified does not satisfy (k, t) -anonymity. For this reason, when it is determined that the generalized node (0, 2) does not satisfy (k, t) -anonymity, the generalized node (0, 2) that further specifies the generalized node (0, 2). 1) does not satisfy (k, t) -anonymity with the determination result of the generalized node (0, 2).

  Here, when a is a generalized node (1, 1), generalized nodes b having a> b relationship are (0, 1) and (1, 0). At this time, when the process of determining (k, t) -anonymity is a query function q, a is a minimal element, q (a) = 1, and any a> b∈ Q (b) = 0 holds for L. As for the generalized node (0, 1), q (a) = 0 based on the determination result of the generalized node (0, 2) as described above without actually calculating q (a). It is self-evident. Therefore, the minimal element search unit 143 determines the generalized node (1, 1) as the minimal element, and outputs the generalized node (1, 1).

  As described above, with reference to FIG. 18 and FIG. 19, an example of processing in which the minimal element search unit 143 searches for a minimal element satisfying (k, t) -anonymity from each generalized node in a bundle composed of generalization strategies. Explained.

[4.5. Flow of a series of processing]
Next, referring to FIG. 20 and FIG. 21, the analysis unit 14 described above searches for a minimum element satisfying (k, t) -anonymity from a bundle of generalization strategies, and a series of searched minimums An example of a process for outputting a generalization strategy corresponding to each element will be described. 20 and 21 are explanatory diagrams for explaining an example of a flow of a series of processes of the analysis unit 14.

  FIG. 20 is a diagram schematically showing an algorithm of an “All-MSS (All Most Specific Sentences)” function showing an example of a series of processes of the analysis unit 14 in a so-called program code format. Note that the example shown in FIG. 20 abstracts a part of information for easy understanding of the processing flow, and is not necessarily shown in a format that can be compiled based on a compiler of a specific programming language.

The “All-MSS” function shown in FIG. 20 has (k, t) -anonymity thresholds (that is, k and t) as input, a table d10 to be processed indicated by a variable T, and a variable Information indicating the generalized hierarchy of each attribute indicated by (H ₁ , H ₂ ,..., H _n ) is acquired. The definition of (H ₁ , H ₂ ,..., H _n ) is the same as that of the “getFrequentSets” function for generalizing attribute values described above with reference to FIG.

  FIG. 21 is a flowchart showing a flow of a series of processes of the “All-MSS” function shown in FIG. Hereinafter, with reference to FIG. 21, an example of a flow of a series of processes of the “All-MSS” function, that is, an example of a series of processes of the analysis unit 14 will be described. In this description, it is assumed that a bundle (see FIG. 7) composed of generalization strategies based on the attribute generalization hierarchy shown in FIGS. 5 and 6 is applied. In this case, it is assumed that each generalized node of the bundle composed of the generalization strategy is associated with the element of the bundle derived from the discrete set shown in FIGS. 14 and 16.

(Step S101)
The analysis unit 14 acquires information on the table d10 (that is, T) to be processed from the DB information acquisition unit 11. Further, the analysis unit 14 receives information indicating an attribute that is a target of generalization (abstraction) of the attribute value from among the attributes of the table d10 to be processed from the hierarchy information acquisition unit 13, and general information of each of the attributes. Information indicating the categorization hierarchy (that is, (H ₁ , H ₂ ,..., H _n )) is acquired. Further, the analysis unit 14 acquires (k, t) -anonymity thresholds (that is, k and t) as information indicating anonymity conditions from the hierarchy information acquisition unit 13.

  The analysis data generation unit 141 extracts a combination of heights of the generalized hierarchies of each attribute based on the information indicating the generalized hierarchies of the attributes to be generalized (abstracted) of the attribute values. Specify the combination as a generalization strategy.

  Then, the analysis data generation unit 141 is based on each predetermined generalization strategy, and the order relation (in other words, the generalization hierarchy of each attribute that each generalization strategy has as an element is more generalized (in other words, abstracted). And a bundle of generalization strategies based on an order relation that abstracts the classification of each attribute.

(Step S103)
First, the minimal element search unit 143 obtains a minimal element v satisfying (k, t) -anonymity based on the “AMSS” function with the maximum element of a bundle composed of generalized strategies as a reference point. Specifically, as described above with reference to FIG. 19, the minimal element search unit 143 uses (k, t) -anonymity when the maximum element (2, 2) of the bundle composed of the generalization strategy is used as a reference point. The minimal element v = (1, 1) satisfying the property is acquired. The minimal element searching unit 143 notifies the reference point deriving unit 145 of the acquired minimal element v = (1, 1) as a minimum element search result that satisfies (k, t) -anonymity.

(Step S105)
The reference point deriving unit 145 acquires the minimal element v = (1, 1) as the minimal element search result satisfying (k, t) -anonymity from the minimal element searching unit 143. The reference point deriving unit 145 specifies the bundle element V derived from the discrete set corresponding to the minimal element v based on the “set” function based on the acquired minimal element v.

  For example, FIG. 22 is an explanatory diagram for explaining an example of the processing of the reference point deriving unit 145, and the reference point deriving unit 145 starts from the discrete set corresponding to the acquired minimal element v = (1, 1). The process which specifies the origin of the induced | guided | derived bundle is typically shown. In FIG. 22, reference numeral d52 indicates the boundary d50 shown in the bundle made up of the generalization strategy on the bundle side derived from the discrete set. That is, when each element on the minimum element side (that is, the lower side of the drawing) from the boundary d52 is converted into a generalized node of a bundle composed of the generalized strategy, the generalized node is (k, t) -anonymity. Will be satisfied. Further, when each element on the maximum element side (that is, the upper side of the drawing) from the boundary d52 is converted into a generalized node of a bundle composed of a generalization strategy, the generalized node has (k, t) -anonymity. It will not satisfy.

  That is, the reference point deriving unit 145 specifies V = {1, 3} as the bundle element V derived from the discrete set corresponding to the acquired minimal element v = (1, 1).

  Next, the reference point deriving unit 145 derives a complement of the bundle element V = {1, 3} derived from the identified discrete set, and substitutes the derived complement into the set indicated by the variable C. . For example, FIG. 23 is an explanatory diagram for explaining an example of processing of the reference point deriving unit 145. In the example shown in FIG. 23, the reference point deriving unit 145 derives an element {2, 4} corresponding to a complement of the bundle element V = {1, 3} derived from the discrete set, and derives the derived element { 2,4} is substituted into set C.

(Step S107)
Next, the reference point deriving unit 145 initializes the set indicated by the variable D with an empty set. Note that the set D is a set for holding elements of bundles derived from the discrete sets that have already been processed, and the process is performed again on the elements. It is provided to prevent this.

(Step S109)
The reference point deriving unit 145 inputs the derived complement C to the function Tr that extracts a subset corresponding to the minimum crossing from the set of positive integers indicated by the bundle elements derived from the discrete set. Then, the reference point deriving unit 145 acquires a subset Tr (C) corresponding to the minimal crossing of the complement C as an output of the function Tr, and is included in the set D among the elements of the subset Tr (C). The bundle element derived from the discrete set corresponding to the non-element is extracted as the element indicated by the variable X.

  As a specific example, as shown in FIG. 23, the reference point deriving unit 145 uses Tr (C) as a subset Tr (C) corresponding to the minimal crossing of the element {2, 4} of the bundle derived from the discrete set. C) = {{2}, {4}} is acquired.

  The function Tr corresponds to a process known as a so-called hypergraph dualization algorithm for calculating a hypergraph dual with the input set (for example, the complementary set C) as a hyper edge. Therefore, the processing content of the function Tr is not particularly limited as long as the processing is based on the hypergraph dualization algorithm. Further, the processing contents of the function Tr are not particularly limited as long as it is possible to extract a subset corresponding to the minimum crossing from the set of input positive integers, not limited to the processing based on the hypergraph dualization algorithm. It goes without saying that it is not done.

(Step S111)
When there is a bundle element X derived from the discrete set (step S109, YES), the reference point deriving unit 145 is based on the “vec” function and includes a bundle composed of generalization strategies corresponding to the element X. Identifies a generalized node v.

  For example, FIG. 24 is an explanatory diagram for explaining an example of processing of the reference point deriving unit 145. In the example shown in FIG. 24, the reference point deriving unit 145 uses a “vec” function to generate a bundle consisting of a corresponding generalized strategy for each of the elements {2} and {4} of the bundle derived from the discrete set. A generalized node v is specified. Specifically, the reference point deriving unit 145 identifies the generalized node v = (0, 2) as the generalized node corresponding to the bundle element {2} derived from the discrete set. Similarly, the reference point deriving unit 145 identifies the generalized node v = (2, 0) as the generalized node corresponding to the bundle element {4} derived from the discrete set.

(Step S113)
Then, the reference point deriving unit 145 determines whether or not the identified generalized node v satisfies (k, t) -anonymity. Note that the above-described “kAnonymityCheck” function may be applied to determine whether or not (k, t) −anonymity is satisfied.

(Step S119)
When the identified generalized node v does not satisfy (k, t) -anonymity (NO in step S113), the reference point deriving unit 145 derives from the discrete set that is the identification source of the generalized node v. The bundle element X (ie, the element X input to the “vec” function) is added to the set D. For example, in the example shown in FIG. 24, the generalized node v = (0, 2) corresponding to the bundle element {2} derived from the discrete set does not satisfy (k, t) -anonymity. Therefore, the reference point deriving unit 145 adds the bundle element X = {2} derived from the discrete set, which is the identification element of the generalized node v = (0, 2), to the set D.

(Step S115)
On the other hand, when the specified generalized node v satisfies (k, t) -anonymity (step S113, YES), the reference point deriving unit 145 sets the generalized node v as a new reference point. The candidate is output to the local minimum search unit 143 as a candidate. For example, in the example shown in FIG. 24, the generalized node v = (2, 0) corresponding to the bundle element {4} derived from the discrete set satisfies (k, t) -anonymity. Therefore, the reference point deriving unit 145 outputs the generalized node v = (2, 0) as a new reference point candidate to the local minimum search unit 143.

  Upon receiving the output of the new reference point candidate, the local minimum element search unit 143 searches the local minimum element w that satisfies (k, t) -anonymity with the candidate as a reference point. Then, the minimal element search unit 143 notifies the reference point derivation unit 145 of the searched minimal element w as a minimal element search result that satisfies (k, t) -anonymity.

(Step S117)
The reference point deriving unit 145 identifies the bundle element V derived from the discrete set corresponding to the acquired minimal element w, and adds the complement of the identified element V to the set C.

(Step S109)
Then, the minimal element search unit 143 and the reference point deriving unit 145 perform the series of processing shown in steps S111 to S117 for discrete elements corresponding to elements not included in the set D among the elements of the subset Tr (C). The process continues as long as there is a bundle element X derived from the set (YES in step S109).

  For example, FIG. 25 is an explanatory diagram for explaining an example of processing of the minimal element search unit 143. The minimal element search unit 143 uses the generalized node v = (2, 0) as a new reference point ( k, t) —shows a case where a minimal element satisfying anonymity is searched. In the example shown in FIG. 25, the generalized node v = (2, 0) itself corresponds to a minimal element that satisfies (k, t) -anonymity.

  When there is no bundle element X derived from the discrete set (step S109, NO), the minimal element search unit 143 determines each of the minimal elements satisfying the searched series of (k, t) -anonymity. Is output to the analysis result output unit 15.

  For example, FIG. 26 is an explanatory diagram for explaining an example of the processing result of the local minimum search unit 143, and is a bundle of generalization strategies based on the generalization hierarchy of attributes shown in FIGS. 5 and 6 (FIG. 7). An example of a local minimum satisfying (k, t) -anonymity searched from (see) is shown. In other words, in the example illustrated in FIG. 26, the generalized nodes (1, 1) and (2, 0) correspond to local minimums that satisfy (k, t) -anonymity. Therefore, the minimal element search unit 143 outputs the generalization strategy corresponding to the generalized nodes (1, 1) and (2, 0) to the analysis result output unit 15.

  The analysis result output unit 15 acquires a generalization strategy corresponding to each of a series of minimum elements searched by the minimum element search unit 143 from the minimum element search unit 143. The analysis result output unit 15 then generalizes (abstracts) the table d10 so that the acquired series of generalization strategies satisfy (k, t) -anonymity (ie, generalization strategy). To the administrator via the administrator terminal 30 as candidates. Note that the conditions presented at this time, that is, the table d10 is generalized so that the generalization strategy corresponding to each of the searched series of minimal elements satisfies the previously specified (k, t) -anonymity, and This corresponds to a generalization strategy that can minimize the decrease in the amount of information.

  As shown in step S109, the analysis unit 14 repeatedly calculates a process of calculating a hypergraph dual with the complement C as a hyper edge. Therefore, as the same processing, an algorithm that can sequentially execute hypergraph dualization, that is, an algorithm that does not require recalculation for a hypergraph that has already been calculated for a dual even if a new hyper edge is added. May be applied. By applying such an algorithm, the analysis unit 14 can further reduce the amount of calculation related to the search for the minimal element that satisfies (k, t) -anonymity.

  As described above, with reference to FIGS. 20 and 21, the analysis unit 14 described above searches for a minimum element satisfying (k, t) -anonymity from a bundle of generalization strategies, and a series of searched minimum elements An example of the process of outputting the generalization strategy corresponding to each has been described.

<5. Calculation amount>
Next, with reference to FIG. 27, the information processing apparatus 10 according to the present embodiment performs the search when searching for a minimal element satisfying (k, t) -anonymity from a bundle of generalization strategies. The calculation amount of such processing will be described. FIG. 27 shows the calculation amount of processing related to the search when the information processing apparatus 10 according to the present embodiment searches for a minimal element satisfying (k, t) -anonymity from a bundle of generalization strategies. It is explanatory drawing for demonstrating. In this description, a query for determining whether or not (k, t) -anonymity is satisfied is the amount of calculation when the information processing apparatus 10 searches for a minimal element that satisfies (k, t) -anonymity. The number of executions of the function q (that is, the “kAnonymityCheck” function) will be described. FIG. 27 shows, as an example, a bundle of generalization strategies based on the generalization hierarchy of attributes indicating “age” and “gender” shown in FIGS. 5 and 6.

  First, as terms for explaining the amount of calculation when the information processing apparatus 10 searches for a minimal element satisfying (k, t) -anonymity from a bundle of generalization strategies, “input size”, “ The definitions of “output size”, “border”, and “bundle width” will be described.

(Input size)
The “input size” corresponds to the expression length of the generalization strategy. Size Ri inputs, the number m of attributes to be generalized, based on the number m _i of the hierarchy in general hierarchy of each attribute is defined based on the following equation (1).

For example, the generalized hierarchy of the attribute indicating “age” shown in FIG. 5 has three hierarchies with heights 0, 1, and 2, and the number of hierarchies m _i = 3. Similarly, the generalized hierarchies of the attribute indicating “sex” shown in FIG. 6 have three hierarchies of height 0, 1, and 2, and the number of hierarchies m _i = 3. Therefore, the number of generalization strategies for generalizing attribute values of attributes indicating “age” and “gender” is (0, 0), (0, 1),. There are nine (1,2,) and (2,2). Therefore, in the example shown in FIG. 27, the input size Ri = log9.

(Output size)
The “size of output” corresponds to the number of generalization strategies output by the information processing apparatus 10, that is, corresponds to the number of minimal elements satisfying (k, t) -anonymity searched by the information processing apparatus 10 To do.

  In the example shown in FIG. 27, when the boundary d50 is an original boundary that satisfies (k, t) -anonymity and an original boundary that does not satisfy (k, t) -anonymity, (k, t) -anonymity There are two minimal elements satisfying the characteristics, generalized nodes (1, 1) and (2, 0). That is, in the example shown in FIG. 27, the output size is “2”.

(border)
The “border” corresponds to a set of generalized strategies corresponding to the boundaries on the bundle, and is divided into a “positive border” and a “negative border”.

  The “positive border” corresponds to a set of minimal generalization strategies satisfying (k, t) -anonymity (that is, (k, t) -minimum elements satisfying anonymity). In the example shown in FIG. 27, a set of generalized nodes (1, 1) and (2, 0) corresponds to a positive border. That is, the size of the main border and the output size are the same.

  A “negative border” corresponds to a set of maximal generalization strategies that do not satisfy (k, t) -anonymity. In the example shown in FIG. 27, a set of generalized nodes (0, 2) and (1, 0) corresponds to a negative border.

(Bundle width)
The “bundle width” corresponds to the number of destinations having the largest “destination” among the sources on the bundle. Here, the generalized node B is the “destination” of the generalized node A. In the order relation, A> B and there is no generalized node C that satisfies A>C> B. means. Here, “>” is used as a symbol indicating a relationship between nodes, but this symbol indicates an order relationship between nodes, not a symbol indicating a magnitude relationship between numerical values, so-called “succeed”. It corresponds to the symbol called. In the following description, when “>”, “<”, “≧”, and “≦” are used as symbols indicating the relationship between the nodes, these symbols indicate the magnitude relationship between the numerical values. It is assumed that the order relationship between the nodes is shown instead of the symbol.

  Specifically, in the example shown in FIG. 27, the destinations of the generalized nodes (1, 2) are the generalized nodes (0, 2) and (1, 1), and the number of the destinations is two. In the example shown in FIG. 27, there is no generalized node having more than two destinations. Therefore, in the example shown in FIG. 27, the width of the bundle is “2”.

(Calculation amount)
Based on the above, when the output size is N, the side width is w, and the negative border size is B ⁻ , the information processing apparatus 10 searches for a minimal element that satisfies (k, t) -anonymity. The calculation amount Q in this case is expressed by the following (Formula 2). The output size N depends on the input size and the data to be generalized.

  Here, a generalized strategy that satisfies (k, t) -anonymity and can minimize a decrease in the amount of information, that is, a series of minimal elements that satisfy (k, t) -anonymity. The specified process corresponds to a so-called enumeration problem. Conventional algorithms for solving such enumeration problems generally correspond to heuristic algorithms, and it has been difficult to calculate the amount of calculation in advance.

  In contrast, the information processing apparatus 10 according to the present embodiment uses the hypergraph dualization algorithm to enumerate search sources (that is, (k, t) -minimum elements satisfying anonymity). Yes. Some of these hypergraph dualization algorithms have a logical upper limit. Therefore, the information processing apparatus 10 according to the present embodiment specifies (enumerates) a generalization strategy that satisfies (k, t) -anonymity and can minimize a decrease in the amount of information. It is possible to calculate the calculation amount in advance.

  Further, according to the algorithm described as the processing of the information processing apparatus 10 according to the present embodiment, does (k, t) -anonymity necessarily satisfy all generalization strategies (ie, generalized nodes)? There is no need to determine whether or not. As a specific example, in the example described with reference to FIGS. 20 to 26, it is determined whether or not (k, t) -anonymity is satisfied for the generalized node (2, 1). However, the minimum elements (1, 1) and (2, 0) satisfying (k, t) -anonymity are specified. As described above, according to the algorithm described as the processing of the information processing apparatus 10 according to the present embodiment, a series of minimal elements satisfying (k, t) -anonymity is efficiently searched from a bundle of generalization strategies. (Enumeration) and the processing load related to the search can be reduced.

  As described above, with reference to FIG. 27, the information processing apparatus 10 according to the present embodiment relates to the search when searching for a minimal element satisfying (k, t) -anonymity from a bundle of generalization strategies. The calculation amount of processing has been described.

<6. Modification>
Next, a modified example of the information processing system 1 according to the present embodiment will be described.

[6.1. Modification 1: Reduction of processing load related to search for generalization strategy]
First, as Modification 1, with reference to FIG. 28 and FIG. 29, the analysis unit 14 of the information processing apparatus 10 searches for a series of minimal elements satisfying (k, t) -anonymity from a bundle of generalization strategies. Another example of the processing to be performed will be described. 28 and 29 are explanatory diagrams for describing an example of a flow of a series of processes of the analysis unit 14 according to the first modification.

  FIG. 28 is a diagram schematically showing an algorithm of the “All-MSS” function showing an example of a series of processes of the analysis unit 14 according to the first modification in a so-called program code format. In the example shown in FIG. 28, some information is abstracted for easy understanding of the processing flow, and is not necessarily shown in a format that can be compiled based on a compiler of a specific programming language. FIG. 29 is a flowchart showing a flow of a series of processes of the “All-MSS” function shown in FIG.

  In addition, the analysis part 14 which concerns on the modification 1 changes (k, t) -anonymity by changing a part of process of the analysis part 14 which concerns on embodiment mentioned above with reference to FIG.20 and FIG.21. The amount of processing for searching for a series of minimal elements to be satisfied is reduced.

  Specifically, when it is determined that the generalized node does not satisfy (k, t) -anonymity, the analysis unit 14 according to the first modification generally does not satisfy this (k, t) -anonymity. Add a node to set E. From the generalized node that does not satisfy this (k, t) -anonymity, even if any element is shifted in a more specific direction, the generalized node after the shift has (k, t) -anonymity. Do not meet. Therefore, when the analysis unit 14 according to Modification 1 identifies a new reference point candidate for searching for a minimal element satisfying (k, t) -anonymity, the analysis unit 14 compares the candidate with the set E. Thus, the generalized nodes included in the set E are previously removed from the identified new reference point candidates. With such a configuration, the analysis unit 14 according to Modification 1 further reduces the number of executions of the process related to the determination of (k, t) -anonymity (that is, the “kAnonymityCheck” function illustrated in FIG. 13), (K, t) —Reduces the amount of processing for searching for a series of local minimums satisfying anonymity.

  Therefore, in the following, with reference to FIG. 29, a detailed description will be given, particularly focusing on portions different from the processing shown in FIG.

(Steps S101 to S105)
Since the process concerning step S101-S105 is the same as that of the example shown in FIG. 21, detailed description is abbreviate | omitted. That is, the minimal element search unit 143 first searches for a minimal element that satisfies (k, t) -anonymity with the maximum element of a bundle composed of generalized strategies as a reference point. Then, the reference point deriving unit 145 converts the searched minimal element into an element derived from the discrete set, and substitutes the converted original complement into the set C.

(Step S107 ′)
Next, the reference point deriving unit 145 initializes the set indicated by the variable D and the set indicated by the variable E with an empty set.

(Step S109)
The reference point deriving unit 145 inputs the derived complement C to the function Tr that extracts a subset corresponding to the minimum crossing from the set of positive integers indicated by the bundle elements derived from the discrete set. Then, the reference point deriving unit 145 acquires a subset Tr (C) corresponding to the minimal crossing of the complement C as an output of the function Tr, and is included in the set D among the elements of the subset Tr (C). The bundle element derived from the discrete set corresponding to the non-element is extracted as the element indicated by the variable X.

(Step S111)
When there is a bundle element X derived from the discrete set (step S109, YES), the reference point deriving unit 145 is based on the “vec” function and includes a bundle composed of generalization strategies corresponding to the element X. Identifies a generalized node v.

(Step S121)
Next, the reference point deriving unit 145 determines whether or not there is an element w (that is, a generalized node w) of the set E that satisfies the relationship w ≧ v based on the set E and the specified generalized node v. Determine.

(Step S123)
When there is an element w of the set E that satisfies the relationship w ≧ v (YES in step S121), the reference point deriving unit 145 is derived from the discrete set that is the identification source of the identified generalized node v. The element X of the bundle (ie, the element X input to the “vec” function) is added to the set D.

(Step S113)
If there is no element w of the set E that satisfies the relationship of w ≧ v (step S121, NO), the reference point deriving unit 145 satisfies the specified generalized node v (k, t) -anonymity? Determine whether or not. Note that the above-described “kAnonymityCheck” function may be applied to determine whether or not (k, t) −anonymity is satisfied.

(Step S115)
When the identified generalized node v satisfies (k, t) -anonymity (step S113, YES), the reference point deriving unit 145 sets the generalized node v as a new reference point candidate and uses the minimal element. The data is output to the search unit 143.
(Step S117)
Then, the reference point deriving unit 145 identifies the bundle element V derived from the discrete set corresponding to the acquired minimal element w, and adds the complement of the identified element V to the set C.

(Step S131)
On the other hand, when the specified generalized node v does not satisfy (k, t) -anonymity (step S113, NO), the reference point deriving unit 145 has the element w of the set E that satisfies the relationship of w <v. It is determined whether or not exists.

(Step S133)
When there is an element w of the set E that satisfies the relationship of w <v (step S131, YES), the reference point deriving unit 145 removes the element w from the set E and adds the specified generalized node v ( That is, E ← E \ {w} ∪ {v}).

(Step S135)
If there is no element w of the set E that satisfies the relationship w <v (step S131, NO), the reference point deriving unit 145 adds the specified generalized node v to the set E.

(Step S135)
Then, the reference point deriving unit 145 adds the element X of the bundle derived from the discrete set that is the specifying element of the specified generalized node v (that is, the element X input to the “vec” function) to the set D. .

(Step S109)
As described above, the minimal element search unit 143 and the reference point derivation unit 145 perform the series of processes shown in Steps S111 to S137 among the elements of the subset Tr (C) that are not included in the set D. As long as there is a bundle element X derived from the discrete set corresponding to (YES in step S109).

  When there is no bundle element X derived from the discrete set (step S109, NO), the minimal element search unit 143 determines each of the minimal elements satisfying the searched series of (k, t) -anonymity. Is output to the analysis result output unit 15. Subsequent processing is the same as the example shown in FIG.

  As described above, with reference to FIG. 28 and FIG. 29, the analysis unit 14 according to the modified example 1 is another process of searching for a series of minimal elements satisfying (k, t) -anonymity from a bundle of generalization strategies. An example has been described. As described above, when the analysis unit 14 according to Modification 1 identifies a new reference point candidate for searching for a minimal element that satisfies (k, t) -anonymity, By comparing with E, generalized nodes included in the set E are excluded in advance from the identified new reference point candidates. With such a configuration, the analysis unit 14 according to Modification 1 further reduces the number of executions of the process related to the determination of (k, t) -anonymity (that is, the “kAnonymityCheck” function illustrated in FIG. 13), It is possible to reduce the amount of processing for searching for a series of minimal elements satisfying (k, t) -anonymity.

[6.2. Modification 2: Example of system configuration]
Next, as a second modification, an example of a system configuration of the information processing system according to the present embodiment will be described.

  For example, FIG. 30 is an explanatory diagram for describing an example of the information processing system 1 according to the second modification. In FIG. 30, reference numeral 10 ′ corresponds to the information processing apparatus 10 (see FIG. 1) according to the above-described embodiment. That is, the example illustrated in FIG. 30 illustrates a case where the information processing apparatus 10 according to the above-described embodiment is realized as a distributed processing system 10 ′ including a plurality of information processing apparatuses 101 to 10 n.

  As described above, the information processing apparatus 10 according to the present embodiment searches for a generalization strategy candidate by analyzing the table d10 stored in the DB 50, and based on the generalization strategy designated by the administrator, the table d10. Is converted into a table d30 with improved anonymity. From such characteristics, in particular, the processing load of the information processing apparatus 10 increases as the number of attributes to be analyzed (that is, attributes to be generalized) and the number of records increase.

  Therefore, the information processing apparatus 10 (see FIG. 1) according to the above-described embodiment is configured as a distributed processing system 10 ′ as illustrated in FIG. The processing load of 10n) may be reduced. In this case, among the components of the information processing apparatus 10 shown in FIG. 10, in particular, the processing of the analysis unit 14 and the DB information conversion unit 17 may be distributed by the plurality of information processing apparatuses 101 to 10n.

  FIG. 31 is an explanatory diagram for explaining an example of the information processing system 1 according to the modified example 2. In FIG. 31, reference numeral 50 ′ denotes the DB 50 (see FIG. 1) according to the above-described embodiment. Equivalent to. That is, the example illustrated in FIG. 31 illustrates a case where the DB 50 according to the above-described embodiment is realized as a distributed DB 50 ′ configured by a plurality of DBs 501 to 50 m.

  In particular, the input / output of data to a so-called database depends on the input / output performance of hardware (for example, a server or a storage) for realizing the database, and the input / output performance may become a bottleneck. In particular, in the information processing system 1 according to the present embodiment, the data amount of the table d10 increases as the number of records in the table d10 to be processed increases. Therefore, as the number of records in the table d10 increases, the input / output performance of the hardware configuring the DB 50 becomes a bottleneck, and the time for the information processing apparatus 10 to acquire the information of the table d10 from the DB 50 may increase. .

  Therefore, the bottleneck that depends on the input / output performance of the hardware may be eliminated by configuring the DB 50 (see FIG. 1) according to the above-described embodiment as a distributed DB 50 ′ as shown in FIG. 31.

  As a specific example, each record in the table d10 may be distributed and managed in each database 501 to 50m of the distributed DB 50 '. With such a configuration, for example, when the information processing apparatus 10 acquires information of the table d10 (particularly, each record of the table d10) from the distributed DB 50 ′, the time required for acquiring the information is 1 / m at the maximum. It is also possible to shorten it.

  In the example shown in FIG. 31, the example in which the DB 50 is configured as a distributed DB has been described, but the generalized DB 40 (see FIG. 1) may be configured as a distributed DB. That is, by configuring the generalized DB 40 as a distributed DB, when the information processing apparatus 10 outputs the information of the table d30 generated based on the information of the table d10 to the generalized DB 40, the table d30 to the generalized DB 40 is displayed. It is possible to shorten the time required to output the information.

  Further, the configurations shown in FIGS. 30 and 31 may be combined. That is, the information processing apparatus 10 may be configured as a distributed processing system 10 ′, and the DB 50 may be configured as a distributed DB 50 ′. Of course, the generalized DB 40 may be configured as a distributed DB.

  The example of the system configuration of the information processing system according to the modification 2 has been described above with reference to FIGS. 30 and 31.

<7. Hardware configuration>
Next, an example of a hardware configuration of the information processing apparatus 10 according to the embodiment of the present disclosure will be described with reference to FIG. FIG. 32 is a diagram illustrating an example of a hardware configuration of the information processing apparatus 10 according to the present embodiment.

  As illustrated in FIG. 32, the information processing apparatus 10 according to the present embodiment includes a processor 901, a memory 903, a storage 905, a communication device 911, and a bus 915. The information processing apparatus 10 may include an operation device 907 and a notification device 909.

  The processor 901 may be, for example, a CPU (Central Processing Unit), a GPU (Graphics Processing Unit), a DSP (Digital Signal Processor), or a SoC (System on Chip), and executes various processes of the information processing apparatus 10. The processor 901 can be configured by, for example, an electronic circuit for executing various arithmetic processes. The analysis unit 14 and the DB information conversion unit 17 described above can be realized by the processor 901.

  The memory 903 includes a RAM (Random Access Memory) and a ROM (Read Only Memory), and stores programs and data executed by the processor 901. The storage 905 can include a storage medium such as a semiconductor memory or a hard disk.

  The operation device 907 has a function of generating an input signal for a user to perform a desired operation. The operation device 907 may include an input unit for inputting information such as buttons and switches, and an input control circuit that generates an input signal based on an input by the user and supplies the input signal to the processor 901.

  The notification device 909 is an example of an output device, and may be a device such as a liquid crystal display (LCD) device or an organic light emitting diode (OLED) display, for example. In this case, the notification device 909 can notify the user of predetermined information by displaying the screen.

  As another example, the notification device 909 may be a device that notifies the user of predetermined information using a lighting or blinking pattern, such as an LED (Light Emitting Diode). Further, the notification device 909 may be a device that notifies a user of predetermined information by outputting a predetermined acoustic signal, such as a speaker.

  The communication device 911 is a communication unit included in the information processing apparatus 10 according to the embodiment of the present disclosure, and communicates with an external device via a network. The communication device 911 is a wired or wireless communication interface. In the case where the communication device 911 is configured as a wireless communication interface, the communication device 911 may include a communication antenna, an RF (Radio Frequency) circuit, a baseband processor, and the like.

  The communication device 911 has a function of performing various kinds of signal processing on a signal received from an external device, and can supply a digital signal generated from the received analog signal to the processor 901.

  The bus 915 connects the processor 901, the memory 903, the storage 905, the operation device 907, the notification device 909, and the communication device 911 to each other. The bus 915 may include a plurality of types of buses.

  In addition, it is possible to create a program for causing hardware such as a processor, a memory, and a storage built in a computer to exhibit functions equivalent to the configuration of the information processing apparatus 10 described above. A computer-readable storage medium that records the program can also be provided.

<8. Summary>
As described above, the information processing apparatus 10 according to the present embodiment classifies the attribute values of the attribute so as to be generalized step by step for each attribute to be processed in the table d10 to be processed. The generalized hierarchy of the attribute is acquired based on the plurality of classifications. Then, the information processing apparatus 10 performs a generalization strategy based on an order relation that generalizes (abstracts) the classification based on a combination of classifications between the attributes (that is, a combination of generalized hierarchy heights). A bundle consisting of

  The information processing apparatus 10 uses the element satisfying (k, t) -anonymity as a reference point in the bundle of the predetermined generalization strategies, and more specifically embodies any element of the original elements. By shifting in the direction, a local minimum satisfying (k, t) -anonymity is searched.

  When searching for a minimal element that satisfies (k, t) -anonymity, the information processing apparatus 10 derives a new reference point based on the searched minimal element. Specifically, the information processing apparatus 10 converts the specified minimal element into a bundle element derived from a discrete set, obtains a minimal crossing from the transformed original complement, and corresponds to the minimal crossing in general. Among the bundle elements composed of the conversion strategies, an element satisfying (k, t) -anonymity is set as a new reference point candidate.

  Then, the information processing apparatus 10 performs processing related to searching for a minimal element satisfying (k, t) -anonymity based on a new reference point, and processing related to derivation of a new reference point based on the search result. , And so on until no new reference point candidates are derived. As described above, the information processing apparatus 10 searches for a series of minimum elements satisfying (k, t) -anonymity, and outputs a generalization strategy corresponding to each of the searched series of minimum elements. It should be noted that the generalization strategy corresponding to each searched series of minimal elements can generalize the table d10 so as to satisfy (k, t) -anonymity, and minimize the reduction in the amount of information. Equivalent to a generalized strategy.

  It should be noted that (k, t) -generalization strategy that satisfies anonymity and can minimize the decrease in the amount of information, that is, identifies a series of minimal elements that satisfy (k, t) -anonymity. This processing corresponds to a so-called enumeration problem. Conventional algorithms for solving such enumeration problems generally correspond to heuristic algorithms, and it has been difficult to calculate the amount of calculation in advance.

  In contrast, the information processing apparatus 10 according to the present embodiment uses the hypergraph dualization algorithm to enumerate search sources (that is, (k, t) -minimum elements satisfying anonymity). Yes. Some of these hypergraph dualization algorithms have a logical upper limit. Therefore, the information processing apparatus 10 according to the present embodiment specifies (enumerates) a generalization strategy that satisfies (k, t) -anonymity and can minimize a decrease in the amount of information. It is possible to calculate the calculation amount in advance.

  Further, according to the information processing apparatus 10 according to the present embodiment, it is not necessarily determined whether (k, t) -anonymity is satisfied for all generalization strategies (that is, generalized nodes). There is no need. Therefore, according to the information processing apparatus 10 according to the present embodiment, the load of processing for searching for (listing) a series of minimal elements satisfying (k, t) -anonymity from a bundle of generalization strategies, It becomes possible to reduce.

  The preferred embodiments of the present disclosure have been described in detail above with reference to the accompanying drawings, but the technical scope of the present disclosure is not limited to such examples. It is obvious that a person having ordinary knowledge in the technical field of the present disclosure can come up with various changes or modifications within the scope of the technical idea described in the claims. Of course, it is understood that it belongs to the technical scope of the present disclosure.

  Further, the effects described in the present specification are merely illustrative or exemplary and are not limited. That is, the technology according to the present disclosure can exhibit other effects that are apparent to those skilled in the art from the description of the present specification in addition to or instead of the above effects.

The following configurations also belong to the technical scope of the present disclosure.
(1)
The processor can abstract each of the attribute values that can be taken by the target attribute by using at least two or more attributes as the target attribute among the plurality of attributes of the table including a plurality of records including the plurality of attributes. The first element of the first bundle defined based on the order relationship that makes the classification more abstract, with each combination between the two or more target attributes as a first element of a plurality of classification categories When the table is abstracted based on the classification corresponding to each, the minimum satisfying the anonymity with the first element satisfying the anonymity based on a predetermined condition between the records of the table as a reference point Performing a search process to search for the source;
Search among the second bundles in which each subset of the finite set defined based on the number of classifications for each target attribute is a second element and the inclusion relation of the second element is defined as an order relation A first element satisfying the anonymity among the first elements corresponding to each of the minimal crossings of the complementary set is identified in advance and is associated with the minimal element. Executing a reference point derivation process for deriving as a new reference point;
Including
A processor executes the search process based on the specified new reference point and the reference point derivation process based on the local minimum searched by the search process until the new reference point is not derived. An information processing method for outputting a combination of the classifications indicated by each of the searched series of minimum elements as a candidate for a condition for abstracting the table.
(2)
The anonymity corresponds to the equivalence class having a record number less than a predetermined number k among equivalence classes indicating the set of records in which the combination of the attribute values of the two or more target attributes is equal in the table. When the records to be deleted are deleted in a range of a predetermined number t or less, the number of records is equal to or more than the predetermined number k for each of the equivalence classes based on the records in the table after the records are deleted. The information processing method according to (1), on the condition that
(3)
The second bundle is an ordered relation of the inclusion relation of the second element, with the second element being a power set of a finite set of positive integers that maximizes the sum of the number of classifications for each target attribute. The information processing method according to (1) or (2), defined as:
(4)
Each of the first elements in the first bundle and each of the second elements in the second bundle correspond to a maximum element of the first bundle and a minimum element of the second bundle. And, in correspondence with the minimum element of the first bundle and the maximum element of the second bundle, it is associated in advance based on the order relationship of the first bundle and the previous second bundle, The information processing apparatus according to (3).
(5)
In the second bundle,
Each of the target attributes is associated with an element corresponding to a plurality of consecutive positive integers different from each other in each element of the finite set of positive integers,
The information according to (3) or (4), wherein each of the plurality of classifications corresponding to the target attribute is associated with a subset of a finite set based on the element corresponding to the plurality of consecutive positive integers. Processing equipment.
(6)
In the second bundle,
Each of the plurality of classifications corresponding to the target attribute has more specific elements among elements corresponding to the plurality of consecutive positive integers associated with the target attribute as the classification is more specific. The information processing apparatus according to (5), wherein the information processing apparatus is associated with a subset sequentially added from an element having a smaller value.
(7)
The first element corresponding to the minimum crossing is, for each of the target attributes, for the minimum crossing, among the elements corresponding to the plurality of consecutive positive integers associated with the target attribute. The information processing apparatus according to (6), specified based on the second element corresponding to a finite set of positive integers interpolated with other elements having a value smaller than the element included in the crossing.
(8)
The information processing according to any one of (1) to (7), wherein in the search process executed first, the minimal element is searched with the maximum element of the first bundle as the reference point. Method.
(9)
The maximum element is the first element corresponding to the combination of the classifications that most abstracts the attribute values of the two or more target attributes in the first bundle, according to (8). Information processing method.
(10)
In the search process, the minimal element is searched from the reference point toward a direction in which the classification corresponding to at least one of the two or more target attributes is more specific. The information processing method according to any one of (9).
(11)
In the search process, the minimum element is searched based on a binary search in which the classification corresponding to at least one of the two or more target attributes is directed to a more specific direction. The information processing apparatus described.
(12)
Of the first elements corresponding to each of the minimum crossings, the first element that has been searched based on the search process is excluded from the candidates for the new reference point. The information processing method according to any one of the above.
(13)
The information processing method according to any one of (1) to (12), wherein the minimal crossing is specified based on dualization of a hypergraph with the complement set as a hyperedge.
(14)
The information processing method according to any one of (1) to (13), wherein at least one of the search process and the reference point derivation process is distributed by a plurality of processors.
(15)
On the computer,
A plurality of divisions such that at least two or more attributes of a plurality of attributes of a table including a plurality of records including a plurality of attributes are set as target attributes, and attribute values that can be taken by the target attributes are abstracted in stages. Corresponding to each of the first elements of the first bundle defined on the basis of the order relation that makes the classification more abstract, with each combination of the two or more target attributes of the classification as a first element When the table is abstracted based on the classification to be performed, the minimal element satisfying the anonymity is searched with the first element satisfying the anonymity based on a predetermined condition as a reference point between the records of the table Search process to
Search among the second bundles in which each subset of the finite set defined based on the number of classifications for each target attribute is a second element and the inclusion relation of the second element is defined as an order relation A first element satisfying the anonymity among the first elements corresponding to each of the minimal crossings of the complementary set is identified in advance and is associated with the minimal element. A reference point deriving process for deriving as a new reference point;
And execute
A search is performed to execute the search process based on the specified new reference point and the reference point derivation process based on the local minimum searched by the search process until the new reference point is not derived. A program for outputting a combination of the classifications indicated by each of the series of minimum elements as a candidate for a condition for abstracting the table.
(16)
A plurality of divisions such that at least two or more attributes of a plurality of attributes of a table including a plurality of records including a plurality of attributes are set as target attributes, and attribute values that can be taken by the target attributes are abstracted in stages. Corresponding to each of the first elements of the first bundle defined on the basis of the order relation that makes the classification more abstract, with each combination of the two or more target attributes of the classification as a first element When the table is abstracted based on the classification to be performed, the minimal element satisfying the anonymity is searched with the first element satisfying the anonymity based on a predetermined condition as a reference point between the records of the table A minimal element search unit that executes search processing to perform,
Search among the second bundles in which each subset of the finite set defined based on the number of classifications for each target attribute is a second element and the inclusion relation of the second element is defined as an order relation A first element satisfying the anonymity among the first elements corresponding to each of the minimal crossings of the complementary set is identified in advance and is associated with the minimal element. A reference point derivation unit for executing a reference point derivation process for deriving a reference point as a new reference point;
The search process based on the specified new reference point and the reference point derivation process based on the local minimum searched by the search process are executed until the new reference point is not derived. An output unit that outputs a combination of the classifications indicated by each of the searched series of minimal elements as a candidate for a condition for abstracting the table;
An information processing apparatus comprising:

DESCRIPTION OF SYMBOLS 1 Information processing system 10 Information processing apparatus 11 DB information acquisition part 12 DB information output part 13 Hierarchical information acquisition part 14 Analysis part 141 Analysis data generation part 143 Minimal element search part 145 Reference point derivation part 15 Analysis result output part 16 Generalization conditions Acquisition unit 17 DB information conversion unit 18 Conversion result output unit 30 Administrator terminal 40 Generalized DB
50 DB
60 Analysis server 70 DB server 80 Client

Claims (16)

The processor can abstract each of the attribute values that can be taken by the target attribute by using at least two or more attributes as the target attribute among the plurality of attributes of the table including a plurality of records including the plurality of attributes. The first element of the first bundle defined based on the order relationship that makes the classification more abstract, with each combination between the two or more target attributes as a first element of a plurality of classification categories When the table is abstracted based on the classification corresponding to each, the minimum satisfying the anonymity with the first element satisfying the anonymity based on a predetermined condition between the records of the table as a reference point Performing a search process to search for the source;
Search among the second bundles in which each subset of the finite set defined based on the number of classifications for each target attribute is a second element and the inclusion relation of the second element is defined as an order relation A first element satisfying the anonymity among the first elements corresponding to each of the minimal crossings of the complementary set is identified in advance and is associated with the minimal element. Executing a reference point derivation process for deriving as a new reference point;
Including
A processor executes the search process based on the specified new reference point and the reference point derivation process based on the local minimum searched by the search process until the new reference point is not derived. An information processing method for outputting a combination of the classifications indicated by each of the searched series of minimum elements as a candidate for a condition for abstracting the table.   The anonymity corresponds to the equivalence class having a record number less than a predetermined number k among equivalence classes indicating the set of records in which the combination of the attribute values of the two or more target attributes is equal in the table. When the records to be deleted are deleted in a range of a predetermined number t or less, the number of records is equal to or more than the predetermined number k for each of the equivalence classes based on the records in the table after the records are deleted. The information processing method according to claim 1, wherein:   The second bundle is an ordered relation of the inclusion relation of the second element, with the second element being a power set of a finite set of positive integers that maximizes the sum of the number of classifications for each target attribute. The information processing method according to claim 1, defined as:   Each of the first elements in the first bundle and each of the second elements in the second bundle correspond to a maximum element of the first bundle and a minimum element of the second bundle. In addition, the first bundle and the previous second bundle are associated in advance so as to correspond to the minimum element of the first bundle and the maximum element of the second bundle. Item 4. The information processing device according to Item 3. In the second bundle,
Each of the target attributes is associated with an element corresponding to a plurality of consecutive positive integers different from each other in each element of the finite set of positive integers,
The information processing apparatus according to claim 3, wherein each of the plurality of classifications corresponding to the target attribute is associated with a subset of a finite set based on the element corresponding to the plurality of consecutive positive integers. In the second bundle,
Each of the plurality of classifications corresponding to the target attribute has more specific elements among elements corresponding to the plurality of consecutive positive integers associated with the target attribute as the classification is more specific. The information processing apparatus according to claim 5, wherein the information processing apparatus is associated with a subset sequentially added from an element having a smaller value.   The first element corresponding to the minimum crossing is, for each of the target attributes, for the minimum crossing, among the elements corresponding to the plurality of consecutive positive integers associated with the target attribute. The information processing apparatus according to claim 6, wherein the information is specified based on the second element corresponding to a finite set of positive integers interpolated with other elements having a value smaller than the element included in the crossing.   The information processing method according to claim 1, wherein in the search process executed first, the minimal element is searched with the maximum element of the first bundle as the reference point.   The maximum element is the first element corresponding to the combination of the classifications that most abstracts the attribute values of the two or more target attributes in the first bundle. Information processing method.   2. The minimal element is searched for in the search process from the reference point toward a direction in which the classification corresponding to at least one of the two or more target attributes is more specific. Information processing method.   11. The minimal element is searched for in the search process based on a binary search in which the classification corresponding to at least one of the two or more target attributes is directed to a more specific direction. Information processing device.   2. The information processing method according to claim 1, wherein, among the first elements corresponding to each of the minimum crossings, the first element that has already been searched based on the search process is excluded from the new reference point candidates. .   The information processing method according to claim 1, wherein the minimal crossing is specified based on dualization of a hypergraph with the complement set as a hyperedge.   The information processing method according to claim 1, wherein at least one of the search process and the reference point derivation process is distributedly processed by a plurality of processors. On the computer,
A plurality of divisions such that at least two or more attributes of a plurality of attributes of a table including a plurality of records including a plurality of attributes are set as target attributes, and attribute values that can be taken by the target attributes are abstracted in stages. Corresponding to each of the first elements of the first bundle defined on the basis of the order relation that makes the classification more abstract, with each combination of the two or more target attributes of the classification as a first element When the table is abstracted based on the classification to be performed, the minimal element satisfying the anonymity is searched with the first element satisfying the anonymity based on a predetermined condition as a reference point between the records of the table Search process to
Search among the second bundles in which each subset of the finite set defined based on the number of classifications for each target attribute is a second element and the inclusion relation of the second element is defined as an order relation A first element satisfying the anonymity among the first elements corresponding to each of the minimal crossings of the complementary set is identified in advance and is associated with the minimal element. A reference point deriving process for deriving as a new reference point;
And execute
A search is performed to execute the search process based on the specified new reference point and the reference point derivation process based on the local minimum searched by the search process until the new reference point is not derived. A program for outputting a combination of the classifications indicated by each of the series of minimum elements as a candidate for a condition for abstracting the table. A plurality of divisions such that at least two or more attributes of a plurality of attributes of a table including a plurality of records including a plurality of attributes are set as target attributes, and attribute values that can be taken by the target attributes are abstracted in stages. Corresponding to each of the first elements of the first bundle defined on the basis of the order relation that makes the classification more abstract, with each combination of the two or more target attributes of the classification as a first element When the table is abstracted based on the classification to be performed, the minimal element satisfying the anonymity is searched with the first element satisfying the anonymity based on a predetermined condition as a reference point between the records of the table A minimal element search unit that executes search processing to perform,
Search among the second bundles in which each subset of the finite set defined based on the number of classifications for each target attribute is a second element and the inclusion relation of the second element is defined as an order relation A first element satisfying the anonymity among the first elements corresponding to each of the minimal crossings of the complementary set is identified in advance and is associated with the minimal element. A reference point derivation unit for executing a reference point derivation process for deriving a reference point as a new reference point;
The search process based on the specified new reference point and the reference point derivation process based on the local minimum searched by the search process are executed until the new reference point is not derived. An output unit that outputs a combination of the classifications indicated by each of the searched series of minimal elements as a candidate for a condition for abstracting the table;
An information processing apparatus comprising:

Images