JP6790905B2 - Detection method, detection device and detection program - Google Patents

Description

The present invention relates to a technique for detecting values common to datasets.

LOD (Linked Open Data) is to publish and share data suitable for computer processing on the Web, and RDF (Resource Description Framework) is known as a technology for realizing LOD. In the RDF data model, information about resources on the Web is described in the form of triples containing subjects, predicates and objects.

RDF datasets published on the web may be updated, and work will be required to detect common triples (or differential triples) between the dataset before update and the dataset after update. There is.

For the detection of triples common between two data sets, a technique of finding a join key in a hash join of RDB (Relational DataBase) or the like can be used. However, since the memory usage becomes enormous in hash join, it may not be appropriate to use hash join.

Japanese Unexamined Patent Publication No. 2016-184400 International Publication No. 2013/111287 Japanese Unexamined Patent Publication No. 2013-246828

An object of the present invention is, in one aspect, to provide a technique for detecting triples common to a plurality of data sets at high speed while reducing the amount of storage area used.

The detection method according to one aspect is included in both the first data set and the second data set from the first data set and the second data set including a plurality of triples including a subject, a predicate and an object. Extract a plurality of common predicates and a plurality of common predicates, and extract a triple containing one of the plurality of common predicates and containing any of the plurality of common predicates from each of the first data set and the second data set. Then, the first data in which each of the plurality of common predicates is associated with each of the plurality of common subjects and the set of target words is associated with each of the plurality of common predicates is used as the first data. A first generated from a triple extracted from a data set, each of a plurality of common predicates is associated with each of a plurality of common subjects, and a set of target words is associated with each of the plurality of common predicates. The process of generating the data of 2 from the triple extracted from the second data set and executing the process of generating a code from each of the set of predicates for each of the first data and the second data is included.

On one side, triples common to multiple datasets can be detected at high speed while reducing storage space usage.

FIG. 1 is a functional block diagram of the detection device. FIG. 2 is a diagram showing an example of the data set DA. FIG. 3 is a diagram showing an example of a data set DB. FIG. 4 is a diagram showing a main processing flow. FIG. 5 is a diagram showing a processing flow of the first extraction process. FIG. 6 is a diagram showing an example of a predicate registered in the hash table h1. FIG. 7 is a diagram showing an example of a predicate registered in the hash table h2. FIG. 8 is a diagram showing a processing flow of the second extraction process. FIG. 9 is a diagram showing an example of the subject registered in the hash table h3. FIG. 10 is a diagram showing an example of a subject registered in the hash table h4. FIG. 11 is a diagram showing a processing flow of the generation process. FIG. 12 is a diagram showing an example of the table t. FIG. 13 is a diagram showing an example of the hash table hp. FIG. 14 is a diagram showing triples to be processed. FIG. 15 is a diagram showing a processing flow of the generation process. FIG. 16 is a diagram showing an example of the table t. FIG. 17 is a diagram showing an example of the table ta. FIG. 18 is a diagram showing an example of the table tb. FIG. 19 is a diagram showing a processing flow of comparison processing. FIG. 20 is a diagram showing an example of a common triple. FIG. 21 is a diagram showing an example of a common triple. FIG. 22 is a diagram showing an example of a common triple. FIG. 23 is a diagram for explaining a hash join. FIG. 24 is a diagram for explaining a sort merge join. FIG. 25 is a diagram for explaining a nested loop coupling. FIG. 26 is a functional block diagram of the computer.

FIG. 1 shows a functional block diagram of the detection device 1 of the present embodiment. For example, the detection device 1 such as a personal computer or a server includes a first extraction unit 101, a second extraction unit 103, a generation unit 105, a comparison unit 107, a data set storage unit 111, and a common predicate storage unit 113. , The common subject storage unit 115, the table storage unit 117, and the common triple storage unit 119.

The first extraction unit 101, the second extraction unit 103, the generation unit 105, and the comparison unit 107 are realized by executing the program loaded in the memory 2501 in FIG. 26 by the CPU (Central Processing Unit) in FIG. 26. .. The data set storage unit 111, the common predicate storage unit 113, the common subject storage unit 115, the table storage unit 117, and the common triple storage unit 119 are provided in the memory 2501 or the HDD (Hard Disk Drive) 2505 in FIG. 26.

