Correlation index construction device, correlation table search device, method, and program

Input means 611 receives an input of a size-specific correlation index. Index specification means 612 specifies the size-specific correlation index to be used for searching among size-specific correlation indexes based on a predetermined threshold of the number of record pairs determined to be couplable when coupling a base table including a target column and an external table. Candidate column search means 613 searches for a column whose distance to the target column is equal to or less than a distance threshold from the external table by using the specified size-specific correlation index, calculates a correlation value indicating the degree of correlation between the found column and the target column, and searches for a column whose correlation value is equal to or larger than a correlation value threshold as a candidate column.

This application is a National Stage Entry of PCT/JP2020/033309 filed on Sep. 2, 2020, the contents of all of which are incorporated herein by reference, in their entirety.

TECHNICAL FIELD

The present invention relates to a correlation table search device, a correlation table searching method, and a correlation table searching program for searching for a table including correlated data, and a correlation index construction device, a correlation index construction device method, and a correlation index construction program for constructing an index used for searching.

BACKGROUND ART

In recent years, in order to improve performance of data analysis, there is an increasing demand for creating value by linking data held by oneself with external data, open data, a data lake, and the like (hereinafter, referred to as an external table group). Such a link can be useful for artificial intelligence (AI) analysis, improvement of prediction accuracy, causal analysis, discovery of insight knowledge, and the like. For example, accuracy in sales prediction can be improved by integrating sales data of a convenience store possessed by a store and weather data.

For example, PTL 1 describes a method of coupling two tables. In the method described in PTL 1, a couplable row pair between two tables is determined, and a conversion model is generated from the determined couplable row pair. Then, a column of the first table is converted based on the generated conversion model, and the converted first table is coupled to the second table.

Note that NPL 1 describes a method of calculating correlation with standardized data.

CITATION LIST

Patent Literature

Non Patent Literature

SUMMARY OF INVENTION

Technical Problem

Meanwhile, since external data is massive and a content of data is diverse, it is difficult to quickly find data useful for a task to be analyzed by oneself from the massive external data.

Since the method described in PTL 1 is a method of coupling two tables, data included in the coupling table is not necessarily data that prompts value creation.

Therefore, an exemplary object of the present invention is to provide a correlation table search device, a correlation table searching method, and a correlation table searching program capable of quickly specifying a table including data correlated with data of a target column, and a correlation index construction device, a correlation index construction device method, and a correlation index construction program capable of constructing an index used for such searching.

Solution to Problem

A correlation table search device according to the present invention includes: input means that receives an input of a size-specific correlation index from a storage device that stores the size-specific correlation index, the size-specific correlation index being an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from an external table and being an index that is generated for each size corresponding to a predetermined number from a size-specific vector obtained by extracting, in ascending order, the predetermined number of elements of a feature vector indicating a feature of data of the column, and extracts, from the external table, a column whose distance to the size-specific vector is equal to or less than a distance threshold determined based on the correlation value threshold; index specification means that specifies a size-specific correlation index to be used for searching among the size-specific correlation indexes based on a predetermined threshold of the number of record pairs determined to be couplable when coupling a base table including a target column and the external table; candidate column search means that searches for a column whose distance to the target column is equal to or less than the distance threshold from the external table by using the specified size-specific correlation index, calculates the correlation value indicating a degree of correlation between the found column and the target column, and searches for a column whose correlation value is equal to or larger than the correlation value threshold as a candidate column; and an output unit that outputs an external table including the candidate column.

A correlation index construction device according to the present invention includes: correlation index generation means that generates, for each column of an external table, a correlation index that is an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from the external table, in which the correlation index generation means generates a feature vector indicating a feature of each column, generates a standardized vector obtained by standardizing the generated feature vector, generates a size-specific vector obtained by extracting a predetermined number of elements from elements of the generated standardized vector in ascending order, and generates a size-specific correlation index that is a correlation index for each size corresponding to the predetermined number from the generated size-specific vector, and the correlation index generation means defines a function for calculating the correlation value by using a distance to the size-specific vector, and generates a correlation index for searching for a column of the external table of which the correlation value calculated from a distance between the feature vector of a target column and the size-specific vector is equal to or larger than the correlation value threshold, by using the defined function.

A correlation table searching method according to the present invention executed by a computer includes: receiving an input of a size-specific correlation index from a storage device that stores the size-specific correlation index, the size-specific correlation index being an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from an external table and being an index that is generated for each size corresponding to a predetermined number from a size-specific vector obtained by extracting, in ascending order, the predetermined number of elements of a feature vector indicating a feature of data of the column, and extracts, from the external table, a column whose distance to the size-specific vector is equal to or less than a distance threshold determined based on the correlation value threshold; specifying a size-specific correlation index to be used for searching among the size-specific correlation indexes based on a predetermined threshold of the number of record pairs determined to be couplable when coupling a base table including a target column and the external table; searching for a column whose distance to the target column is equal to or less than the distance threshold from the external table by using the specified size-specific correlation index, calculating the correlation value indicating a degree of correlation between the found column and the target column, and searching for a column whose correlation value is equal to or larger than the correlation value threshold as a candidate column; and outputting an external table including the candidate column.

A correlation index construction device method according to the present invention executed by a computer includes: generating a feature vector indicating a feature of each column of an external table, generating a standardized vector obtained by standardizing the generated feature vector, generating a size-specific vector obtained by extracting a predetermined number of elements from elements of the generated standardized vector in ascending order, and generating a size-specific correlation index that is a correlation index for each size corresponding to the predetermined number from the generated size-specific vector, the correlation index being an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from the external table; and defining a function for calculating the correlation value by using a distance to the size-specific vector, and generating a correlation index for searching for a column of the external table of which the correlation value calculated from a distance between the feature vector of a target column and the size-specific vector is equal to or larger than the correlation value threshold, by using the defined function.

A correlation table searching program according to the present invention causes a computer to execute: input processing of receiving an input of a size-specific correlation index from a storage device that stores the size-specific correlation index, the size-specific correlation index being an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from an external table and being an index that is generated for each size corresponding to a predetermined number from a size-specific vector obtained by extracting, in ascending order, the predetermined number of elements of a feature vector indicating a feature of data of the column, and extracts, from the external table, a column whose distance to the size-specific vector is equal to or less than a distance threshold determined based on the correlation value threshold; index specification processing of specifying a size-specific correlation index to be used for searching among the size-specific correlation indexes based on a predetermined threshold of the number of record pairs determined to be couplable when coupling a base table including a target column and the external table; candidate column search processing of searching for a column whose distance to the target column is equal to or less than the distance threshold from the external table by using the specified size-specific correlation index, calculating the correlation value indicating a degree of correlation between the found column and the target column, and searching for a column whose correlation value is equal to or larger than the correlation value threshold as a candidate column; and output processing of outputting an external table including the candidate column.

A correlation index construction program according to the present invention causes a computer to execute: correlation index generation processing of generating, for each column of an external table, a correlation index that is an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from the external table, in which in the correlation index generation processing, the computer generates a feature vector indicating a feature of each column, generates a standardized vector obtained by standardizing the generated feature vector, generates a size-specific vector obtained by extracting a predetermined number of elements from elements of the generated standardized vector in ascending order, and generates a size-specific correlation index that is a correlation index for each size corresponding to the predetermined number from the generated size-specific vector, and in the correlation index generation processing, the computer defines a function for calculating the correlation value by using a distance to the size-specific vector, and generates a correlation index for searching for a column of the external table of which the correlation value calculated from a distance between the feature vector of a target column and the size-specific vector is equal to or larger than the correlation value threshold, by using the defined function.

Advantageous Effects of Invention

According to the present invention, a table including data correlated with data of a target column can be quickly specified.

DESCRIPTION OF EMBODIMENTS

First Exemplary Embodiment

First, a first exemplary embodiment of the present invention will be described. The first exemplary embodiment aims to reduce a cost for specifying a table that is couplable to a target column.FIG.1is a block diagram illustrating a configuration example of an exemplary embodiment of a coupling table specification system according to the present invention. A coupling table specification system100of the present exemplary embodiment is a system that specifies an external table (hereinafter, referred to as a coupling table) that is couplable to a table as a coupling source (that is, a base table). More specifically, the coupling table is a table including a column that is couplable to any column included in the base table.

In addition, the coupling table specification system100of the present exemplary embodiment determines whether or not a record is couplable by using a function that calculates a similarity between records (hereinafter, referred to as a similarity function). Examples of the similarity function include Jaccard similarity, an edit distance, a Euclidean distance of a character string converted based on Word2vec, and the like. Note that the similarity function used in the present exemplary embodiment is not limited to these three types of similarity functions.

