Systems and methods for automatic clustering and canonical designation of related data in various data structures

• US 10,127,289 B2
• Filed: 08/10/2016
• Issued: 11/13/2018
• Est. Priority Date: 08/19/2015
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Manning, Lawrence, Mehta, Rahul, Erenrich, Daniel, Visa, Guillem Palou, Hu, Roger, Falco, Xavier, Gilmore, Rowan, Bingham, Eli, Prestinario, Jason, Huang, Yifei, Fernandez, Daniel, Elser, Jeremy, Sader, Clayton, Agarwal, Rahul, Elkherj, Matthew, Latourette, Nicholas, Zamoshchin, Aleksandr
• Primary Examiner(s): Torgrimson, Tyler
• Application Number:
  US15/233,149
• Publication Number:
  US 20170052958A1
• Time in Patent Office: 825 Days
• Field of Search: None
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 18/23 Clustering techniques

Abstract

Computer implemented systems and methods are disclosed for automatically clustering and canonically identifying related data in various data structures. Data structures may include a plurality of records, wherein each record is associated with a respective entity. In accordance with some embodiments, the systems and methods further comprise identifying clusters of records associated with a respective entity by grouping the records into pairs, analyzing the respective pairs to determine a probability that both members of the pair relate to a common entity, and identifying a cluster of overlapping pairs to generate a collection of records relating to a common entity. Clusters may further be analyzed to determine canonical names or other properties for the respective entities by analyzing record fields and identifying similarities.

Claims

1. A system comprising:

a data store configured to store computer-executable instructions and a plurality of records, wherein each record of the plurality of records is associated with a respective entity and comprises one or more fields;

a computing device including a processor in communication with the data store, the processor configured to execute the computer-executable instructions to at least;

identify, based at least in part on a first field of the one or more fields, a first group of the plurality of records;

determine that a distribution of sizes of groups including the first group satisfies a distribution rule;

generate one or more record pairs from the first group, each of the one or more record pairs comprising a respective first record and second record, wherein at least one field of the first record differs from a corresponding field in the second record;

determine, for each of the one or more record pairs, a respective match score, the respective match scores comprising probabilities that the respective first record and second record of the respective record pair are associated with a respective same entity;

identify a plurality of clusters of record pairs, wherein each pair in each cluster has a record in common with at least one other pair in the cluster, and wherein each pair in each cluster has a respective match score above a threshold;

determine, for each of the plurality of clusters, that a diameter of the cluster satisfies a diameter criterion;

determine, for each of the plurality of clusters, that an entropy of the cluster satisfies an entropy criterion;

determine, based at least in part on the distribution of sizes of groups, the respective match scores, the diameter criterion, and the entropy criterion, that each of the plurality of clusters corresponds to a respective entity;

determine, for each of the plurality of clusters, a geographical location associated with the cluster, the geographic location corresponding to the respective entity;

generate, based at least in part on the geographical location associated with each cluster and a number of record pairs in each cluster, a heat map for display on a client computing device, wherein the heat map enables identification of suitable locations for providing coverage of the geographical locations associated with the clusters, wherein the heat map overlays information regarding the number of record pairs in each cluster on the geographic location associated with the cluster, and wherein the heat map displays information regarding the at least one field of individual records in each cluster as a color, symbol, shading, or other representation; and

cause the client computing device to display the heat map.

2. The system of claim 1, wherein the processor is further configured to execute the computer-executable instructions to at least:

determine, based at least in part on a first pair in a first cluster of the plurality of clusters of record pairs, a first candidate name to associate with the cluster;

determine, based at least in part on a second pair in the first cluster, a second candidate name based to associate with the cluster; and

determine a name to associate with the first cluster based at least in part on the first candidate name and the second candidate name.

3. The system of claim 2, wherein determining the first candidate name is based at least in part on a first field of the first record and a corresponding second field of the second record.

4. The system of claim 3, wherein determining the first candidate name comprises identifying a longest common substring of the first field and the second field.

5. The system of claim 3, wherein determining the first candidate name is based at least in part on calculating a Levenshtein distance between a first field of the first record and a corresponding second field of the second record.

