# US 10,503,755 B2 · Data clustering, segmentation, and parallelization > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,503,755 B2 - Document ID: US10503755B2 - Status: Granted - Kind: B2 - Application number: 13/677,991 - Filed: 2012-11-15 - Published: 2013-05-16 - Granted: 2019-12-10 - Earliest claimed: 2011-11-15 - Assignees: Ab Initio Technology LLC - Applicants: Arlen Anderson - Inventors: Arlen Anderson - Web page: https://patentgrep.com/patent/US10503755B2 ## CPC - G06F 16/285: {Clustering or classification} - G06F 16/20: of structured data, e.g. relational data - G06F 16/24534: {Query rewriting; Transformation} - G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning} - G06F 16/3338: {Query expansion} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A first set of original records is processed by a first processing entity to generate a second set of records that includes the original records and one or more copies of each original record, each original record including one or more fields. The processing of each of at least some of the original records includes: generating at least one copy of the original record, and associating a first segment value with the original record and associating a second segment value with the copy. The method also includes partitioning the second set of records among a plurality of recipient processing entities based on the segment values associated with the records in the second set, and, at each recipient processing entity, performing an operation based on one or more data values of the records received at the recipient processing entity to generate results. ## Claims ### Claim 1 A method, including: processing a first set of original records by a first processing entity to generate a second set of records that includes the original records and one or more copies of each original record, each original record including one or more fields, and the processing of each of at least some of the original records including generating at least one copy of the original record, and associating a first segment value with the original record and associating a second segment value with the copy, where the first segment value corresponds to a first portion of one or more data values of respective fields of the original record and the second segment value correspond to a second portion of the one or more data values of the respective fields of the original record, and where the second portion is different from the first portion, and partitioning the second set of records among a plurality of recipient processing entities based on the segment values associated with the records in the second set, and, at each recipient processing entity, performing an operation based on one or more data values of the records received at the recipient processing entity to generate results. ### Claim 2 (depends on 1) The method of claim 1, wherein the first segment value corresponds to a first sequence of characters from a first data value of a first field taken from a first set of positions of the characters in the first data value, and the second segment value corresponds to a second sequence of characters from the first data value taken from a second set of positions of the characters in the first data value. ### Claim 3 (depends on 2) The method of claim 2, wherein the first set of positions are non-overlapping with the second set of positions. ### Claim 4 (depends on 3) The method of claim 3, wherein the first set of positions are even positions relative to the first character of the data value, and the second set of positions are odd positions relative to the first character of the data value. ### Claim 5 (depends on 1) The method of claim 1, wherein associating a segment value with a record includes writing the associated segment value into a new field of the record. ### Claim 6 (depends on 1) The method of claim 1, wherein performing an operation based on the one or more data values of the records received at the recipient processing entity includes determining a match between character strings occurring in one or more data values of a first record and character strings occurring in one or more data values of at least a second record. ### Claim 7 (depends on 6) The method of claim 6, wherein the match is an approximate match. ### Claim 8 (depends on 7) The method of claim 7, wherein the approximate match allows the strings being matched to be different up to a specified edit distance. ### Claim 9 (depends on 7) The method of claim 7, wherein the approximate match is based on a match criterion that defines allowed differences between a data value of the first record and a data value of the second record, and wherein, for each original record, the first portion of the one or more data values and the second portion of the one or more data values are selected so that at least one of the first segment value or the second segment value does not change in response to a change of the one or more data values according to any of the allowed differences. ### Claim 10 (depends on 9) The method of claim 9, wherein the allowed differences include differences between a first character string occurring in the data value of the first record and a second character string occurring in the data value of the second record. ### Claim 11 (depends on 9) The method of claim 9, wherein the allowed differences include differences between a first binary value occurring in the data value of the first record and a second binary value occurring in the data value of the second record. ### Claim 12 (depends on 1) The method of claim 1, wherein performing an operation based on the one or more data values of the records received at the recipient processing entity includes surrogate key assignment. ### Claim 13 (depends on 12) The method of claim 12, wherein the results generated at the recipient processing entity include, for each record received at the recipient processing entity, the record augmented with an assigned surrogate key based on the one or more data values of the record. ### Claim 14 (depends on 1) The method of claim 1, wherein performing an operation based on the one or more data values of the records received at the recipient processing entity includes clustering the received records into one or more clusters. ### Claim 15 (depends on 14) The method of claim 14, wherein the results generated at the recipient processing entity include, for each record received at the recipient processing entity, the record augmented with an assigned cluster based on the one or more data values of the record and the one or more data values of at least some of the other records received at the recipient processing entity. ### Claim 16 (depends on 1) The method of claim 1, wherein the operation includes at least one of: surrogate key assignment, clustering, roll-up, or join. ### Claim 17 (depends on 1) The method of claim 1, wherein the first segment value corresponds to a first portion of multiple data values of respective fields of the original record and the second segment value correspond to a second portion of the multiple data values of the respective fields of the original record, and where the second portion is different from the first portion. ### Claim 18 (depends on 1) The method of claim 1, further including receiving results from each recipient processing entity at a second processing entity, and processing the received results to remove redundant results. ### Claim 19 (depends on 18) The method of claim 18, wherein the second set of records includes the original records and at least one copy of each original record. ### Claim 20 (depends on 19) The method of claim 19, wherein processing the received results to remove redundant results includes selecting at most one of: a first result associated with an original record, or a second result associated with a copy of the original record. ### Claim 21 (depends on 1) The method of claim 1, further including receiving results from each recipient processing entity at the first processing entity, and processing the received results to remove redundant results. ### Claim 22 (depends on 1) The method of claim 1, wherein each of the recipient processing entities perform the respective operations independently. ### Claim 23 (depends on 1) The method of claim 1, wherein the number of recipient processing entities is at least as large as the smallest number of different segment values associated with each original record and its copies. ### Claim 24 (depends on 1) The method of claim 1, wherein the processing entities are cores in a multicore processor, and the first processing entity sends the partitioned records from the second set of records to the recipient processing entities over an interconnection network in the multicore processor. ### Claim 25 (depends on 1) The method of claim 1, wherein the processing entities are processors in a multi-processor computer system, and the first processing entity sends the partitioned records from the second set of records to the recipient processing entities over an interconnection network in the multi-processor computer system. ### Claim 26 (depends on 1) The method of claim 1, wherein the processing entities are server computers in a rack-mounted server system, and the first processing entity sends the partitioned records from the second set of records to the recipient processing entities over an interconnection network in the rack-mounted server system. ### Claim 27 (depends on 1) The method of claim 1, wherein the processing entities are computer systems in communication over a network, and the first processing entity sends the partitioned records from the second set of records to the recipient processing entities over the network. ### Claim 28 A computer program stored on a non-transitory computer-readable medium, the computer program including instructions for causing a computing system to: process a first set of original records by a first processing entity to generate a second set of records that includes the original records and one or more copies of each original record, each original record including one or more fields, and the processing of each of at least some of the original records including generating at least one copy of the original record, and associating a first segment value with the original record and associating a second segment value with the copy, where the first segment value corresponds to a first portion of one or more data values of respective fields of the original record and the second segment value correspond to a second portion of the one or more data values of the respective fields of the original record, and where the second portion is different from the first portion, and partition the second set of records among a plurality of recipient processing entities based on the segment values associated with the records in the second set, and, at each recipient processing entity, perform an operation based on one or more data values of the records received at the recipient processing entity to generate results. ### Claim 29 A computing system, including: a first processing entity that includes at least one processor configured to process a first set of original records to generate a second set of records that includes the original records and one or more copies of each original record, each original record including one or more fields, and the processing of each of at least some of the original records including generating at least one copy of the original record, and associating a first segment value with the original record and associating a second segment value with the copy, where the first segment value corresponds to a first portion of one or more data values of respective fields of the original record and the second segment value correspond to a second portion of the one or more data values of the respective fields of the original record, and where the second portion is different from the first portion, and a plurality of recipient processing entities receiving respective subsets of the second set of records partitioned based on the segment values associated with the records in the second set, each recipient processing entity configured to perform an operation based on one or more data values of the records received at the recipient processing entity to generate results. ### Claim 30 A method, including: partitioning a set of records by a first processing entity into multiple subsets of records; and processing different subsets of the set of records by different respective recipient processing entities and storing results in data storage accessible to each of the recipient processing entities, the processing by each recipient processing entity including performing an operation on at least one record in the subset based on determining whether or not there is an approximate match between one or more values of one or more fields of the record and an entry within local reference information maintained by the recipient processing entity, and performing an operation on at least one record in the subset based on determining whether or not there is an approximate match between one or more values of one or more fields of the record and an entry within the data storage that was provided by any of the other recipient processing entities, and updating the data storage based on the local reference information maintained by the recipient processing entity. ### Claim 31 (depends on 30) The method of claim 30, wherein the data storage accessible to each of the recipient processing entities includes a non-volatile storage medium. ### Claim 32 (depends on 31) The method of claim 31, wherein the local reference information maintained by each recipient processing entity is stored in a volatile storage medium. ### Claim 33 (depends on 30) The method of claim 30, wherein the approximate match allows the values being matched to be different up to a specified edit distance. ### Claim 34 (depends on 30) The method of claim 30, wherein performing an operation on each record in the subset includes surrogate key assignment. ### Claim 35 (depends on 34) The method of claim 34, wherein results generated at a recipient processing entities include, for each record received at the recipient processing entity, the record augmented with an assigned surrogate key based on the one or more values of the record. ### Claim 36 (depends on 30) The method of claim 30, wherein performing an operation on each record in the subset includes clustering the records into one or more clusters. ### Claim 37 (depends on 36) The method of claim 36, wherein results generated at a recipient processing entity include, for each record received at the recipient processing entity, the record augmented with an assigned cluster based on the one or more values of the record and the one or more values of at least some of the other records received at the recipient processing entity. ### Claim 38 (depends on 30) The method of claim 30, wherein the operation includes at least one of: surrogate key assignment, clustering, roll-up, or join. ### Claim 39 A computer program stored on a non-transitory computer-readable medium, the computer program including instructions for causing a computing system to: partition a set of records by a first processing entity into multiple subsets of records; and process different subsets of the set of records by different respective recipient processing entities and storing results in data storage accessible to each of the recipient processing entities, the processing by each recipient processing entity including performing an operation on at least one record in the subset based on determining whether or not there is an approximate match between one or more values of one or more fields of the record and an entry within local reference information maintained by the recipient processing entity, and performing an operation on at least one record in the subset based on determining whether or not there is an approximate match between one or more values of one or more fields of the record and an entry within the data storage that was provided by any of the other recipient processing entities, and updating the data storage based on the local reference information maintained by the recipient processing entity. ### Claim 40 A computing system, including: a first processing entity that includes at least one processor configured to partition a set of records into multiple subsets of records; and a plurality of recipient processing entities each configured to process a different respective subset of the set of records and store results in data storage accessible to each of the recipient processing entities, the processing by each recipient processing entity including performing an operation on at least one record in the subset based on determining whether or not there is an approximate match between one or more values of one or more fields of the record and an entry within local reference information maintained by the recipient processing entity, and performing an operation on at least one record in the subset based on determining whether or not there is an approximate match between one or more values of one or more fields of the record and an entry within the data storage that was provided by any of the other recipient processing entities, and updating the data storage based on the local reference information maintained by the recipient processing entity.