Since the similarity functions as exemplified above have different viewpoints, an optimal similarity function cannot be uniquely determined. For example, a similarity between “RAMUNE” and “RAMUNE 250 ml” is calculated as 0.375 in a case of the edit distance, and is calculated as 0.5 in a case of the Jaccard similarity. Meanwhile, a similarity between “champ orange” and “champ orange” is calculated as 0.875 in a case of the edit distance, and is calculated as 0.5 in a case of the Jaccard similarity. In this way, the value of the similarity is changed according to contents of records to be compared.

For example, in the method described in NPL 1, two records are defined to be couplable in a case where the greatest similarity is greater than a threshold Tramong similarities calculated by respective similarity functions.FIG.2is an explanatory diagram illustrating an example of processing of determining a couplable table.FIG.2illustrates an example of determining whether or not an external table FT1is couplable to a base table BT1. Here, it is assumed that the threshold Trof the similarity used to determine whether or not records are couplable is 0.5 (Tr=0.5), and a threshold Tcof a record pair used to determine whether or not columns are couplable is 2 (Tc=2).

For example, it is assumed that the Jaccard similarity is calculated as 0.5, the edit distance is calculated as 0.37, and the similarity after Word2vec conversion is calculated as 0.8 for “RAMUNE” and “RAMUNE 250 ml” illustrated inFIG.2. In this case, the greatest similarity is calculated as 0.8, which is greater than the threshold Tr, and thus it is determined that the two records are couplable.

Furthermore, in the example illustrated inFIG.2, it is determined whether or not two columns of “product name” and “drink name” are couplable. Here, it is assumed that it is determined that “RAMUNE” and “RAMUNE 250 ml”, and “champ orange” and “CHAMP Orange” are couplable, and it is determined that “my cola” is not couplable to any record. In this case, the number of couplable record pairs is two, and it is thus determined that two columns are couplable since the number is equal to or larger than the threshold Tr.

However, in a case where such determination processing is simply performed for all records, a calculation amount of O (NMF) is required as described above. Therefore, in the present exemplary embodiment, the calculation amount (cost) at the time of searching is reduced by constructing an index of an external table group in advance.

The coupling table specification system100illustrated inFIG.1includes an external table storage device10, a coupling index construction device110, a coupling index storage unit120, a coupling table search device130, and a coupling table storage unit140.

The external table storage device10stores a plurality of external tables (that is, the external table group) as candidates to be coupled to a base table. An example of the external table is the external table FT1illustrated inFIG.2. The external table storage device10is implemented by, for example, a storage server, a magnetic disk, or the like.

In the present exemplary embodiment, a case where the coupling table specification system100includes the external table storage device10will be described. However, the coupling index construction device110may acquire the external table group from a storage (not illustrated) or the like connected through a communication line. In this case, the coupling table specification system100does not have to include the external table storage device10.

The coupling index construction device110is a device that constructs an index (hereinafter, referred to as a coupling index) of an external table group used for coupling to a base table. The coupling index construction device110includes a coupling column candidate extraction unit112and a coupling index generation unit114.

The coupling column candidate extraction unit112extracts, as a coupling column candidate, a column including a record that can be a key of coupling to another table among external tables included in the external table group. For example, the coupling column candidate extraction unit112estimates all column types of the external table group, and determines whether or not a column of the estimated type is couplable to a column of another table. Note that the column type here may be a type such as a “character string type” or a “numerical value type” indicating an attribute of a character, or may indicate a concept represented by the column.

A method of estimating the column type is arbitrary, and a known method may be used. The coupling column candidate extraction unit112may estimate each column type (meaning of the column) by using, for example, the method described in PTL 2. Then, for example, in a case where the estimated column type indicates a predetermined meaning or is an attribute of a predetermined character (for example, the character string type), the coupling column candidate extraction unit112may extract the column as the coupling column candidate.

FIG.3is an explanatory diagram illustrating an example of processing of estimating the column type. For example, based on records illustrated inFIG.3, it is assumed that a column 1 including a character string is a column meaning “name”, a column 2 including a number is a column meaning “age”, and a column 3 including alphanumeric characters is a column meaning “grade”.

In this case, the coupling column candidate extraction unit112may determine that there is a high possibility that data of the column meaning “name” will be a coupling key, and extract the column 1 as the coupling column candidate. In addition, for example, a numerical value type column or a column having a small number of unique values is unlikely to serve as the coupling key, and there is a high possibility that a character string type column serves as the coupling key. Therefore, the coupling column candidate extraction unit112may extract the character string type column 1 having a large number of unique values as the coupling column candidate.

The coupling index generation unit114generates a coupling index of an external table group. Specifically, the coupling index generation unit114generates a coupling index of the extracted coupling column candidates. In this way, a target of the index is limited to the coupling column candidate, so that a cost required to generate a coupling index and the size of a coupling index to be generated can be reduced.

In the present exemplary embodiment, the coupling index generation unit114creates, as the coupling index, an index for searching for a record whose similarity calculated by the similarity function is greater than a predetermined threshold for each similarity function. It is sufficient if the coupling index generation unit114generates the coupling index by any method according to the similarity function.

Various methods of generating the index according to the similarity function are known. For example, minHash-locality-sensitive hashing (LSH) is known as the index according to the similarity function for calculating the Jaccard similarity. Furthermore, a method of generating a set (matrix) of vectors on a memory and a library (FAISS) are known as the index according to the similarity function for calculating the Euclidean similarity. In addition, a transposed index is known as the index according to the similarity function for calculating whether or not there is an exact match. Since the method of generating these indexes is widely known, a detailed description thereof is omitted here.

As the coupling index generated in this way is used for searching, the calculation amount can be theoretically reduced to O (MF log(N)), and searching can be quickly performed. The coupling index generation unit114stores the generated coupling index in the coupling index storage unit120.

The coupling column candidate extraction unit112and the coupling index generation unit114are implemented by a processor (for example, a central processing unit (CPU) or a graphics processing unit (GPU)) of a computer that operates according to a program (coupling index generation program).

For example, the program may be stored in a storage unit (not illustrated) included in the coupling index construction device110, and the processor may read the program and operate as the coupling column candidate extraction unit112and the coupling index generation unit114according to the program. Furthermore, the function of the coupling index construction device110may be provided in a software as a service (SaaS) format.

In addition, each of the coupling column candidate extraction unit112and the coupling index generation unit114may be implemented by dedicated hardware. In addition, some or all of the components of each device may be implemented by a general-purpose or dedicated circuitry, a processor, or the like, or a combination thereof. These may be implemented by a single chip or may be implemented by a plurality of chips connected via a bus. Some or all of the components of each device may be implemented by a combination of the above-described circuitry or the like and the program.

Furthermore, in a case where some or all of the components of the coupling index construction device110are implemented by a plurality of information processing devices, circuitries, and the like, the plurality of information processing devices, circuitries, and the like may be arranged in a centralized manner or in a distributed manner. For example, the information processing device, the circuitry, and the like may be implemented as a form in which each of a client server system, a cloud computing system, and the like is connected via a communication network.

The coupling index storage unit120stores the coupling index according to the similarity function. In the present exemplary embodiment, a case where the coupling index storage unit120stores the coupling index generated by the coupling index construction device110has been described, but the coupling index storage unit120may store a coupling index generated by another device (not illustrated).

The coupling table search device130searches for a table that is countable to a column that is a target (hereinafter, referred to as a target column) in a base table from an external table group by using the coupling index. The coupling table search device130includes an input unit132, a search plan generation unit134, a record search unit136, and a coupling table output unit138.

The input unit132receives an input of the target column to be coupled to the external table among the columns included in the base table. In addition, the input unit132reads the coupling index stored in the coupling index storage unit120. Note that the input unit132may read the coupling index from another storage device (not illustrated) other than the coupling index storage unit120.

The search plan generation unit134analyzes a record in the target column before performing a search using the coupling index for each similarity function, and generates a search plan that defines a use order of the coupling index at the time of searching.

First, the search plan generation unit134calculates, for each coupling index, the number of couplable record pairs (hereinafter, referred to as the number of results) estimated in a case where the record in the target column is found using the coupling index for each similarity function. Examples of a method of estimating the number of results by using the coupling index for the similarity function include kernel density estimation and cardinality estimation. The search plan generation unit134may estimate the number of results for each coupling index by using these known estimation methods.

Next, the search plan generation unit134generates a search plan that defines the use order of the coupling index in descending order of the calculated number of results. The reason for defining the use order in this manner is as follows. There is a high possibility that many couplable record pairs can be found by performing a search using the coupling index estimated to have a large number of results. Then, the record of the external table group already determined to be couplable can be excluded from a search target in the subsequent coupling index, so that the search processing can be omitted. As a result, a cost for the search can be further reduced.

