Systems and methods for automatic clustering and canonical designation of related data in various data structures
First Claim
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.
8 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16)
-
-
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. - View Dependent Claims (18, 19, 20)
-
Specification