The first extraction unit 101 executes processing based on the data set stored in the data set storage unit 111, and stores the processing result in the common predicate storage unit 113. The second extraction unit 103 executes processing based on the data set stored in the data set storage unit 111 and the data stored in the common predicate storage unit 113, and stores the processing result in the common subject storage unit 115. The generation unit 105 executes processing based on the data set stored in the data set storage unit 111, the data stored in the common predicate storage unit 113, and the data stored in the common subject storage unit 115, and the processing result is obtained. Is stored in the table storage unit 117. The comparison unit 107 executes processing based on the data stored in the table storage unit 117, and stores the processing result in the common triple storage unit 119.

According to the present embodiment described below, a common triple can be found for a plurality of data sets (for example, a plurality of data sets having different versions) with a smaller amount of time calculation. Here, it is assumed that the dataset has the following characteristics.
(1) The number of types of triples is very large (for example, billions)
(2) The number of types of predicates is small (at most 100)
(3) The number of digits of the number of types of subject and the number of types of object is several orders of magnitude smaller than the number of digits of the number of types of triple.

The above features (1) to (3) are features of general RDF data, and are not assumed to be a particularly characteristic data set.

In addition, when changing the version of the data set, it is assumed that the following changes are made.
(4) Some subjects are added or deleted (the number of subjects does not more than double)
(5) Some predicates may be added or deleted (the number of predicates will not more than double)
(6) Some objects are added or deleted (because of the difference between versions, some of the objects are changed)

The above features (4) to (6) are general as features of changing the version of RDF data, and it is not assumed that a particularly characteristic change is made.

In order to simplify the explanation, the data set shown in FIG. 2 (referred to as data set DA) and the data set shown in FIG. 3 (referred to as data set DB) will be described below as examples. Comparing the dataset DA and the dataset DB, five triples ((s1, p1, o1), (s1, p2, o2), (s1, p2, o3), (s2, p1, o4), (s2) , P2, o5)) are common.

The process executed by the detection device 1 will be described with reference to FIGS. 4 to 21.

First, the first extraction unit 101 executes the first extraction process (FIG. 4: step S1). The first extraction process will be described with reference to FIGS. 5 to 7.

First, the first extraction unit 101 initializes the hash tables h1 and h2 in the memory 2501 (for example, clears the values if they are registered) (FIG. 5: step S21).

The first extraction unit 101 identifies one unprocessed triple from the data set DA stored in the data set storage unit 111 (step S23).

When the same predicate as the predicate included in the triple specified in step S23 is not registered in the hash table h1, the first extraction unit 101 registers the predicate included in the triple specified in step S23 in the hash table h1 (step). S25). By the process of step S25, each of the predicates registered in the hash table h1 becomes unique in the hash table h1. That is, a plurality of predicates of the same type are not registered in the hash table h1. Predicates are registered in the hash table h1 as shown in FIG.

The first extraction unit 101 determines whether the data set DA has an unprocessed triple (step S27). If there are unprocessed triples (step S27: Yes route), processing returns to step S23.

On the other hand, when there is no unprocessed triple (step S27: No route), the first extraction unit 101 identifies one unprocessed triple from the data set DB stored in the data set storage unit 111 (step S29). ).

When the same predicate as the predicate included in the triple specified in step S29 is registered in the hash table h1 and is not registered in the hash table h2, the first extraction unit 101 includes the predicate included in the triple specified in step S29. Is registered in the hash table h2 (step S31). By the process of step S31, each of the predicates registered in the hash table h2 becomes unique in the hash table h2. Predicates are registered in the hash table h2 as shown in FIG.

The first extraction unit 101 determines whether or not there are unprocessed triples in the data set DB (step S33). If there are unprocessed triples (step S33: Yes route), processing returns to step S29. On the other hand, when there is no unprocessed triple (step S33: No route), the first extraction unit 101 stores the hash table h2 as the hash table hp in the common predicate storage unit 113. Then the process returns to the caller.

By executing the above processing, a predicate common to the dataset DA and the dataset DB (hereinafter referred to as a common predicate) can be extracted.

Returning to the description of FIG. 4, the second extraction unit 103 executes the second extraction process (step S3). The second extraction process will be described with reference to FIGS. 8 to 10.

First, the second extraction unit 103 initializes the hash tables h3 and h4 in the memory 2501 (FIG. 8: step S41).

The second extraction unit 103 identifies one unprocessed triple from the dataset DA (step S43).

In the second extraction unit 103, the same predicate as the predicate included in the triple specified in step S43 is registered in the hash table hp, and the same subject as the subject included in the triple specified in step S43 is registered in the hash table h3. If not, the subject included in the triple specified in step S43 is registered in the hash table h3 (step S45). By the process of step S45, each of the subjects registered in the hash table h3 becomes unique in the hash table h3. The subject is registered in the hash table h3 as shown in FIG.