6. The system of claim 1, wherein the processor is further configured to execute the computer-executable instructions to identify the first group of the plurality of records by at least:

accessing a first record, a second record, and a third record of the plurality of records;

accessing a blocking model including information indicative of at least a first field and a second field to be compared between candidate pairs of records;

comparing a value of the first field of the first record with a value of the first field of the second record to determine first matching fields;

comparing a value of the second field of the first record with a value of the second field of the second record to determine second matching fields;

in response to determining the first matching fields and the second matching fields, grouping the first record and the second record into the first group;

comparing the value of the first field of the second record with a value of the first field of the third record to determine third matching fields;

comparing the value of the second field of the second record with a value of the second field of the third record to determine fourth matching fields; and

in response to determining the third matching fields and the fourth matching fields, adding the third record to the first group.

7. The system of claim 6, wherein determining at least one of the first, second, third, or fourth matching fields is based at least in part on a soft or fuzzy match.

8. The system of claim 6, wherein determining at least one of the first, second, third, or fourth matching fields is based at least in part on a weighting.

9. The system of claim 1, wherein the processor is further configured to execute the computer-executable instructions to identify the first group of the plurality of records by at least:

accessing a first record, a second record, and a third record of the plurality of records;

accessing a blocking model including information indicative of at least a first field to be compared between candidate pairs of records and a second field to be compared between candidate pairs of records;

comparing a value of the first field of the first record with a value of the first field of the second record to determine first matching fields;

in response to determining the first matching fields, grouping the first record and the second record into the first group;

comparing a value of the first field of the second record with a value of the first field of the third record to determine that the fields do not match;

comparing the value of the second field of the second record with a value of the second field of the third record to determine second matching fields;

in response to determining the second matching fields, adding the third record to the first group.

10. The system of claim 1, wherein the processor is further configured to execute the computer-executable instructions to at least:

validate the first group of the plurality of records by at least one of;

determining that a size of the first group satisfies a threshold, or

determining that a distribution of sizes of groups including the first group satisfies a distribution rule.

11. A method comprising:

obtaining a first plurality of records, wherein each record of the first plurality of records is associated with a respective entity and comprises a first one or more fields;

obtaining a second plurality of records, wherein each record of the second plurality of records is associated with a respective entity and comprises a second one or more fields, and wherein each record of the second plurality of records is associated with a different entity;

identifying, based at least in part on a first field of the first one or more fields, a first subset of the first plurality of records;

determining that a distribution of sizes of subsets of the first plurality of records satisfies a distribution rule, the subsets of the first plurality of records including the first subset;

identifying, based at least in part on a second field of the second one or more fields, a second subset of the second plurality of records;

generating a plurality of record pairs, wherein each record pair in the plurality of record pairs comprises a respective first record from the first subset and a respective second record from the second subset, and wherein at least one field of the first record differs from a corresponding field in the second record;

determining a respective match score for each of the plurality of record pairs, the respective match scores comprising probabilities that the respective first record and second record of the respective record pairs are associated with a respective same entity;

identifying, for each record in the first subset, a respective cluster of record pairs, wherein each record pair in the cluster includes the record;

determining, for each cluster of record pairs, that a diameter of the cluster satisfies a diameter criterion;

determining, for each cluster of record pairs, that an entropy of the cluster satisfies an entropy criterion;

determining, based at least in part on the distribution of sizes, the respective match scores, the diameter criterion, and the entropy criterion, that each cluster of record pairs corresponds to a respective entity;

identifying, for each cluster of record pairs, a respective matching record pair based at least in part on the match scores of the record pairs in the cluster;

generating, based at least in part on a geographical location associated with each cluster and a number of record pairs in each cluster, a heat map for display on a client computing device, wherein the heat map enables identification of suitable locations for providing coverage of the geographical location associated with the clusters, wherein the heat map overlays information regarding the number of record pairs in each cluster on the geographic location associated with the cluster, and wherein the heat map displays information regarding the at least one field of individual records in each cluster as a color, symbol, shading, or other representation; and

