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

Patent metadata

Field	Value
Publication number	US-12430346-B2
Application number	US-202418731699-A
Country	US
Kind code	B2
Filing date	Jun 3, 2024
Priority date	Aug 19, 2015
Publication date	Sep 30, 2025
Grant date	Sep 30, 2025

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.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving, via a network interface configured to receive digital data packets including data records, data records;
generating a plurality of record pairs from the received data records, wherein generating the plurality of record pairs includes:
applying a blocking model to the data records to generate groups of data records based at least in part on relationships between values of fields of the data records;
causing a client computing device to present at least a portion of the groups of data records to a user via a first user interface;
receiving first user feedback, from the user and via input to the first user interface of the client computing device, identifying one or more bad groups of data records;
generating first update information to be fed back into the blocking model based on the first user feedback;
re-applying the blocking model, based at least in part on the first update information, to re-generate the groups of data records; and
designating each of the groups of data records as a record pair of the plurality of record pairs;

applying a machine learning model to determine respective probabilities, for each of the plurality of record pairs, that respective first records and second records of the respective record pairs are associated with a respective same entity;
identifying, from the plurality of record pairs, an indeterminate record pair based at least in part on the associated determined probability being below a pre-established threshold;
causing the client computing device to present the indeterminate record pair to a user via a second user interface;
receiving second user feedback, from the user and via input to the second user interface of the client computing device, indicating whether the first and second records of the indeterminate record pair are associated with the same entity;
generating second update information to be fed back into the machine learning model based on the second user feedback;
re-applying the machine learning model, based at least in part on the second update information, to re-determine the probability of the indeterminate record pair;
identifying, for each cluster of record pairs, respective geographical locations corresponding to the clusters based at least in part on the respective probabilities;
associating, based on the identified geographical locations corresponding to the clusters, geographical locations with each of the data records;
generating, and causing the client computing device to display, a geographic map; and
based on the geographical locations associated with the respective data records, overlaying a heat map of the data records on the geographical map, wherein the heat map illustrates, for individual clusters of record pairs, information regarding a size of the cluster at the geographical location corresponding to the cluster.

2. The computer-implemented method of claim 1 further comprising:
determining, based at least in part on the probabilities, respective entities associated with one or more clusters of record pairs; and
outputting the clusters of record pairs and the respective entities associated with each cluster to the client computing device.

3. The computer-implemented method of claim 2 further comprising:
determining, for the record that is included in each record pair of a first cluster of record pairs, a canonical value for at least one field based at least in part on the probabilities of the record pairs in the first cluster.

4. The computer-implemented method of claim 2 further comprising:
filtering the record pairs in a first cluster of record pairs, and wherein the entity associated with the first cluster of record pairs is determined based at least in part on the filtered record pairs.

5. The computer-implemented method of claim 2 further comprising:
pruning the record pairs in each cluster of record pairs to produce a bipartite graph.

6. The computer-implemented method of claim 5 , wherein the record pairs are pruned based at least in part on the probabilities.

7. A system comprising:
a network interface configured to receive digital data packets including data records; and
one or more processors configured to execute computer-executable instructions to at least:
receiving data records via the network interface;
generate a plurality of record pairs from the received data records, wherein generating the plurality of record pairs includes:
applying a blocking model to the data records to generate groups of data records based at least in part on relationships between values of fields of the data records;
causing a client computing device to present at least a portion of the groups of data records to a user via a first user interface;
receiving first user feedback, from the user and via input to the first user interface of the client computing device, identifying one or more bad groups of data records;
generating first update information to be fed back into the blocking model based on the first user feedback;
re-applying the blocking model, based at least in part on the first update information, to re-generate the groups of data records; and
designating each of the groups of data records as a record pair of the plurality of record pairs;

apply a machine learning model to determine respective probabilities, for each of the plurality of record pairs, that respective first records and second records of the respective record pairs are associated with a respective same entity;
identify, from the plurality of record pairs, an indeterminate record pair based at least in part on the associated determined probability being below a pre-established threshold;
cause the client computing device to present the indeterminate record pair to a user via a second user interface;
receive second user feedback, from the user and via input to the second user interface of the client computing device, indicating whether the first and second records of the indeterminate record pair are associated with the same entity;
generate second update information to be fed back into the machine learning model based on the second user feedback;
re-apply the machine learning model, based at least in part on the second update information, to re-determine the probability of the indeterminate record pair;
identify, for each cluster of record pairs, respective geographical locations corresponding to the clusters based at least in part on the respective probabilities;
associate, based on the identified geographical locations corresponding to the clusters, geographical locations with each of the data records;
generate, and causing the client computing device to display, a geographic map; and
based on the geographical locations associated with the respective data records, overlay a heat map of the data records on the geographical map, wherein the heat map illustrates, for individual clusters of record pairs, information regarding a size of the cluster at the geographical location corresponding to the cluster.

8. The system of claim 7 , wherein the one or more processors are configured to execute computer-executable instructions to further at least:
determine, based at least in part on the probabilities, respective entities associated with one or more clusters of record pairs; and
output the clusters of record pairs and the respective entities associated with each cluster to the client computing device.

9. The system of claim 8 , wherein the one or more processors are configured to execute computer-executable instructions to further at least:
determine, for the record that is included in each record pair of a first cluster of record pairs, a canonical value for at least

Assignees

• Palantir Technologies Inc

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

Classifications

• G06F18/23

  Clustering techniques · CPC title

• G06F16/285

  Clustering or classification · CPC title

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F16/35 Primary

  Clustering; Classification · CPC title

• G06F16/24578 Primary

  using ranking · CPC title