The second extraction unit 103 determines whether the data set DA has unprocessed triples (step S47). If there are unprocessed triples (step S47: Yes route), processing returns to step S43.

On the other hand, when there is no unprocessed triple (step S47: No route), the second extraction unit 103 identifies one unprocessed triple from the data set DB (step S49).

In the second extraction unit 103, the same predicate as the predicate included in the triple specified in step S49 is registered in the hash table hp, and the same subject as the subject included in the triple specified in step S49 is registered in the hash table h3. If the same subject as the subject included in the triple specified in step S49 is not registered in the hash table h4, the subject included in the triple specified in step S49 is registered in the hash table h4 (step S51). By the process of step S51, each of the subjects registered in the hash table h4 becomes unique in the hash table h4. The subject is registered in the hash table h4 as shown in FIG.

The second extraction unit 103 determines whether or not there are unprocessed triples in the data set DB (step S53). If there are unprocessed triples (step S53: Yes route), processing returns to step S49. On the other hand, when there is no unprocessed triple (step S53: No route), the second extraction unit 103 stores the hash table h4 as the hash table hs in the common subject storage unit 115. Then the process returns to the caller.

By executing the above processing, the subject (hereinafter referred to as the common subject) that is the subject common to the dataset DA and the dataset DB and is included in the triple containing the common predicate can be extracted. Become.

Returning to the description of FIG. 4, the generation unit 105 identifies one unprocessed data set from the data set DA and the data set DB (step S5). Then, the generation unit 105 executes the generation process for the data set specified in step S5 (step S7). The generation process will be described with reference to FIGS. 11 to 18.

First, the generation unit 105 uses the number of elements of the hash table hs stored in the common subject storage unit 115 (that is, the number of common subjects) as the number of rows and the number of elements of the hash table hp stored in the common predicate storage unit 113. Initialize in the memory 2501 a table t whose number of columns is the number obtained by adding 1 to twice the number of common predicates (that is, FIG. 11: step S61).

The generation unit 105 sets each common subject registered in the hash table hs in the first column of the table t (step S63). By the processing up to this point, data is stored in the table t, for example, as shown in FIG.

The generation unit 105 stores the serial number n starting from 0 in the common predicate storage unit 113 in association with the elements of the hash table hp (step S65). By the processing of step S65, the format of the hash table hp becomes as shown in FIG. 13, for example.

The generation unit 105 generates an index (for example, B-tree) for the first column (that is, the common subject) of the table t (step S67). The generated index is used, for example, in step S89.

The generation unit 105 identifies one unprocessed triple from the dataset identified in step S5 (step S69).

The generation unit 105 determines whether the subject included in the triple specified in step S69 is registered in the hash table hs and the predicate included in the triple specified in step S69 is registered in the hash table hp (step S71).

If the subject included in the triple specified in step S69 is not registered in the hash table hs, or the predicate included in the triple specified in step S69 is not registered in the hash table hp (step S71: No route), the process Goes to step S77.

Triples other than triples containing both a common subject and a common predicate are excluded from the processing of steps S73 and S75 by the processing of step S71. For example, in the case of the data set DA, as shown in FIG. 14, the triple in the fourth row and the triple in the eighth row are excluded from the processing of steps S73 and S75.

On the other hand, when the subject included in the triple specified in step S69 is registered in the hash table hs and the predicate included in the triple specified in step S69 is registered in the hash table hp (step S71: Yes root), the generation unit. 105 executes the following processing. Specifically, the generation unit 105 acquires n corresponding to the predicate included in the triple specified in step S69 from the hash table hp (step S73).

The generation unit 105 registers the object included in the triple specified in step S69 in the (n * 2 + 3) column of the row in which the subject included in the triple specified in step S69 is included in the first column (step S75). ).

The generation unit 105 determines whether the data set specified in step S5 has an unprocessed triple (step S77). If there are unprocessed triples (step S77: Yes route), processing returns to step S69. On the other hand, when there is no unprocessed triple (step S77: No route), the process proceeds to step S79 of FIG. 15 via the terminal A.

Moving on to the description of FIG. 15, the generation unit 105 identifies one unprocessed row from the table t (FIG. 15: step S79).

The generation unit 105 sets the types of objects registered in the (m * 2 + 3) column in the row specified in step S79 for each value of m (m = 0, 1, 2, ..., M). Is specified (step S81). M corresponds to the number of common predicates minus one. Since there is a possibility that duplicate objects are registered according to the processing up to step S77, a set of object types (that is, a set of unique objects) is specified.