For example, it is assumed that there are coupling indexes A and B of two types of similarity functions. That is, the number F of similarity functions is 2 (F=2). Here, it is assumed that the number N of all records included in the external table group is 10 (N=10), and the number M of all records of the base table is 1 (M=1). Then, it is assumed that the number of results in a case of using the coupling index A for a record of a certain target column is two and the number of results in a case of using the coupling index B is five.

In a case where the search is performed by using the coupling index A and the coupling index B in this order, the calculation amount is log(10)+log(8). On the other hand, in a case where the search is performed by using the coupling index B and the coupling index Ain this order, the calculation amount is log(10)+log(5). In this way, the use order of the coupling index is defined in descending order of the number of results, so that the calculation amount can be reduced.

The record search unit136searches for the record in the target column by using the coupling index in the order defined in the search plan. At this time, the record search unit136excludes a record in the external table that is found by an already used coupling index from the search target, and performs a search using a subsequent coupling index. Then, the record search unit136specifies, as the coupling table, an external table in which records whose number is equal to or larger than the predetermined threshold Tchave been found as a result of searching for a record in the target column by using all the coupling indexes.

FIG.4is an explanatory diagram illustrating an example of processing of specifying the coupling table of the target column. First, once the input unit132inputs a record R1of the target column, the search plan generation unit134generates the search plan. In the example illustrated inFIG.4, it is assumed that the search plan is generated as “First: exact match coupling index, Second: Jaccard similarity coupling index, Third: Euclidean distance coupling index”.

Next, the record search unit136searches for the record R1of the target column by using the coupling index in the order defined in the search plan. Here, the record search unit136first searches for the record R1of the target column by using the exact match coupling index. As a result, a matching record group (hereinafter, referred to as a first record group) is found in the external table group. Next, the record search unit136excludes the first record group from the target and searches for the record R1in the target column by using the Jaccard similarity coupling index. As a result, a matching record group (hereinafter, referred to as a second record group) is further found in the external table group. Then, the record search unit136excludes the first record group and the second record group from the target and searches for the record R1in the target column by using the Euclidean distance coupling index. As a result, a matching record group (hereinafter, a third record group) is further found in the external table group.

As a result of this search, for example, it is assumed that a record “RAMUNE 250 ml” is found from a column 1 of a table A and a record “HATA RAMUNE” is found from a column 3 of a table C as illustrated inFIG.4. The record search unit136specifies the table A including the record “RAMUNE 250 ml” as a table (coupling table) that is couplable through the column 1, and specifies the table C including the record “HATA RAMUNE” as a table (coupling table) that is couplable through the column 3.

The coupling table output unit138outputs the found coupling table. The coupling table output unit138may store the found coupling table in the coupling table storage unit140.

The coupling table storage unit140stores a table that is couplable to the target column in the base table. The coupling table storage unit140may store, for example, a couplable base table in association with the coupling table. Note that the coupling table storage unit140may store the coupling table found by the coupling table search device130, or may store a coupling table generated by another device (not illustrated).

The coupling index storage unit120and the coupling table storage unit140are implemented by, for example, a magnetic disk or the like.

The input unit132, the search plan generation unit134, the record search unit136, and the coupling table output unit138are implemented by a processor of a computer that operates according to the program (coupling table search program).

For example, the program may be stored in a storage unit (not illustrated) included in the coupling table search device130, and the processor may read the program and operate as the input unit132, the search plan generation unit134, the record search unit136, and the coupling table output unit138according to the program. Furthermore, the function of the coupling table search device130may be provided in a SaaS format.

Next, an operation of the coupling table specification system100of the present exemplary embodiment will be described.FIG.5is a flowchart illustrating an operation example of the coupling index construction device110of the present exemplary embodiment. The coupling column candidate extraction unit112extracts a coupling column candidate from each table included in the external table group (step S11). The coupling index generation unit114generates a coupling index of the extracted coupling column candidate for each similarity function (step S12). Then, the coupling index generation unit114stores the generated coupling index in the coupling index storage unit120(step S13).

FIG.6is a flowchart illustrating an operation example of the coupling table search device130of the present exemplary embodiment. The input unit132receives an input of a coupling index from the coupling index storage unit120(step S21). In addition, the input unit132receives an input of a target column among columns included in a base table (step S22).

The search plan generation unit134calculates the number of results for each coupling index estimated for a record in the target column (step S23). Then, the search plan generation unit134generates a search plan that defines a use order of the coupling index in descending order of the calculated number of results (step S24).

The record search unit136searches for the record in the target column by using the coupling index in the order defined in the search plan (step S25). At this time, the record search unit136excludes a record in the external table that is found by an already used coupling index from the search target, and performs a search using a subsequent coupling index. Then, the record search unit136specifies, as the coupling table, an external table in which records whose number is equal to or larger than a predetermined threshold have been found (step S26).

As described above, in the present exemplary embodiment, the input unit132receives an input of a coupling index, the search plan generation unit134calculates the number of results for each coupling index, and generates the search plan that defines a use order of the coupling index in descending order of the calculated number of results. In addition, the record search unit136searches for a record in the target column by using the coupling index in the order defined in the search plan and specifies, as the coupling table, an external table in which records whose number is equal to or larger than a predetermined threshold have been found. At this time, the record search unit136excludes a record in the external table that is found by an already used coupling index from the search target, and performs a search using a subsequent coupling index. Therefore, a cost for specifying a table that is couplable to a target column can be reduced.

That is, in the coupling table specification system100of the present exemplary embodiment, since a search space can be pruned by using coupling indexes for different similarity functions, it is possible to quickly extract data that is couplable to base data from an external table group with a high accuracy.

Second Exemplary Embodiment

Next, a second exemplary embodiment of the present invention will be described. The second exemplary embodiment aims to quickly specify a table including a column including data correlated with data of a target column.FIG.7is a block diagram illustrating a configuration example of an exemplary embodiment of a correlation table specification system according to the present invention. A correlation table specification system200according to the present exemplary embodiment is a system that specifies an external table (hereinafter, referred to as a correlation table) including a column correlated with a target column.

In the present exemplary embodiment, the column correlated with the target column means a column of the external table group assumed to have any correlation with data included in the target column, and more specifically means a column of that external table group including a data group having a similar feature or distribution of a data group included in the target column. In addition, this correlation includes both a positive correlation and a negative correlation.

For example, it is assumed that there is a task of “predicting sales”. At this time, the target column is a column including sales data included in a base table. In a case where there is a prediction model with sales as an objective variable, the correlated column corresponds to a column including an explanatory variable used as a feature that can affect the objective variable. Therefore, as the correlation table is specified, a more effective explanatory variable (feature) can be added to the prediction model for implementing the task of “predicting sales”, and as a result, performance of the task can be improved.

FIG.8is an explanatory diagram illustrating an example of processing of extracting the correlated column. The reason for extracting the correlated column is to determine which table is useful for improving the performance of the task in the external table group. For example, it is assumed that tables are coupled through a column “product name” of a base table BT2and a column “drink name” of an external table FT2illustrated inFIG.8. In this case, it is desirable to be able to determine whether columns (a column “attribute 1” or a column “attribute 2”) other than the coupling column of the external table FT2are useful for improving the performance of the task of predicting the column “sales” included in the base table.

In addition, in the present exemplary embodiment, a table contributing to the improvement of the performance of the task is defined as follows. That is, in a case where a certain external table is couplable to the base table through records whose number is equal to or larger than the threshold Tc, and there is a column in which a value (hereinafter, referred to as a correlation value) indicating the degree of correlation with a column of the base table that corresponds to the objective variable is equal to or higher than a threshold Tpamong columns associated by the coupling, the external table is set as a table contributing to the improvement of the performance of the task. Note that the present exemplary embodiment mainly aims to specify a column correlated with a target column, and it does not matter whether or not coupling to a base table is possible. In the following description, the threshold Tpof the correlation value may be referred to as a correlation value threshold.

The correlation table specification system200illustrated inFIG.7includes an external table storage device10, a correlation index construction device210, a correlation index storage unit220, a correlation table search device230, and a correlation table storage unit240.

Similarly to the first exemplary embodiment, the external table storage device10stores a plurality of external tables (that is, an external table group). The external table storage device10is implemented by, for example, a storage server, a magnetic disk, or the like.

Also in the present exemplary embodiment, a case where the correlation table specification system200includes the external table storage device10will be described. However, the correlation index construction device210may acquire the external table group from a storage (not illustrated) or the like connected through a communication line. In this case, the correlation table specification system200does not have to include the external table storage device10.

The correlation index construction device210is a device that constructs an index (hereinafter, referred to as a correlation index) of an external table group used for searching for a column correlated with a target column. The correlation index construction device210includes a non-coupling column candidate extraction unit212and a correlation index generation unit214.

