JPH0378666B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Application of the Invention] The present invention relates to a data selection method for selecting only data whose data contents match each other from two data groups.

[Prior art]

In the field of data management systems, there is often a need to extract and combine data whose data contents match each other from two data groups. In this case, if each data group has a large amount of data and requires a long time to combine, a data selection operation is used in which data that cannot be combined is removed from each data group in advance to shorten the combination time. FIG. 1 is a diagram explaining the principle of such a data sorting method, where 1 and 2 are data groups, 4 is a hashing device with a predetermined hashing function, 6 is a bit array device with a finite bit array, and 8 is a This is a selected data group. The operation begins with bit array device 6.
After setting all bits of the bit array to "0", execute operation 11 to hash the data contents of the data group 1 with the hashing device 4 and convert it into a value corresponding to the address space of the bit array device 6.
Set "1" to the bit position of the bit array whose address is that value. Next, when this operation 11 is completed, operation 13 is executed, and the data contents of data group 2 are similarly hashed by the hashing device 4, and the bit position of the bit array device 4, which uses this value as an address, is "1". Data 8 is obtained by selecting only the data. FIG. 1 shows that, for example, if data group 1 is "ABDDFG" and data group 2 is "AACDEFFH", "AADFF" is obtained as the selected data group 8. FIG. 2 is a time chart of the operation of FIG.

In Figure 1, there are cases where the sorted data of only one data group is obtained, but in reality two data groups 1 and 2 are obtained.
In many cases, screening data with matching data content is required for each. In such cases, conventionally, a data selection method shown in FIG. 3 has been used.

In Fig. 3, 1 and 2 are data groups, 3 and 4 are hashing devices with the same hashing function, 5 and 6 are bit array devices with finite bit arrays,
7 and 8 are selected data groups. In the operation, after setting all the bits in each bit array of the bit array devices 3 and 4 to "0", first execute operation 11, and then hash the data contents of data group 1 with the hashing device 4 as explained in FIG. Then, "1" is set in the bit position of the bit array device 4 whose address is that value. Next, operations 12 and 13 are executed simultaneously. Here, operation 12 is data group 2
This is an operation of hashing the data contents in the hashing device 3 and setting "1" to the bit position of the bit array device 3, which uses the value as an address.
3 is a hashing device 4 for data contents of the same data group 2.
This is an operation in which data 8 is obtained by hashing the data and selecting only the data whose bit position in the bit array device 6 is "1", using that value as the address. After operations 12 and 13 are completed, operation 14 is executed, and the data contents of data group 1 are again hashed by hashing device 3, and the data whose bit position in bit array device 5 is “1” with the value as the address is Data 7 is obtained by selecting only those. In Figure 3, data group 1
“ABDDFG” and data group 2 “ACDEFFH”
In this case, the selection data 7 indicates "ADDF" and the selection data 8 indicates "AADFF".

FIG. 4 shows a time chart of the operation of FIG. 3. As can be seen from this, the conventional data sorting method shown in FIG. 3 has the disadvantage that the processing time is long because the processing is performed sequentially in three stages.

[Purpose of the invention]

An object of the present invention is to provide a data selection method that can shorten the time required for the entire data selection compared to the conventional method.

[Summary of the invention]

The key point of the present invention is that in the data selection method shown in FIG. The aim is to shorten the overall time required.

[Embodiments of the invention]

FIG. 5 is a diagram for explaining the operation of the data selection method of the present invention, and is basically the same as FIG. 3. A time chart of the operation according to the invention is shown in FIG.
Here, FIG. 6 shows an example where the amount of data in data group 1 is smaller than that in data group 2. This example will be explained below.

In operation, all bits in the bit arrays of the bit array devices 5 and 6 are first set to "0". Next, operations 11 and 12 are performed simultaneously on data groups 1 and 2, starting from the first data of each data group. The contents of operations 11 and 12 are the same as in FIG. Here, since it is assumed that the data amount of data groups 1 and 2 is smaller in data group 1, even if operation 11 is completed, operation 12 is not completed yet. This operation 1
When step 1 is finished, continue step 12,
At the same time, the data of data group 2 used in operation 12 is also input to the hashing device 4, and operation 13 is started. After that, when operation 12 is completed, operation 14 is performed on data group 1 from the first data of data group 1, but data group 2 has not yet been subjected to operation 13 from the first data. Operation 13 is performed for the data. Operation 1
The contents of 3 and 14 are also the same as in FIG. As shown in Figure 5, when data group 1 is set to "ABDDFG" and data group 2 is set to "AACDEFFH", the contents of selection data 7 and 8 are the same as those shown in Figure 3, but this In the operation of the invention, the screening data 8 is obtained in the order of "FAADF".

Here, the conventional method shown in FIG. 3 and the method of the present invention will be compared. Now, let the numbers of data in the two data groups 1 and 2 be n and m (nm), respectively, and the time required for operations 11 and 12 on one data is d _s , operation 13,
Let the time required for 14 be d _r . From Figure 4, the third
The total processing time using the method shown in the figure is d _so + max (d _s , d _r ) m + d _r

Claims (1)

[Claims] 1. In order to select data whose data contents match each other between two data groups, two sets of bit arrays and hashing devices are provided, and the data contents of one data group are hashed by the hashing device of the other set. , "1" (or "0") is placed in the bit position of the bit array of the set whose address is that value.
is set, the first operation is performed, and the data contents of the other data group are hashed by the hashing device of the other set, so that the bit position of the bit array of the set with that value as the address is "1" (or "0''), the first operation is performed on two data groups at the same time.
When the operation is started and the first operation on one data group is completed, the first operation is continued on the other data group, and at the same time, the second operation is started, and the first operation on the other data group is completed. 1. A data sorting method characterized in that when the second data group is completed, a second operation is performed on one data group, and the second operation is continued on a portion of the other data group that has not been sorted yet.