Patent ID: 11914565
Assignee: YELLOWBRICK DATA, INC.
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 12:
13. A computer program product comprising a nontransitory computer useable medium having computer readable program code embodied therein for identifying matches between a first database data set and a second database data set, the computer program product comprising computer readable program code devices configured to cause a computer system to:
A. hash each of a plurality of data elements of the first database data set to produce a first hash result for each of the plurality of data elements, each first hash result comprising a first portion and a second portion, the first and second portions each comprising less than all of the first hash result and not entirely overlapping with each other;
B. assign each of the plurality of data elements of the first database data set to one of a plurality of buffers, responsive to the first portion of the first hash result for each of said respective data elements in the plurality;
C. by each of a plurality of processor cores, substantially simultaneously with the other processor cores:
(1) select a buffer in the plurality not already selected by any of the plurality of processor cores;
(2) assign each of the plurality of data elements assigned to the selected buffer, to a sub buffer in a plurality of sub buffers, each sub buffer corresponding to a range of potential first hash results, a second plurality of sub buffers corresponding to each of the buffers, responsive to the second portion of the first hash result of each said data element and the range of potential first hash results of said one of the sub buffers;
(3) generate a hash table for the data elements assigned to each said sub buffer comprising a first alternate hash result for each data element that is generated using, and different from, the first hash result for the respective data element;
(4) store in storage other than random access memory each sub buffer corresponding to the selected buffer, and the hash table of said sub buffer; and
(5) repeat operation of computer readable program code devices (C)(1)-(C)(4) until all buffers in the plurality have been selected;

D. receive a portion, less than all, of a plurality of data elements of the second database data set into a plurality of chunks of memory;
E. by each of the plurality of processor cores, substantially simultaneously with the other processor cores:
(1) select one of the plurality of chunks of memory not already selected by any of the plurality of processor cores; and
(2) for each of the plurality of data elements in the selected chunk:
(a) hash said data element in the selected chunk to produce a second hash result for said data element;
(b) assign the data element in the selected chunk to one of a plurality of sub partitions, each of the sub partitions in the plurality being assigned a range of potential second hash results equal to a range of a different one of the sub buffers, said assigning being responsive to the range of potential second hash results of said sub partition and the second hash result of said data element in the selected chunk; and

(3) repeat operation of computer readable program code devices (E)(1) and (E)(2) until all of the chunks of memory have been processed;

(F) by each of the plurality of processor cores, substantially simultaneously with other processor cores:
(1) select one of the plurality of sub partitions not already selected by any of the plurality of processor cores;
(2) read the hash table and data elements of the first database data set of any sub buffer having a range of potential first hash results corresponding to the range of potential second hash results of the selected sub partition;
(3) for each of the plurality of data elements in the selected sub partition:
(a) identify whether a second alternate hash result of said data element corresponds to any of the first alternate hash results of said any sub buffer; and
(b) if the second alternate hash result corresponds to said any first alternate hash result, compare said data element in the selected sub partition with the data element in the sub buffer read that corresponds to the corresponding first alternate hash result, and if said compare results in a match, identify as matched with said data element in the selected sub partition the data element in the sub buffer read that corresponds to said data element in the selected sub partition; and

(4) repeat operation of (F)(1)-(F)(3) until all of the sub partitions have been selected; and

(G) repeat operation of computer readable program code devices (D)-(F) until all of the plurality of data elements of the second database data set have been processed as specified by computer readable program code devices (D)-(F).