The non-coupling column candidate extraction unit212extracts, as a non-coupling column candidate, a column including a record that is assumed not to be a key of coupling to another table among external tables included in the external table group. In other words, the non-coupling column candidate extraction unit212extracts, as the non-coupling column candidate, a column other than the coupling column candidate extracted by the coupling column candidate extraction unit112of the first exemplary embodiment.

Similarly to the processing in the coupling column candidate extraction unit112of the first exemplary embodiment, for example, the non-coupling column candidate extraction unit212may estimate all column types of the external table group, determine whether or not a column of the estimated type is couplable to a column of another table, and extract the column as the non-coupling column candidate in a case where it is determined that the column of the estimated type is not couplable. At this time, similarly to the coupling column candidate extraction unit112of the first exemplary embodiment, for example, in a case where the estimated column type indicates a predetermined meaning or is an attribute of a predetermined character (for example, a numerical value type), the non-coupling column candidate extraction unit212may extract the column as the non-coupling column candidate.

For example, in the example illustrated inFIG.3, the non-coupling column candidate extraction unit212may determine that data of a column meaning “age” or “grade” is unlikely to serve as the coupling key, and may extract a column 2 and a column 3 as the non-coupling column candidates. In addition, for example, a numerical value type column or a column having a small number of unique values is unlikely to serve as the coupling key. Therefore, the non-coupling column candidate extraction unit212may extract the numerical value type column 2 or the alphanumeric character type column 3 assumed to have a small number of unique values as the non-coupling column candidate.

The correlation index generation unit214generates a correlation index of an external table group. Specifically, the correlation index generation unit214generates a coupling index of the extracted non-coupling column candidates. In this way, a target of the index is limited to the non-coupling column candidate, so that a cost required to generate a correlation index and the size of a correlation index to be generated can be reduced.

In the present exemplary embodiment, the correlation index generation unit214generates, as the correlation index, an index for searching for a column whose correlation value is equal to or greater than a predetermined correlation value threshold from columns of an external table. As described above, the present exemplary embodiment aims to quickly specify a table including a column whose correlation value with a column of a base table is equal to or greater than the threshold Tpin order to specify a table including a column including correlated data. However, it is difficult to construct an index for calculating a correlation value.

Therefore, the correlation index generation unit214first generates a feature vector indicating a feature of each column. Here, feature vectors of two columns are X and Y. Furthermore, the correlation index generation unit214calculates vectors (hereinafter, referred to as standardized vectors) (X′,Y′) obtained by standardizing the generated feature vectors. Furthermore, the correlation index generation unit214defines a function for calculating the correlation value based on a distance between the standardized vectors. That is, it can be said that this processing converts the calculation of the correlation value into calculation based on the distance.

Here, the function for calculating the correlation value is corr(X′,Y′), and a function for calculating the distance is d(X′,Y′). At this time, in a case where d(X′,Y′) is a function for calculating the Euclidean distance, the correlation index generation unit214may calculate the correlation value as in Equation 1 exemplified below, for example, as described in NPL 1.

In this manner, the correlation index generation unit214defines the function for calculating the correlation value by using the distance, and generates the correlation index for searching for a column whose correlation value calculated by the distance to the feature vector of the target column is equal to or greater than the correlation value threshold by using the defined function. In accordance with this definition, the correlation index generation unit214may convert the correlation value threshold Tpand define a threshold Tdas in Equation 2 exemplified below. That is,

In the following description, the threshold Tddetermined based on the correlation value threshold Tpmay be referred to as a distance threshold.

Therefore, it is sufficient if the correlation index generation unit214determines columns whose distance therebetween is calculated to be equal to or less than the distance threshold Tdas correlated columns. In this way, as the correlation value can be calculated based on the Euclidean distance, for example, it is possible to generate an index for searching for a record whose correlation value is equal to or greater than a predetermined threshold by using the known method (the method of generating the index according to the similarity function) as described in the first exemplary embodiment.

Here, the method of calculating the correlation value based on the Euclidean distance has been described. However, the method of calculating the correlation value is not limited to the method based on the Euclidean distance. A correlation value calculation method is arbitrary as long as it is a method capable of generating an index for searching for a record whose correlation value is equal to or greater than a predetermined threshold.

Then, the correlation index generation unit214generates the correlation index based on the standardized vectors (X′,Y′). By generating such a correlation index, it is possible to quickly search for a column whose distance to the target column is smaller than the threshold Tdfrom the external table group.

Note that, in a case where such a correlation index is used, it is simply necessary to calculate distances from the target column to all the columns of the external table group and compare the calculated distances with the threshold Td. In a case where it is assumed that that the number of all columns of the external table group is C, the calculation amount is O (C).

It is also conceivable to generate an index of a distance to further improve a search speed. However, since a column to be coupled to the external table group is unknown in advance, using the distance index cannot solve this problem. Therefore, in the present exemplary embodiment, a correlation index capable of reducing the amount of data in columns to be compared and reducing a calculation cost required for search is created.

First, the correlation index generation unit214extracts a predetermined element in ascending order of the size of an element of the standardized vectors (X′,Y′), and constructs the correlation index based on the extracted element. A method of constructing the correlation index is similar to the method of generating the coupling index in the first exemplary embodiment. For example, the correlation index generation unit214may generate the correlation index of the Euclidean distance search described above based on the extracted element.

In the following description, the number of extracted elements is referred to as a size, and a vector extracted from the feature vectors (standardized vectors) in ascending order of the size of an element of a predetermined size is referred to as a size-specific vector. A correlation index generated based on the size-specific vector is referred to as a size-specific correlation index. That is, the correlation index generation unit214generates the size-specific vector obtained by extracting an element of a predetermined size from the elements of the standardized vectors in ascending order, and generates the size-specific correlation index from the generated size-specific vector. Note that a method of generating the size-specific correlation index from the size-specific vector is similar to a method of creating an index for searching for a column whose distance is equal to or greater than a predetermined threshold.

The size-specific correlation index generated in this manner is an index for searching for a column whose correlation value indicating the degree of correlation between columns is equal to or larger than the correlation value threshold Tpfrom the external table, and is an index generated for each size from the size-specific vector obtained by extracting an element of a predetermined size from the elements of the feature vectors of the columns in ascending order. In addition, the size-specific correlation index is an index for extracting a column whose distance to the size-specific vector is less than the distance threshold Tddetermined based on the correlation value threshold Tp.

The correlation index generation unit214may extract a predetermined number of elements from the standardized vectors, or may determine the number (size) of elements to be extracted based on distribution of the number of elements in each column. For example, the correlation index generation unit214may determine each of the maximum value of the number of elements, the minimum value of the number of elements, and the average value of the number of elements as the size. Furthermore, the correlation index generation unit214may generate one size-specific correlation index or may generate a plurality of size-specific correlation indexes.

For example, it is assumed that there are four columns P1 to P4, the number of elements of P1 is six, the number of elements of P2 is five, the number of elements of P3 is four, and the number of elements of P4 is two. At this time, the correlation index generation unit214may generate a correlation index of a size of 6, which is the maximum value of the number of elements, a correlation index of a size of 2, which is the minimum value of the number of elements, and a correlation index of a size of 4, which is the average value.

Hereinafter, a method of generating the correlation index will be described with a specific example. Here, it is assumed that two columns (feature vectors) of A=[5, 1, 2, 3, 4, 7] and B=[0, 7, 5, 3, 4, 9] exist, and correlation indexes of size 2, size 4, and size 6 are generated. At this time, the correlation index generation unit214may generate correlation indexes of three types of sizes exemplified below.Correlation index of size 2: A[1,2], B[0,3]Correlation index of size 4: A[1,2,3,4], B[0,3,4,5]Correlation index of size 6: A[1,2,3,4,5,7], B[0,3,4,5,7,9]

Furthermore, the correlation index generation unit214may generate only a correlation index in which an element of a corresponding size exists. For example, for the four columns P1 to P4 described above, it is assumed that P1=[0,1,2,3,4,5], P2=[3,4,5,6,7], P3=[1,2,3,3], and P4=[0,1]. At this time, the correlation index generation unit214may generate correlation indexes exemplified below.Correlation index of size 2: P1[0,1], P2[3,4], P3[1,2], P4[0,1]Correlation index of size 4: P1[0,1,2,3], P2[3,4,5,6], P3[1,2,3,3]Correlation index of size 6: P1[0,1,2,3,4,5]

The correlation index generation unit214stores the generated correlation index in the correlation index storage unit220. In addition, the correlation index generation unit214stores the generated size-specific correlation index in the correlation index storage unit220.

