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

Claim 6:
7. A system for identifying matches between a first database data set and a second database data set, the system comprising:
(A) a partition assignment manager having an input for receiving a plurality of data elements of the first database data set, the partition assignment manager for hashing each of the 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, and for assigning via an output each of the plurality of data elements and the first hash result produced therefrom, to one of a plurality of buffers, responsive to the first portion of the first hash result for each of the respective data elements in the plurality;
(B) in each of a plurality of processor cores, operating substantially simultaneously with the other processor cores:
(1) a sub partition assignment manager having an input coupled to the partition assignment manager output for receiving the second portion of the first hash result of each of the data elements of the first database data set, the sub partition assignment manager for selecting via an input/output a buffer in the plurality of buffers not already selected by any of the plurality of processor cores and for assigning via an output each of the plurality of data elements assigned to the selected buffer, to one sub buffer in a plurality of sub buffers, each such sub buffer corresponding to a range of potential first hash results, a second plurality of the sub buffers corresponding to each buffer in the plurality, responsive to the second portion of the first hash result of each said data element and the range of potential first hash results of the one of the sub buffers, and for storing via the sub partition assignment manager output in storage other than random access memory each sub buffer corresponding to the selected buffer and;
(2) a hash table manager having an input coupled to the partition assignment manager output for receiving at least a portion of the first hash result and to the sub partition assignment manager output for receiving of the plurality of data elements assigned to the sub buffers in the plurality, the hash table manager for generating a hash table for each sub buffer comprising a first alternate hash result, for each data element that is generated using, and different from, the first hash result for said data element, and for storing in the storage other than random access memory via an output the hash table of said sub buffer, associated with said sub buffer; and
wherein operation of the sub partition assignment manager and the hash table manager is repeated until all buffers in the plurality have been selected and hash tables generated for all sub buffers;

(C) an ODS setup manager having an input for receiving a portion, less than all, of a plurality of data elements of the second database data set and for storing such portion into a plurality of chunks of memory via an output;
(D) at each of the plurality of processor cores, an ODS assignment manager having an input coupled to the ODS setup manager output for receiving at least the data elements of the second database data set in at least some of the plurality of chunks of memory, the ODS assignment manager for selecting one of the plurality of chunks not already selected by any of the plurality of processor cores, and for each of the plurality of data elements in the selected chunk: hashing said data element in the selected chunk to produce a second hash result for said data element, and providing an assignment via an output 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 assignments being responsive to the range of potential second hash results of the sub partition and the second hash result of said data element in the selected chunk, the ODS assignment manager in one of the plurality of processor cores operating substantially simultaneously with the ODS assignment manager in each of at least one other of the processor cores in the plurality;
(E) at each of the plurality of processor cores, substantially simultaneously with the other processor cores: an ODS match manager having an input coupled to the ODS setup manager output for receiving some of the plurality of data elements of the second database data set, to the output of at least some of the ODS assignment managers for receiving at least some of the assignments, to the storage other than random access memory for receiving the hash table and data elements of the first database data set of a plurality of the sub buffers, the ODS match manager for
(1) selecting via an input/output one of the plurality of sub partitions not already selected by any of the plurality of processor cores;
(2) reading the hash table and data elements of the first database data set assigned to 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; and
(3) for each of the plurality of data elements in the selected sub partition:
(a) identifying whether a second alternate hash result of said data element corresponds to the first alternate hash result; and
(b) if the second alternate hash result corresponds to the first alternate hash result, comparing 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 the comparing results in a match, identifying at an output 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) repeating operation of (1)-(3) until all sub partitions have been so processed; and

(F) wherein operation of elements (C)-(E) are repeated until all of the plurality of data elements of the second database data set have been processed by elements (E)-(G).