The generation unit 105 sorts the objects in the specified set for each value of m and generates a checksum (step S83). In step S83, a code other than the checksum may be generated.

The generation unit 105 registers a checksum in the (m * 2 + 2) column for each value of m (step S85). By the processing up to step S85, for example, the table t as shown in FIG. 16 is generated.

The generation unit 105 determines whether or not there are unprocessed rows in the table t (step S87). If there are unprocessed rows in the table t (step S87: Yes route), the process returns to step S79.

On the other hand, when there are no unprocessed rows in the table t (step S87: No route), the generation unit 105 sorts the rows in the table t based on the values in the first column of the table t (step S89). In step S89, for example, sorting is performed so that the common subjects in the first column are in lexicographic order. And the process ends.

When the process of step S89 is executed, the table t shown in FIG. 16 is updated to the table t shown in FIG. Further, when the generation process is executed for the data set DB, for example, the table t shown in FIG. 18 is generated. In the following, the table t generated for the dataset DA will be referred to as the table ta, and the table t generated for the dataset DB will be referred to as the table tb. The generation unit 105 stores the table ta and the table tb in the table storage unit 117.

When the comparison process described below is executed by the same method as the nested loop join instead of the sort merge join, the process in step S89 may be omitted.

As described above, by converting the set of triples including both the common subject and the common predicate into the data for each common subject, the comparison process to be executed later can be executed at high speed.

Returning to the description of FIG. 4, the generation unit 105 determines whether there is an unprocessed data set among the data set DA and the data set DB (step S9). If there is an unprocessed data set among the data set DA and the data set DB (step S9: Yes route), the process returns to step S5.

On the other hand, when there is no unprocessed data set in the data set DA and the data set DB (step S9: No route), the comparison unit 107 executes the comparison process (step S11). The comparison process will be described with reference to FIGS. 19 to 22.

First, the comparison unit 107 sets the variable α representing the row number of the table ta to 0 and sets the variable β representing the row number of the table tb to 0 (FIG. 19: step S91).

The comparison unit 107 reads the table ta from the table storage unit 117. Then, the comparison unit 107 determines whether α is larger than the number of rows in the table ta (step S93). When α is larger than the number of rows in the table ta (step S93: Yes route), the process returns to the caller and ends.

When α is not larger than the number of rows in the table ta (step S93: No route), the comparison unit 107 reads the table tb from the table storage unit 117. Then, the comparison unit 107 determines whether β is larger than the number of rows in the table tb (step S95). If β is larger than the number of rows in table tb (step S95: Yes route), the process returns to the caller and ends.

When β is not larger than the number of rows in the table tb (step S95: No route), the comparison unit 107 has the same first column in the α row of the table ta and the first column in the β row of the table tb. (Step S97).

When the first column of the α-th row of the table ta and the first column of the β-th row of the table tb are not the same (step S97: No route), the comparison unit 107 executes the following processing. Specifically, the comparison unit 107 increments β by 1 when the α-th row of the table ta is later than the β-th row of the table tb in the lexical order, and the β-th row of the table tb is the α of the table ta. If it is later in the lexical order than the line, α is incremented by 1 (step S99). Then, the process returns to step S93. The processing of steps S91 to S99 is based on the sort-merge join.

On the other hand, when the first column of the α-th row of the table ta and the first column of the β-th row of the table tb are the same (step S97: Yes route), the comparison unit 107 executes the following processing. Specifically, the comparison unit 107 sets the checksum of the αth row (m * 2 + 2) column of the table ta for each value of m (m = 0, 1, 2, ..., M). Compare with the checksum in the βth row (m * 2 + 2) column of the table tb (step S101).

When the checksum in the α-th row (m * 2 + 2) column of the table ta and the checksum in the β-th row (m * 2 + 2) column of the table tb are the same (step S103: Yes route). The comparison unit 107 executes the following processing. Specifically, the comparison unit 107 checks each of the objects in the (m * 2 + 3) column of the αth row (or the βth row of the table tb) of the table ta and the (m * 2 + 2) column. A triple including the common predicate corresponding to the sum and the common subject in the first column is stored in the common triple storage unit 119 (step S105). Then, the process returns to step S93.