The non-coupling column candidate extraction unit212and the correlation index generation unit214are implemented by a processor of a computer that operates according to a program (correlation index generation program). For example, the program may be stored in a storage unit (not illustrated) included in the correlation index construction device210, and the processor may read the program and operate as the non-coupling column candidate extraction unit212and the correlation index generation unit214according to the program. Furthermore, the function of the correlation index construction device210may be provided in a SaaS format.

The correlation index storage unit220stores the correlation index and the size-specific correlation index. In the present exemplary embodiment, a case where the correlation index storage unit220stores the correlation index and the size-specific correlation index generated by the correlation index construction device210has been described. However, the correlation index storage unit220may store a correlation index and a size-specific correlation index generated by another device (not illustrated).

The correlation table search device230searches for a table including a column correlated with a column that is a target (that is, a target column) in a base table from an external table group by using the correlation index. The correlation table search device230includes an input unit232, an index specification unit234, a candidate column search unit236, and a correlation table output unit238.

The input unit232receives an input of the target column for which a correlated column of the external table group is found, among the columns included in the base table. In addition, the input unit232reads the correlation index stored in the correlation index storage unit220. Note that the input unit232may read the correlation index from another storage device (not illustrated) other than the correlation index storage unit220.

The index specification unit234specifies a correlation index to be used for searching. Specifically, the index specification unit234specifies a correlation index to be used for searching based on the threshold Tcof the number of record pairs determined to be couplable when coupling a base table and an external table. Note that the value of the threshold Tcis determined in advance by a user or the like.

The index specification unit234may determine to use a coupling index of the same size as the value of the threshold Tcfor searching. Note that, in a case where there is no coupling index of the same size as the value of the threshold Tc, the index specification unit234may determine to use a coupling index of the largest size among coupling indexes of sizes smaller than the value of the threshold Tcfor searching. This is because it is guaranteed that all pieces of data of a candidate column can be found by using a coupling index of a size smaller than the value of the threshold Tc.

For example, it is assumed that Tc=3 in a situation where the correlation index of size 2, the correlation index of size 4, and the correlation index of size 6 described above exist. At this time, the index specification unit234determines to use the correlation index of size 2 equal to or smaller than 3 for searching.

Such determination is made for the following reasons. In a case where the threshold Tcis given, the size of a column coupled to an external table is always equal to or larger than Tc. Therefore, a lower limit of the distance can be calculated by listing the element of the column including the objective variable and the element of the feature vector in ascending order of the size. Then, by comparing the lower limit of the distance with the threshold Td, it can be determined whether or not to exclude the feature vector (that is, each column of the external table).

FIG.9is an explanatory diagram illustrating an example of processing of determining whether or not to exclude the feature vector. It is assumed that each of data of a column “sales” of a base table BT3illustrated inFIG.9and data of a column “attribute 1” and a column “attribute 2” of an external table FT3is standardized data. That is, each portion surrounded by a broken line illustrated inFIG.9corresponds to a feature vector.

As illustrated inFIG.9, it is assumed that the feature vector of the column “sales” used as the objective variable is [1,3,5], the feature vector of the column “attribute 1” is [2,1,5], and the feature vector of the column “attribute 2” is [9,7,4]. In addition, it is assumed that the threshold Tcis 2 (Tc=2) and the threshold Tdis 2 (Td=2).

In an initial state, it is unclear whether a column “item name” of the base table BT3and a column “drink name” of the external table FT3are couplable. In other words, it is unclear which record of the external table FT3is coupled to the record of the base table BT3.

Even in such a state, the lower limit of the distance between the column “sales” and the column “attribute 1” can be calculated as d([1,3],[1,2])=1 by comparing elements having small values. Since this value is smaller than the threshold Td=2, the columns may be correlated columns. Therefore, it is determined that the column “attribute 1” is a target on which subsequent processing is to be performed.

On the other hand, the lower limit of the distance between the column “sales” and the column “attribute 2” can be calculated as d([1,3],[4,7])=3 by comparing elements having small values. Since this value is larger than the threshold Td=2, the distance is not smaller than Tdeven in a case where the distance is calculated with any other element. Therefore, the column “attribute 2” is determined as a column having no correlation, and can be excluded from subsequent processing.

The candidate column search unit236searches the external table group by using the correlation index determined for the target column, and searches for a candidate column assumed to be correlated. Specifically, the candidate column search unit236searches for a column equal to or larger than a predetermined threshold (here, the distance threshold Td) from the external table group by using the correlation index. Note that a method of searching for a column equal to or larger than a predetermined threshold (here, the distance threshold Td) by using the correlation index (for example, the correlation index of Euclidean distance search) is widely known, and thus a detailed description thereof is omitted here.

Then, the candidate column search unit236calculates a correlation value between the target column and the found column, and specifies a column equal to or larger than a predetermined threshold (here, the threshold Tpof the correlation value) as the candidate column. In this manner, the candidate column search unit236searches for the column by the correlation index and calculates the correlation value for the found column, so that the correlation value can be calculated only for a column assumed to be more correlated, and thus a calculation cost can be reduced.

The correlation table output unit238outputs the external table including the candidate column as a correlation table. The correlation table output unit238may store the correlation table in the correlation table storage unit240.

FIG.10is an explanatory diagram illustrating an example of processing of specifying the correlation table. In the example illustrated inFIG.10, it is assumed that a target column R2of a base table is a column indicating “sales” which is an objective variable, and the threshold Tcis 3 (Tc=3). In this case, the index specification unit234determines to use the correlation index of size 2 equal to or smaller than the threshold for searching.

The candidate column search unit236searches for a column including a highly correlated feature by using the correlation index of size 2. The example illustrated inFIG.10indicates that a column 2 of a table A is found as a column including a feature a, and a column 5 of a table C is found as a column including a feature b. Then, the candidate column search unit236calculates the correlation value again between the target column and the candidate column, and the correlation table output unit238outputs the table A and the table C including the candidate column.

The correlation table storage unit240stores the correlation table including the candidate column. The correlation table storage unit240may store a correlated column (that is, the candidate column) in association with the target column of the base table. For example, in the above example, the correlation table storage unit240may store the column “sales”, which is the target column that can be the objective variable of the task, and the candidate column in the correlation table in association with each other. Note that the correlation table storage unit240may store the correlation table output by the correlation table search device230or may store a correlation table generated by another device (not illustrated).

The correlation index storage unit220and the correlation table storage unit240are implemented by, for example, a magnetic disk or the like.

The input unit232, the index specification unit234, the candidate column search unit236, and the correlation table output unit238are implemented by a processor of a computer that operates according to a program (correlation table searching program).

For example, the program may be stored in a storage unit (not illustrated) included in the correlation table search device230, and the processor may read the program and operate as the input unit232, the index specification unit234, the candidate column search unit236, and the correlation table output unit238according to the program.

Next, an operation of the correlation table specification system200according to the present exemplary embodiment will be described.FIG.11is a flowchart illustrating an operation example of the correlation index construction device210according to the present exemplary embodiment. The non-coupling column candidate extraction unit212extracts a non-coupling column candidate from an external table (step S31). The correlation index generation unit214generates a feature vector indicating a feature of the non-coupling column candidate (step S32), and generates a standardized vector obtained by standardizing the generated feature vector (step S33).

In addition, the correlation index generation unit214generates a size-specific vector obtained by extracting an element of a predetermined size from the elements of the generated standardized vector in ascending order (step S34), and generates a size-specific correlation index for each size from the generated size-specific vector (step S35). Then, the correlation index generation unit214stores the generated size-specific correlation index in the correlation index storage unit220(step S36).

FIG.12is a flowchart illustrating an operation example of the correlation table search device230according to the present exemplary embodiment. The input unit232receives an input of a target column among columns included in a base table (step S41). The index specification unit234specifies a size-specific correlation index to be used for searching among the size-specific correlation indexes stored in the correlation index storage unit220based on the threshold Tcof the number of record pairs (step S42). The input unit232receives an input of the specified size-specific correlation index (step S43).

The candidate column search unit236uses the specified size-specific correlation index to search for a column whose distance to the target column is equal to or less than the distance threshold from the external table (step S44). The candidate column search unit236calculates a correlation value between the found column and the target column (step S45), and searches for a column whose correlation value is equal to or larger than the correlation value threshold as a candidate column (step S46). Then, the correlation table output unit238outputs the external table including the candidate column as a correlation table (step S47).

As described above, in the present exemplary embodiment, the input unit232receives an input of the size-specific correlation index, and the index specification unit234specifies the size-specific correlation index to be used for searching among the size-specific correlation indexes based on the threshold Tcof the number of record pairs. In addition, the candidate column search unit236searches for a column whose distance to the target column is equal to or less than the distance threshold Tdfrom the external table by using the specified size-specific correlation index, calculates a correlation value indicating the degree of correlation between the found column and the target column, and searches for a column whose correlation value is equal to or larger than the correlation value threshold Tpas a candidate column. Then, the correlation table output unit238outputs the external table including the candidate column. Therefore, a table including data correlated with data of a target column can be quickly specified.