causing the client computing device to display the heat map.

12. The method of claim 11, wherein identifying the respective matching record pair for each cluster comprises identifying a record pair having a highest match score.

13. The method of claim 11, wherein determining a match score is based at least in part on one or more reference pairs.

14. The method of claim 13, wherein the one or more reference pairs each comprise a first matched record associated with a first entity and a second matched record associated with the first entity.

15. The method of claim 13, wherein the one or more reference pairs each comprise a first unmatched record associated with a first entity and a second unmatched record associated with a second entity.

16. The method of claim 11 further comprising:

identifying an indeterminate record pair of the plurality of record pairs, the indeterminate record pair having a match score indicating a least certainty of whether the first record and second record of the indeterminate record pair are associated with the same entity;

outputting the indeterminate record pair to a user;

receiving, from the user, an indication that the first record and the second record of the indeterminate record pair are associated with the same entity;

calculating, for each of the plurality of record pairs, a respective revised match score based at least in part on the indication;

wherein identifying the respective matching record pair for each cluster of record pairs is further based at least in part on the revised match scores of the record pairs in the cluster.

17. A non-transitory computer-readable storage medium including computer-executable instructions that, when executed by a processor, cause the processor to:

obtain a plurality of records, wherein each record of the plurality of records is associated with a respective entity and comprises one or more fields;

generate one or more record pairs from at least a portion of the plurality of records, each of the one or more record pairs comprising a respective first record and second record, wherein at least one field of the first record differs from a corresponding field in the second record, and wherein a distribution of portions of the plurality of records satisfies a distribution rule;

determine, for each of the one or more record pairs, a respective match score, the respective match scores comprising probabilities that the respective first record and second record of the respective record pairs are associated with a respective same entity;

identify a first cluster of record pairs, wherein each pair in the first cluster has a record in common with at least one other pair in the first cluster, and wherein each pair in the first cluster has a respective match score above a first threshold;

determine that an entropy of the first cluster of record pairs satisfies an entropy criterion;

generate, based at least in part on a geographical location associated with the first cluster and a number of record pairs in the first cluster, a heat map for display on a client computing device, wherein the heat map enables identification of suitable locations for providing coverage of the geographical location associated with the first cluster, wherein the heat map overlays information regarding the number of record pairs in the first cluster on the geographic location associated with the first cluster, and wherein the heat map displays information regarding the at least one field of individual records in the first cluster as a color, symbol, shading, or other representation; and

causing the client computing device to display the heat map.

18. The non-transitory computer-readable storage medium of claim 17, wherein the computer-executable instructions that cause the processor to determine a respective match score for each of the one or more record pairs comprise computer-executable instructions that cause the processor to:

obtain a plurality of reference pairs, each of the plurality of reference pairs comprising a respective first record and second record, wherein the respective first record and second record of a reference pair are associated with the same entity;

determine a first plurality of match scores according to a first model, wherein the first plurality of match scores corresponds to the plurality of reference pairs;

determine a second plurality of match scores according to a second model, wherein the second plurality of match scores corresponds to the plurality of reference pairs;

determine, based at least in part on the first plurality of match scores, a first accuracy score for the first model;

determine, based at least in part on the second plurality of match scores, a second accuracy score for the second model;

wherein the computer-executable instructions that cause the processor to determine the respective match score for each of the one or more record pairs cause the processor to determine the respective match score according to the model having the higher accuracy score.

19. The non-transitory computer-readable storage medium of claim 17, wherein the computer-executable instructions further cause the processor to:

output the first cluster of record pairs to a client computing device;

receive, from the client computing device, a second threshold;

identify a second cluster of record pairs, wherein each pair of the second cluster has a record in common with at least one other pair in the second cluster, and wherein each pair in the second cluster has a respective match score above the second threshold; and

output the second cluster to the client computing device.

20. The non-transitory computer-readable storage medium of claim 17, wherein the computer-executable instructions further cause the processor to generate one or more normalized fields for the plurality of records, and wherein the respective match score for each of the one or more record pairs is based at least in part on the one or more normalized fields.