On the other hand, when the checksum in the αth row (m * 2 + 2) column of the table ta and the checksum in the βth row (m * 2 + 2) column of the table tb are not the same (step S103: No route). ), The comparison unit 107 executes the following processing. Specifically, the comparison unit 107 includes each of the objects in the α-th row (m * 2 + 3) column of the table ta and each of the objects in the β-th row (m * 2 + 3) column of the table tb. Compare with. Then, when the objects match, the comparison unit 107 includes a triple including the matched object, the common predicate corresponding to the checksum in the (m * 2 + 2) column, and the common subject in the first column. , Stored in the common triple storage unit 119 (step S107). Then, the process returns to step S93.

For example, when the table ta shown in FIG. 17 and the table tb shown in FIG. 18 are targeted, in step S103, the subject is s1 and the predicate is p1, and the subject is s1 and the predicate is. It is determined that the checksums match when the subject is p2 and when the subject is s2 and the predicate is p1. Therefore, in step S105, as shown in FIG. 20, a triple in which the subject is s1 and the predicate is p1 and the object is o1, and the subject is s1 and the predicate is p2 and the object is A common triple is a triple that is o2, a triple that has a subject of s1 and a predicate of p2 and an object of o3, and a triple that has a subject of s2 and a predicate of p1 and an object of o4. It is stored in the storage unit 119. Further, in step S103, when the subject is s2 and the predicate is p2, it is determined that the checksums do not match, but in step S107, it is determined that the object o5 matches. Therefore, as shown in FIG. 21, a triple having a subject of s2, a predicate of p2, and an object of o5 is stored in the common triple storage unit 119. Therefore, finally, the five triples shown in FIG. 22 are stored in the common triple storage unit 119.

The triple stored in the common triple storage unit 119 is displayed on the display device of the detection device 1, for example, and is confirmed by the user.

As described above, in the present embodiment, the data sets are put together with a common subject, and the comparison between the objects is avoided as much as possible by comparing the checksums. Therefore, a common triple. Can be detected at high speed. Further, by holding the intermediate data in the format of the table t, the amount of the storage area used can be reduced as compared with the case where the hash join or the like is executed.

It should be noted that the fact that the version change of the data set has the characteristics of (4) to (6) means that the difference between the data sets is slight, and in such a case, there are many checksums before and after the change. The same is true for. Therefore, there is a high possibility that comparison between objects can be avoided.

Here, the comparison result between the processing time when the processing of the present embodiment is executed and the processing time when the normal sort merge join is executed is shown.

As a premise, the number of types of triples contained in the target data set is 1,159,975,820, the number of types of subject is 58,841,774, the number of types of predicate is 68,894, and the purpose is It is assumed that the number of types of words is 232,911,608. Further, since the processing in which the time calculation amount is in the linear order and the processing in which the input data amount is large have a large influence on the execution time, only these processings are targeted for time measurement. Specifically, in the case of the present embodiment, the process of sorting the subject of the data set is targeted, and in the case of the normal sort merge join, the process of sorting the triples of the data set is targeted.

Then, a dataset having the same number of rows as the number of triple types and a dataset having the same number of rows as the number of subject types are created, and the amount of memory available for the created dataset is set to 1 gigabyte for GNU sorting. It is assumed that the processing time when is executed is measured.

In this case, it takes 26 minutes 57 seconds to sort a dataset that has the same number of rows as the number of triple types, whereas it takes 26 minutes 57 seconds to sort a dataset that has the same number of rows as the number of subject types. The time was 49 seconds. Therefore, it was confirmed that the time required for sorting can be significantly shortened by executing the process of the present embodiment.

Although one embodiment of the present invention has been described above, the present invention is not limited thereto. For example, the functional block configuration of the detection device 1 described above may not match the actual program module configuration.

Further, the configuration of each table described above is an example, and does not have to be the configuration as described above. Further, also in the processing flow, it is possible to change the order of processing if the processing result does not change. Further, it may be executed in parallel.

Further, the comparison process may be executed in the same manner as the nested loop join instead of the sort merge join.

[appendix]
This appendix describes the process of identifying common records using hash joins, sort merge joins, and nested loop joins.

1. 1. Hash Join FIG. 23 is a diagram for explaining a hash join. In the example shown in FIG. 23, a common triple is extracted between the dataset T1 and the dataset T2. In the hash table, the hash value calculated by the hash function from the values of the comparison target column (column 1, column 2 and column 3 in this example) of the data set T1 and the value of the comparison target column are registered. Then, while referring to the hash table, it is confirmed whether the comparison target column of each record of the data set T2 matches the record of the data set T1.