In the present exemplary embodiment, the correlation index generation unit214generates the correlation index. At this time, the correlation index generation unit214generates a feature vector indicating a feature of each column of the external table, generates a standardized vector obtained by standardizing the generated feature vector, generates a size-specific vector obtained by extracting an element of a predetermined size from elements of the generated standardized vector in ascending order, and generates a size-specific correlation index from the generated size-specific vector. In addition, the correlation index generation unit214defines a function for calculating the correlation value by using a distance to the size-specific vector, and generates the correlation index for searching for a column of the external table of which the correlation value calculated by a distance between the feature vector of a target column and the size-specific vector is equal to or larger than the correlation value threshold by using the defined function. By generating such a correlation index (size-specific correlation index) in advance, the correlation table search device230can quickly specify a table including data correlated with data of a target column.

Third Exemplary Embodiment

Next, a third exemplary embodiment of the present invention will be described. The third exemplary embodiment aims to efficiently integrate correlated data with a table including a target column.FIG.13is a block diagram illustrating a configuration example of an exemplary embodiment of a table integration system according to the present invention. A table integration system300of the present exemplary embodiment is a system that integrates a column correlated with a target column included in a base table.

In the present exemplary embodiment, integrating an external table with a base table refers to processing of coupling an external table (that is, a coupling table) that is couplable to a base table to generate a new table as described in the first exemplary embodiment.

Furthermore, in the present exemplary embodiment, the target column is a column including target data in an assumed task, and is, for example, a column including an objective variable of a prediction model. Furthermore, the task means prediction (estimation) processing such as regression and classification performed using a selected feature, and is specifically given by a function or the like indicating the prediction model.

In addition, in the present exemplary embodiment, the column correlated with the target column means a column of an external table group assumed to have any correlation with data included in the target column, and more specifically means a column of an external table group including a data group having a similar feature or distribution of a data group included in the target column, similarly to the second exemplary embodiment. In addition, this correlation includes both a positive correlation and a negative correlation.

In addition, similarly to the second exemplary embodiment, the correlated column corresponds to a column including an explanatory variable used as a feature that can affect the objective variable. Therefore, as such a column is integrated with the base table, the performance of the task can be improved.

The table integration system300illustrated inFIG.13includes a table storage device20, an integrated table generation device310, and an integrated table storage unit330.

The table storage device20stores a plurality of external tables (that is, an external table group). Unlike the external table storage devices10of the first and second exemplary embodiments, the table storage device20of the present exemplary embodiment stores an external table group extracted from a predetermined viewpoint. The table storage device20includes a coupling table storage unit21and a correlation table storage unit22.

The coupling table storage unit21stores a coupling table (that is, an external table that is couplable to a base table) described in the first exemplary embodiment. It is assumed that the coupling table storage unit21stores the couplable base table in association with the coupling table. The coupling table storage unit21may store the coupling table specified by the coupling table specification system100of the first exemplary embodiment, or may store a coupling table generated by another system (not illustrated) or the like.

The correlation table storage unit22stores a correlation table (that is, an external table including a column correlated with a target column) described in the second exemplary embodiment. The correlation table storage unit22may store the correlation table specified by the correlation table specification system200of the second exemplary embodiment, or may store a correlation table generated by another system (not illustrated) or the like.

In the present exemplary embodiment, as described in the second exemplary embodiment, it is assumed that the correlation table storage unit22stores a column (that is, a candidate column) including data correlated with data of a target column in association with the target column of a base table. In addition, the correlation table storage unit22of the present exemplary embodiment only needs to store information by which a column of a table correlated with the target column can be specified, and does not necessarily need to store data of each column. That is, the correlation table storage unit22may store the candidate column (that is, a column whose correlation value with respect to the target column is equal to or larger than a predetermined threshold Tp) described in the second exemplary embodiment.

In the present exemplary embodiment, it is assumed that the coupling table is generated in advance by, for example, the method described in the first exemplary embodiment and stored in the coupling table storage unit21. In addition, it is assumed that the candidate column is also generated in advance by, for example, the method described in the second exemplary embodiment and stored in the correlation table storage unit22.

The integrated table generation device310is a device that generates an integrated table obtained by coupling the base table and the candidate column. The integrated table generation device310includes an input unit312, a table coupling unit314, a feature processing unit316, a feature selection unit318, and an integrated table output unit320.

The input unit312receives an input of the base table and designation of the target column. In addition, the input unit312receives an input of the coupling table and the candidate column. Note that the input unit312may receive designation of the objective variable of the task. In this case, the input unit312may specify the target column of the corresponding base table from the designated objective variable.

When the input of the base table and the designation of the target column are received, the input unit312may acquire the coupling table for the input base table from the coupling table storage unit21and acquire the candidate column for the target column from the correlation table storage unit22.

The table coupling unit314couples a column corresponding to the candidate column in the coupling table to the base table. Specifically, the table coupling unit314extracts the candidate column from the coupling table, and couples the extracted candidate column of the coupling table to the base table.

Note that a method of coupling the tables is arbitrary. The table coupling unit314may couple the coupling table to the base table by an arbitrary method such as left-join or out-join. Note that a table after coupling may be referred to as an integrated table.

FIG.14is an explanatory diagram illustrating an example of processing of coupling tables. In the example illustrated inFIG.14, it is assumed that a base table BT4including a column “sales” including data used as the objective variable as the target column and a couplable external table (coupling table) FT4exist. In addition, it is assumed that the external table FT4is a correlation table including a column “attribute 1” and a column “attribute 2” which are columns (correlation columns) determined to be correlated with the target column. In the external table FT4, a column “drink name” is a coupling column candidate, and the columns “attributes 1 to n” correspond to non-coupling column candidates.

The table coupling unit314extracts the column “attribute 1” and the column “attribute 2” from the external table FT4. In other words, the table coupling unit314deletes columns (the non-coupling column candidates) other than the column “drink name”, the column “attribute 1”, and the column “attribute 2” from the external table FT4. Then, the table coupling unit314couples the column “item name” and the column “drink name” of the base table BT4, and couples the column “attribute 1” and the column “attribute 2” to generate an integrated table IT.

The feature processing unit316generates a feature for data of the target column from data of a column included in the integrated table. The feature processing unit316can use various methods for generating the feature. For example, it is assumed that a missing value exists in the integrated table according to the coupling method (for example, left-join) or an original table state. In this case, the feature processing unit316may compensate for the missing value by estimating data distribution by a known method or using external knowledge information or the like.

In addition, the feature processing unit316may generate one or more column sets (clusters) by clustering selected columns based on the distribution of data in each column. Note that a method of clustering the columns is also arbitrary, and the feature processing unit316may cluster the columns by using, for example, the method described in NPL 2.

Then, the feature processing unit316may generate the feature for each clustered column set (cluster). Note that a method of generating the feature is also arbitrary, and the feature may be generated based on a predetermined method. For example, the feature processing unit316may couple all columns included in one cluster to generate the feature. In addition, the feature processing unit316may select one column from one cluster by a predetermined method (for example, a column having the largest number of unique values is selected) to generate the feature.

The feature selection unit318selects a feature that improves performance of a predetermined task based on data included in the coupled candidate column or the feature generated from the candidate column. Here, improving the performance of the task means improving any evaluation index related to the task, and more specifically, improving prediction accuracy and the like. The evaluation index used at the time of selection is arbitrary and determined in advance.

Hereinafter, a specific method of selecting the feature will be described. Here, it is assumed that a trained model that predicts sales of a product by learning is used as the task. In this case, the feature selection unit318selects the feature that improves performance of the task of predicting the data of the target column.

In a case of a task of performing sales prediction, data of “sales” included in the target column is used as the objective variable, and data of each column included in the coupling table is used as the feature (explanatory variable). That is, each record of the integrated table corresponds to training data. Note that a mode of the trained model is arbitrary, and examples thereof include a linear model and a random forest.

First, the feature selection unit318selects one or more features among the generated features by a predetermined method. Note that the method of selecting the feature is not limited, and the feature selection unit318may select the feature by using an arbitrary feature selection technology. Then, the feature selection unit318trains the model by using the selected feature.

Then, the feature selection unit318evaluates the trained model based on a predetermined evaluation method, and selects a feature that improves the calculated evaluation index. Note that the evaluation method is also not particularly limited, and the feature selection unit318may evaluate the trained model based on the f1 score of cross validation, for example.

