Data clustering, segmentation, and parallelization

• US 10,503,755 B2
• Filed: 11/15/2012
• Issued: 12/10/2019
• Est. Priority Date: 11/15/2011
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Inventors: Anderson, Arlen
• Primary Examiner(s): Gurmu, Muluemebet
• Application Number:
  US13/677,991
• Publication Number:
  US 20130124474A1
• Time in Patent Office: 2,581 Days
• Field of Search: 707634
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/3338 Query expansion

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

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.

2. 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.

3. The method of claim 2, wherein the first set of positions are non-overlapping with the second set of positions.

4. 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.

5. 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.

6. 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.

7. The method of claim 6, wherein the match is an approximate match.

8. The method of claim 7, wherein the approximate match allows the strings being matched to be different up to a specified edit distance.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. The method of claim 1, wherein the operation includes at least one of:

surrogate key assignment, clustering, roll-up, or join.

17. 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.

18. 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.

19. The method of claim 18, wherein the second set of records includes the original records and at least one copy of each original record.

20. 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.

21. 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.

22. The method of claim 1, wherein each of the recipient processing entities perform the respective operations independently.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

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.

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.

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.

31. The method of claim 30, wherein the data storage accessible to each of the recipient processing entities includes a non-volatile storage medium.

32. The method of claim 31, wherein the local reference information maintained by each recipient processing entity is stored in a volatile storage medium.

33. The method of claim 30, wherein the approximate match allows the values being matched to be different up to a specified edit distance.

34. The method of claim 30, wherein performing an operation on each record in the subset includes surrogate key assignment.

35. 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.

36. The method of claim 30, wherein performing an operation on each record in the subset includes clustering the records into one or more clusters.

37. 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.

38. The method of claim 30, wherein the operation includes at least one of:

surrogate key assignment, clustering, roll-up, or join.

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.

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.