2. 2. Sort-Merge Join FIG. 24 is a diagram for explaining a sort-merge join. In a sort-merge join, the records in each dataset are first sorted. In the example shown in FIG. 24, the comparison target columns are column 1, column 2, and column 3, and the value of the first record of the data set T1 and the value of the first record of the data set T2 are first compared. If they are equal, they are extracted as common records. If the value of the first record of dataset T1 is greater than the value of the first record of dataset T2 (or later in lexical order), then the value of the next record of dataset T2 and the first of dataset T1 The value of the record is compared. Conversely, if the value of the first record in dataset T1 is less than the value of the first record in dataset T2 (or is earlier in lexical order), then the value of the next record in dataset T1 and dataset T2 The value of the first record of is compared. The above process is repeated.

3. 3. Nested Loop Coupling FIG. 25 is a diagram for explaining a nested loop coupling. In the example shown in FIG. 25, the value of the comparison target column (here, column 1, column 2 and column 3) of the first record in the data set T1 and the value of the comparison target column of each record in the data set T2. Are compared. By executing this process from the second record to the last record in the data set T1, a common record is extracted.

This is the end of the appendix.

The detection device 1 described above is a computer device, and as shown in FIG. 26, is a drive for the memory 2501, the CPU 2503, the HDD 2505, the display control unit 2507 connected to the display device 2509, and the removable disk 2511. The device 2513, the input device 2515, and the communication control unit 2517 for connecting to the network are connected by a bus 2519. The operating system (OS: Operating System) and the application program for executing the processing in this embodiment are stored in the HDD 2505, and are read from the HDD 2505 to the memory 2501 when executed by the CPU 2503. The CPU 2503 controls the display control unit 2507, the communication control unit 2517, and the drive device 2513 according to the processing contents of the application program to perform a predetermined operation. Further, although the data in the process of processing is mainly stored in the memory 2501, it may be stored in the HDD 2505. In the embodiment of the present invention, the application program for performing the above-described processing is stored and distributed on the computer-readable removable disk 2511 and installed from the drive device 2513 to the HDD 2505. It may be installed on the HDD 2505 via a network such as the Internet and a communication control unit 2517. Such a computer device realizes various functions as described above by organically collaborating with the hardware such as the CPU 2503 and the memory 2501 described above and the program such as the OS and the application program. ..

The embodiments of the present invention described above can be summarized as follows.

The detection method according to the first aspect of the present embodiment is (A) from the first data set and the second data set including a plurality of triples including a subject, a predicate, and an object, the first data set and the first data set. A plurality of common predicates and a plurality of common predicates included in any of the two data sets are extracted, and (B) a triple containing any of the plurality of common predicates and containing any of the plurality of common predicates is obtained. Extracted from each of the data set and the second data set, (C) each of the plurality of common predicates is associated with each of the plurality of common subjects, and the object is associated with each of the plurality of common predicates. The first data to which the set of is associated is generated from the triple extracted from the first dataset, and (D) each of the plurality of common predicates is associated with each of the plurality of common subject and the relevant The second data in which the set of target words is associated with each of the plurality of common predicates is generated from the triple extracted from the second dataset, and (E) the first data and the second data. For each, it includes a process of executing a process of generating a code from each of the set of predicates.

Triples common to multiple data sets can be detected at high speed while reducing the amount of storage space used.

Further, this detection method is used to compare (F) a code generated from each of the sets of target words included in the first data with a code generated from each of the sets of target words included in the second data. Based on this, a process of extracting triples contained in both the first data set and the second data set may be further included.

Since it is not necessary to compare the objects, it is possible to prevent the detection time from becoming long even when the number of objects is large.

Further, in the process of extracting triples included in both the first data set and the second data set, (f1) a code generated from the first set of objects included in the first data and a code. When the code generated from the second set of objects included in the second data is the same, each object included in the first set or the second set and the common subject corresponding to the object. And a triple containing a common predicate is extracted, and (f2) a code generated from a third set of objects contained in the first data and a fourth set of objects contained in the second data are generated. If the codes are not the same, the first data set and the second data set are based on the comparison between each object contained in the third set and each object contained in the fourth set. Triples contained in any of them may be extracted.

Since the comparison between the objects is performed only when the symbols are not the same, it is possible to suppress a long time required for detection.

Further, in the process of extracting a plurality of common subjects and a plurality of common predicates, (a1) a plurality of common predicates that are predicates included in the second dataset among the plurality of predicates included in the first dataset are extracted. Then, (a2), among the triples contained in the second data set, the triples containing the same predicate as any of the extracted common predicates and the same subject as the subject contained in the first data set are specified. , A plurality of common subjects that are the subjects included in the specified triple may be extracted.

Further, the code generated from the set of objects may be a checksum.