In addition, the feature selection unit318may generate a plurality of trained models of the same mode and aggregate (an average, a weighted average, or the like) evaluation results of the plurality of trained models, or may generate a plurality of trained models of different modes (for example, a linear model and a random forest) and aggregate evaluation results of the plurality of trained models.

Then, the feature selection unit318selects one or more features with higher evaluations. For example, in a case where a feature is selected and learned by a forward method (step forward), the feature selection unit318may select a combination of features having the highest evaluation index. However, the method of selecting the feature is not limited to this method, and any method may be used.

The integrated table output unit320outputs an integrated table obtained by coupling a column including the selected feature and the base table. In other words, the integrated table output unit320outputs an integrated table in which a column from which the selected feature is generated is left. The integrated table output unit320may store the integrated table in the integrated table storage unit330.

The integrated table storage unit330stores a table (that is, the integrated table) obtained by coupling the column of the external table with the base table.

The coupling table storage unit21, the correlation table storage unit22, and the integrated table storage unit330are implemented by, for example, a magnetic disk or the like.

The input unit312, the table coupling unit314, the feature processing unit316, the feature selection unit318, and the integrated table output unit320are implemented by a processor of a computer that operates according to a program (integrated table generation program).

For example, the program may be stored in a storage unit (not illustrated) included in the integrated table generation device310, and the processor may read the program and operate as the input unit312, the table coupling unit314, the feature processing unit316, the feature selection unit318, and the integrated table output unit320according to the program. In addition, the function of the integrated table generation device310may be provided in a SaaS format.

Next, an operation of the table integration system300of the present exemplary embodiment will be described.FIG.15is a flowchart illustrating an operation example of the integrated table generation device310of the present exemplary embodiment. The input unit312receives an input of a coupling table, a candidate column, and a base table (step S51). The table coupling unit314couples a column corresponding to a candidate column in the coupling table with the base table (step S52). Note that the feature processing unit316may generate a feature from data included in the coupled column.

The feature selection unit318selects a feature that improves performance of a task based on data included in the coupled candidate column (step S53). Then, the integrated table output unit320outputs an integrated table obtained by coupling a column including the selected feature and the base table (step S54).

As described above, in the present exemplary embodiment, the input unit312receives an input of a coupling table, a candidate column, and a base table, and the table coupling unit314couples a column corresponding to a candidate column in the coupling table with the base table. Then, the feature selection unit318selects a feature that improves performance of a task based on data included in the coupled candidate column, and the integrated table output unit320outputs an integrated table obtained by coupling a column including the selected feature and the base table. Therefore, correlated data can be efficiently integrated with a table including a target column.

Fourth Exemplary Embodiment

Next, a fourth exemplary embodiment of the present invention will be described. In a fourth exemplary embodiment, a method of efficiently integrating correlated data with respect to a table including a target column by combining the systems of the first to third exemplary embodiments will be described.

FIG.16is a block diagram illustrating a configuration example of an exemplary embodiment of an external data utilization system according to the present invention. An external data utilization system400illustrated inFIG.16includes the coupling table specification system100according to the first exemplary embodiment, the correlation table specification system200according to the second exemplary embodiment, and the table integration system300according to the third exemplary embodiment.

The coupling table specification system100stores, in the coupling table storage unit140, a coupling table for a base table generated based on the processing described in the first exemplary embodiment. In addition, the correlation table specification system200stores, in the correlation table storage unit240, a correlation table and a candidate column generated based on the processing described in the second exemplary embodiment. Then, the table integration system300acquires a coupling table for a base table from the coupling table storage unit140based on the processing described in the third exemplary embodiment, acquires a correlation table (candidate column) for a target column from the correlation table storage unit240, generates an integrated table, and stores the integrated table in the integrated table storage unit330.

The coupling table generation processing performed by the coupling table specification system100and the correlation table generation processing performed by the correlation table specification system200can be separately and independently performed at any timing. Therefore, correlated data can be efficiently integrated with a base table as necessary.

Next, an outline of the present invention will be described.FIG.17is a block diagram illustrating an outline of a correlation table search device according to the present invention. A correlation table search device610(for example, the correlation table search device230) according to the present invention includes: input means611(for example, the input unit232) that receives an input of a size-specific correlation index from a storage device (for example, the correlation index storage unit220) that stores the size-specific correlation index, the size-specific correlation index being an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold (for example, the threshold Tp) from an external table and being an index that is generated for each size corresponding to a predetermined number from a size-specific vector obtained by extracting, in ascending order, the predetermined number of elements of a feature vector indicating a feature of data of the column, and extracts, from the external table, a column whose distance to the size-specific vector is equal to or less than a distance threshold (for example, the threshold Td) determined based on the correlation value threshold; index specification means612(for example, the index specification unit234) that specifies a size-specific correlation index to be used for searching among the size-specific correlation indexes based on a predetermined threshold (for example, the threshold Tc) of the number of record pairs determined to be couplable when coupling a base table including a target column and the external table; candidate column search means613(for example, the candidate column search unit236) that searches for a column whose distance to the target column is equal to or less than the distance threshold from the external table by using the specified size-specific correlation index, calculates the correlation value indicating a degree of correlation between the found column and the target column, and searches for a column whose correlation value is equal to or larger than the correlation value threshold as a candidate column; and output means614(for example, the correlation table output unit238) that outputs an external table including the candidate column.

With such a configuration, a table including data correlated with data of a target column can be quickly specified.

In addition, the index specification means612may specify the size-specific correlation index of the largest size with a value equal to or less than the threshold of the number of record pairs. With such a configuration, it is ensured that all pieces of data of a candidate column can be found.

FIG.18is a block diagram illustrating an outline of a correlation index construction device according to the present invention. A correlation index construction device620(for example, the correlation index construction device110) of the present invention includes correlation index generation means621(for example, the correlation index generation unit214) that generates, for each column of an external table, a correlation index that is an index for searching for a column whose correlation value indicating the degree of correlation between columns is equal to or larger than a predetermined correlation value threshold (for example, the threshold Tp) from the external table.

The correlation index generation means621generates a feature vector indicating a feature of each column, generates a standardized vector obtained by standardizing the generated feature vector, generates a size-specific vector obtained by extracting a predetermined number of elements from elements of the generated standardized vector in ascending order, and generates a size-specific correlation index that is a correlation index for each size corresponding to the predetermined number from the generated size-specific vector. In addition, the correlation index generation means621defines a function for calculating the correlation value by using a distance to the size-specific vector, and generates the correlation index for searching for a column of the external table of which the correlation value calculated by a distance between the feature vector of a target column and the size-specific vector is equal to or larger than the correlation value threshold by using the defined function.

With such a configuration, it is possible to construct an index for quickly specifying a table including data correlated with data of a target column.

In addition, the correlation index construction device620may include non-coupling column candidate extraction means (for example, the non-coupling column candidate extraction unit212) that extracts, as a non-coupling column candidate, a column including a record that is assumed not to serve as a key of coupling to another table among external tables included in an external table group. Then, the correlation index generation means621may generate the feature vector indicating a feature of the non-coupling column candidate and generate the correlation index for the non-coupling column candidate. With such a configuration, a cost for generating the correlation index can be reduced.

Furthermore, the correlation index generation means621may determine each size of the size-specific correlation index according to the number of elements of the generated feature vector.

Specifically, the correlation index generation means621may determine each size of the size-specific correlation index to be a size corresponding to at least one of the maximum value of the number of elements of the feature vector, the minimum value of the number of elements of the feature vector, or the average value of the number of elements of the feature vector based on the generated feature vector.

FIG.19is a schematic block diagram illustrating a configuration of a computer according to at least one exemplary embodiment. A computer1000includes a processor1001, a main storage device1002, an auxiliary storage device1003, and an interface1004.

The correlation table search device610or the correlation index construction device620described above is implemented in the computer1000. Then, the operation of each processing unit described above is stored in the auxiliary storage device1003in the form of a program (the correlation table searching program or the correlation index construction program). The processor1001reads the program from the auxiliary storage device1003, develops the program in the main storage device1002, and executes the above processing according to the program.

Note that, in at least one exemplary embodiment, the auxiliary storage device1003is an example of a non-transitory tangible medium. Other examples of the non-transitory tangible medium include a magnetic disk, a magneto-optical disk, a compact disc read-only memory (CD-ROM), a digital versatile disk (DVD)-ROM, a semiconductor memory, and the like connected via the interface1004. Furthermore, in a case where the program is distributed to the computer1000via a communication line, the computer1000that has received the program may develop the program in the main storage device1002and execute the above processing.

Furthermore, the program may be for implementing some of the functions described above. In addition, the program may be a program that implements the above-described functions in combination with another program already stored in the auxiliary storage device1003, a so-called difference file (difference program).