The detection device according to the second aspect of the present embodiment is the first data set and the second data set from the first data set and the second data set including a plurality of triples including the (G) predicate and the object. An extraction unit (for example, the first extraction unit 101 and the second extraction unit 103) that extracts a plurality of common subjects and a plurality of common predicates included in any of the data sets, and (H) one of the plurality of common subjects. A triple containing and containing any one of the plurality of common predicates is extracted from each of the first data set and the second data set, and each of the plurality of common predicates is associated with each of the plurality of common subjects. Moreover, the first data in which the set of the object words is associated with each of the plurality of common predicates is generated from the triple extracted from the first data set, and a plurality of data are generated for each of the plurality of common subjects. Second data, in which each of the common predicates is associated and a set of objectives is associated with each of the plurality of common predicates, is generated from the triple extracted from the second dataset, and the first Each of the data and the second data has a generation unit (for example, a generation unit 105) that executes a process of generating a code from each of the set of predicates.

A program for causing a computer to execute the processing by the above method can be created, and the program can be a computer-readable storage medium such as a flexible disk, a CD-ROM, a magneto-optical disk, a semiconductor memory, or a hard disk. Stored in storage. The intermediate processing result is temporarily stored in a storage device such as a main memory.

The following additional notes will be further disclosed with respect to the embodiments including the above embodiments.

(Appendix 1)
On the computer
From the first dataset and the second dataset containing a plurality of triples containing a subject, a predicate, and an object, a plurality of common subjects and a plurality of common subjects included in both the first dataset and the second dataset. Extract the common predicate of
A triple containing any of the plurality of common subjects and containing any of the plurality of common predicates is extracted from each of the first data set and the second data set.
The first data in which each of the plurality of common predicates is associated with each of the plurality of common subjects and a set of objects is associated with each of the plurality of common predicates is obtained from the first data. Generated from triples extracted from the dataset of
The second data in which each of the plurality of common predicates is associated with each of the plurality of common subjects and a set of objects is associated with each of the plurality of common predicates is obtained. Generated from triples extracted from the dataset of
For each of the first data and the second data, a process of generating a code from each of the set of objects is executed.
A detection program that executes processing.

(Appendix 2)
On the computer
The first data set is based on a comparison between the codes generated from each of the sets of objects included in the first data and the codes generated from each of the sets of objects included in the second data. And the triples contained in both of the second dataset,
The detection program according to Appendix 1 for further executing the process.

(Appendix 3)
In the process of extracting triples contained in both the first data set and the second data set,
When the code generated from the first set of objects included in the first data and the code generated from the second set of objects included in the second data are the same, the first A triple containing a set or each object included in the second set and a common subject and a common predicate corresponding to the object is extracted.
When the code generated from the third set of target words included in the first data and the code generated from the fourth set of target words included in the second data are not the same, the third set is described. Based on the comparison between each object included in the set of and each object included in the fourth set, triples included in both the first data set and the second data set are extracted. To do
The detection program described in Appendix 2.

(Appendix 4)
In the process of extracting the plurality of common subjects and the plurality of common predicates,
From the plurality of predicates included in the first dataset, the plurality of common predicates that are predicates included in the second dataset are extracted.
Among the triples included in the second dataset, the triples containing the same predicate as any of the extracted common predicates and the same subject as the subject included in the first dataset are identified and specified. Extract the plurality of common subjects that are the subjects included in the triple.
The detection program according to any one of Supplementary notes 1 to 3.

(Appendix 5)
The code generated from the set of objects is a checksum,
The detection program according to any one of Supplementary notes 1 to 4.

(Appendix 6)
The computer
From the first dataset and the second dataset containing a plurality of triples containing a subject, a predicate, and an object, a plurality of common subjects and a plurality of common subjects included in both the first dataset and the second dataset. Extract the common predicate of
A triple containing any of the plurality of common subjects and containing any of the plurality of common predicates is extracted from each of the first data set and the second data set.
The first data in which each of the plurality of common predicates is associated with each of the plurality of common subjects and a set of objects is associated with each of the plurality of common predicates is obtained from the first data. Generated from triples extracted from the dataset of
The second data in which each of the plurality of common predicates is associated with each of the plurality of common subjects and a set of objects is associated with each of the plurality of common predicates is obtained. Generated from triples extracted from the dataset of
For each of the first data and the second data, a process of generating a code from each of the set of objects is executed.
A detection method that performs processing.