Some or all of the above exemplary embodiments may be described as the following supplementary notes, but are not limited to the following.

(Supplementary note 1) A correlation table search device including: input means that receives an input of a size-specific correlation index from a storage device that stores the size-specific correlation index, the size-specific correlation index being an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from an external table and being an index that is generated for each size corresponding to a predetermined number from a size-specific vector obtained by extracting, in ascending order, the predetermined number of elements of a feature vector indicating a feature of data of the column, and extracts, from the external table, a column whose distance to the size-specific vector is equal to or less than a distance threshold determined based on the correlation value threshold;index specification means that specifies a size-specific correlation index to be used for searching among the size-specific correlation indexes based on a predetermined threshold of the number of record pairs determined to be couplable when coupling a base table including a target column and the external table;candidate column search means that searches for a column whose distance to the target column is equal to or less than the distance threshold from the external table by using the specified size-specific correlation index, calculates the correlation value indicating a degree of correlation between the found column and the target column, and searches for a column whose correlation value is equal to or larger than the correlation value threshold as a candidate column; and an output unit that outputs an external table including the candidate column.

(Supplementary note 2) The correlation table search device according to Supplementary note 1, in which the index specification means specifies the size-specific correlation index of a largest size with a value equal to or less than the threshold of the number of record pairs.

(Supplementary note 3) A correlation index construction device including correlation index generation means that generates, for each column of an external table, a correlation index that is an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from the external table,in which the correlation index generation means generates a feature vector indicating a feature of each column, generates a standardized vector obtained by standardizing the generated feature vector, generates a size-specific vector obtained by extracting a predetermined number of elements from elements of the generated standardized vector in ascending order, and generates a size-specific correlation index that is a correlation index for each size corresponding to the predetermined number from the generated size-specific vector, andthe correlation index generation means defines a function for calculating the correlation value by using a distance to the size-specific vector, and generates a correlation index for searching for a column of the external table of which the correlation value calculated from a distance between the feature vector of a target column and the size-specific vector is equal to or larger than the correlation value threshold, by using the defined function.

(Supplementary note 4) The correlation index construction device according to Supplementary note 3, further including non-coupling column candidate extraction means that extracts, as a non-coupling column candidate, a column including a record that is assumed not to serve as a key of coupling to another table among external tables included in an external table group,in which the correlation index generation means generates the feature vector indicating a feature of the non-coupling column candidate and generates the correlation index for the non-coupling column candidate.

(Supplementary note 5) The correlation index construction device according to Supplementary note 3 or Supplementary note 4, in which the correlation index generation means determines each size of the size-specific correlation index according to the number of elements of the generated feature vector.

(Supplementary note 6) The correlation index construction device according to any one of Supplementary notes 3 to 5, in which the correlation index generation means determines each size of the size-specific correlation index to be a size corresponding to at least one of a maximum value of the number of elements of the feature vector, a minimum value of the number of elements of the feature vector, or an average value of the number of elements of the feature vector based on the generated feature vector.

(Supplementary note 7) A correlation table searching method executed by a computer, the correlation table searching method including:receiving an input of a size-specific correlation index from a storage device that stores the size-specific correlation index, the size-specific correlation index being an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from an external table and being an index that is generated for each size corresponding to a predetermined number from a size-specific vector obtained by extracting, in ascending order, the predetermined number of elements of a feature vector indicating a feature of data of the column, and extracts, from the external table, a column whose distance to the size-specific vector is equal to or less than a distance threshold determined based on the correlation value threshold;specifying a size-specific correlation index to be used for searching among the size-specific correlation indexes based on a predetermined threshold of the number of record pairs determined to be couplable when coupling a base table including a target column and the external table;searching for a column whose distance to the target column is equal to or less than the distance threshold from the external table by using the specified size-specific correlation index, calculating the correlation value indicating a degree of correlation between the found column and the target column, and searching for a column whose correlation value is equal to or larger than the correlation value threshold as a candidate column; andoutputting an external table including the candidate column.

(Supplementary note 8) A correlation index construction method executed by a computer, the correlation index construction method including:generating a feature vector indicating a feature of each column of an external table, generating a standardized vector obtained by standardizing the generated feature vector, generating a size-specific vector obtained by extracting a predetermined number of elements from elements of the generated standardized vector in ascending order, and generating a size-specific correlation index that is a correlation index for each size corresponding to the predetermined number from the generated size-specific vector, the correlation index being an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from the external table; anddefining a function for calculating the correlation value by using a distance to the size-specific vector, and generating a correlation index for searching for a column of the external table of which the correlation value calculated from a distance between the feature vector of a target column and the size-specific vector is equal to or larger than the correlation value threshold, by using the defined function.

(Supplementary note 9) A program storage medium storing a correlation table searching program for causing a computer to execute:input processing of receiving an input of a size-specific correlation index from a storage device that stores the size-specific correlation index, the size-specific correlation index being an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from an external table and being an index that is generated for each size corresponding to a predetermined number from a size-specific vector obtained by extracting, in ascending order, the predetermined number of elements of a feature vector indicating a feature of data of the column, and extracts, from the external table, a column whose distance to the size-specific vector is equal to or less than a distance threshold determined based on the correlation value threshold;index specification processing of specifying a size-specific correlation index to be used for searching among the size-specific correlation indexes based on a predetermined threshold of the number of record pairs determined to be couplable when coupling a base table including a target column and the external table;candidate column search processing of searching for a column whose distance to the target column is equal to or less than the distance threshold from the external table by using the specified size-specific correlation index, calculating the correlation value indicating a degree of correlation between the found column and the target column, and searching for a column whose correlation value is equal to or larger than the correlation value threshold as a candidate column; andoutput processing of outputting an external table including the candidate column.

(Supplementary note 10) A program storage medium storing a correlation index construction program for causing a computer to execute:correlation index generation processing of generating, for each column of an external table, a correlation index that is an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from the external table,in which in the correlation index generation processing, the computer generates a feature vector indicating a feature of each column, generates a standardized vector obtained by standardizing the generated feature vector, generates a size-specific vector obtained by extracting a predetermined number of elements from elements of the generated standardized vector in ascending order, and generates a size-specific correlation index that is a correlation index for each size corresponding to the predetermined number from the generated size-specific vector, andin the correlation index generation processing, the computer defines a function for calculating the correlation value by using a distance to the size-specific vector, and generates a correlation index for searching for a column of the external table of which the correlation value calculated from a distance between the feature vector of a target column and the size-specific vector is equal to or larger than the correlation value threshold, by using the defined function.

(Supplementary note 11) A correlation table searching program for causing a computer to execute:input processing of receiving an input of a size-specific correlation index from a storage device that stores the size-specific correlation index, the size-specific correlation index being an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from an external table and being an index that is generated for each size corresponding to a predetermined number from a size-specific vector obtained by extracting, in ascending order, the predetermined number of elements of a feature vector indicating a feature of data of the column, and extracts, from the external table, a column whose distance to the size-specific vector is equal to or less than a distance threshold determined based on the correlation value threshold;index specification processing of specifying a size-specific correlation index to be used for searching among the size-specific correlation indexes based on a predetermined threshold of the number of record pairs determined to be couplable when coupling a base table including a target column and the external table;candidate column search processing of searching for a column whose distance to the target column is equal to or less than the distance threshold from the external table by using the specified size-specific correlation index, calculating the correlation value indicating a degree of correlation between the found column and the target column, and searching for a column whose correlation value is equal to or larger than the correlation value threshold as a candidate column; andoutput processing of outputting an external table including the candidate column.

(Supplementary note 12) A correlation index construction program for causing a computer to execute:correlation index generation processing of generating, for each column of an external table, a correlation index that is an index for searching for a column whose correlation value indicating a degree of correlation between columns is equal to or larger than a predetermined correlation value threshold from the external table,in which in the correlation index generation processing, the computer generates a feature vector indicating a feature of each column, generates a standardized vector obtained by standardizing the generated feature vector, generates a size-specific vector obtained by extracting a predetermined number of elements from elements of the generated standardized vector in ascending order, and generates a size-specific correlation index that is a correlation index for each size corresponding to the predetermined number from the generated size-specific vector, andin the correlation index generation processing, the computer defines a function for calculating the correlation value by using a distance to the size-specific vector, and generates a correlation index for searching for a column of the external table of which the correlation value calculated from a distance between the feature vector of a target column and the size-specific vector is equal to or larger than the correlation value threshold, by using the defined function.

Although the present invention has been described above with reference to the exemplary embodiments, the present invention is not limited to the above exemplary embodiments. Various modifications that can be understood by those skilled in the art can be made to the configuration and details of the present invention within the scope of the present invention.

REFERENCE SIGNS LIST