(Appendix 7)
From the first dataset and the second dataset containing a plurality of triples containing a subject, a predicate, and an object, a plurality of common subjects and a plurality of common subjects included in both the first dataset and the second dataset. And the extraction part that extracts the common predicate of
A triple containing any of the plurality of common subjects and containing any of the plurality of common predicates is extracted from each of the first data set and the second data set, and each of the plurality of common subjects. A triple obtained from the first data set, the first data in which each of the plurality of common predicates is associated with the data and a set of target words is associated with each of the plurality of common predicates. Second data generated from, each of the plurality of common predicates is associated with each of the plurality of common subjects, and a set of target words is associated with each of the plurality of common predicates. , A generation unit that generates a code from each of the set of predicates for each of the first data and the second data, which is generated from the triple extracted from the second data set.
Detection device having.

1 Detection device 101 1st extraction unit 103 2nd extraction unit 105 Generation unit 107 Comparison unit 111 Data set storage unit 113 Common predicate storage unit 115 Common subject storage unit 117 Table storage unit 119 Common triple storage unit

Claims (6)

On the computer
From the first dataset and the second dataset containing a plurality of triples containing a subject, a predicate, and an object, a plurality of common subjects and a plurality of common subjects included in both the first dataset and the second dataset. Extract the common predicate of
A triple containing any of the plurality of common subjects and containing any of the plurality of common predicates is extracted from each of the first data set and the second data set.
The first data in which each of the plurality of common predicates is associated with each of the plurality of common subjects and a set of objects is associated with each of the plurality of common predicates is obtained from the first data. Generated from triples extracted from the dataset of
The second data in which each of the plurality of common predicates is associated with each of the plurality of common subjects and a set of objects is associated with each of the plurality of common predicates is obtained. Generated from triples extracted from the dataset of
For each of the first data and the second data, a process of generating a code from each of the set of objects is executed.
A detection program that executes processing. On the computer
The first data set is based on a comparison between the codes generated from each of the sets of objects included in the first data and the codes generated from each of the sets of objects included in the second data. And the triples contained in both of the second dataset,
The detection program according to claim 1, wherein the processing is further executed. In the process of extracting triples contained in both the first data set and the second data set,
When the code generated from the first set of objects included in the first data and the code generated from the second set of objects included in the second data are the same, the first A triple containing a set or each object included in the second set and a common subject and a common predicate corresponding to the object is extracted.
When the code generated from the third set of target words included in the first data and the code generated from the fourth set of target words included in the second data are not the same, the third set is described. Based on the comparison between each object included in the set of and each object included in the fourth set, triples included in both the first data set and the second data set are extracted. To do
The detection program according to claim 2. In the process of extracting the plurality of common subjects and the plurality of common predicates,
From the plurality of predicates included in the first data set, the plurality of common predicates that are predicates included in the second data set are extracted.
Among the triples included in the second dataset, the triples containing the same predicate as any of the extracted common predicates and the same subject as the subject included in the first dataset are identified and specified. Extract the plurality of common subjects that are the subjects included in the triple.
The detection program according to any one of claims 1 to 3. The computer
From the first dataset and the second dataset containing a plurality of triples containing a subject, a predicate, and an object, a plurality of common subjects and a plurality of common subjects included in both the first dataset and the second dataset. Extract the common predicate of
A triple containing any of the plurality of common subjects and containing any of the plurality of common predicates is extracted from each of the first data set and the second data set.
The first data in which each of the plurality of common predicates is associated with each of the plurality of common subjects and a set of objects is associated with each of the plurality of common predicates is obtained from the first data. Generated from triples extracted from the dataset of
The second data in which each of the plurality of common predicates is associated with each of the plurality of common subjects and a set of objects is associated with each of the plurality of common predicates is obtained. Generated from triples extracted from the dataset of
For each of the first data and the second data, a process of generating a code from each of the set of objects is executed.
A detection method that performs processing. From the first dataset and the second dataset containing a plurality of triples containing a subject, a predicate, and an object, a plurality of common subjects and a plurality of common subjects included in both the first dataset and the second dataset. And the extraction part that extracts the common predicate of
A triple containing any of the plurality of common subjects and containing any of the plurality of common predicates is extracted from each of the first data set and the second data set, and each of the plurality of common subjects. A triple obtained from the first data set, the first data in which each of the plurality of common predicates is associated with the data and a set of target words is associated with each of the plurality of common predicates. Second data generated from, each of the plurality of common predicates is associated with each of the plurality of common subjects, and a set of target words is associated with each of the plurality of common predicates. , A generation unit that generates a code from each of the set of predicates for each of the first data and the second data, which is generated from the triple extracted from the second data set.
Detection device having.

Images