# US 2021/0240693 A1 · Event-driven identity graph conflation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0240693 A1
- Document ID: US20210240693A1
- Status: Published application
- Kind: A1
- Application number: 16/777,692
- Filed: 2020-01-30
- Published: 2021-08-05
- Earliest claimed: 2020-01-30
- Assignees: Walmart Apollo, LLC
- Applicants: Walmart Apollo, LLC
- Inventors: Deepak Goyal; Giridhar Addepalli; Sebastien Jean-Maurice Olivier Pehu; Saigopal Thota; Mridul Jain; Navinder Pal Singh Brar
- Web page: https://patentgrep.com/patent/US20210240693A1

## CPC

- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A distributed system including multiple processing nodes. The distributed system can perform certain acts. The acts can include receiving a first conflation event identifying a first node and a second node. The first node can be part of a first set. The first set can include a sole parent node stored at a first processing node of the multiple processing nodes. The second node can be part of a second set. The second set can include a sole parent node stored at a second processing node of the multiple processing nodes. The first and second sets can be disjoint sets. The first conflation event can be received at an event-driven stream application at one of the multiple processing nodes. The acts also can include conflating the first set and the second set into a conflated set. The conflated set can include the first and second nodes. The conflated set can include a sole parent node. Data for each node of the conflated set can be stored at the sole parent node of the conflated set at a processing node of the multiple processing nodes. Other embodiments are disclosed.

## Claims

### Claim 1

A distributed system comprising:
multiple processing nodes,
wherein the distributed system is configured to perform:
receiving a first conflation event identifying a first node and a second node, wherein the first node is part of a first set, the first set comprises a sole parent node stored at a first processing node of the multiple processing nodes, the second node is part of a second set, the second set comprises a sole parent node stored at a second processing node of the multiple processing nodes, the first and second sets are disjoint sets, and the first conflation event is received at an event-driven stream application at one of the multiple processing nodes; and
conflating the first set and the second set into a conflated set, wherein the conflated set comprises the first and second nodes, wherein the conflated set comprises a sole parent node, and data for each node of the conflated set is stored at the sole parent node of the conflated set at a processing node of the multiple processing nodes.

### Claim 2 (depends on 1)

The distributed system of claim 1, wherein:
the first node is the sole parent node of the first set;
the second node is the sole parent node of the second set;
the first node is lexicographically smaller than the second node;
data for the first node are stored at the first node;
the second set further comprises a third node that is a child node mapped to the second node;
the third node is stored at a third processing node of the multiple processing nodes; and
data for the second node and data for the third node are stored at the second node.

### Claim 3 (depends on 2)

The distributed system of claim 2, wherein:
the first conflation event is received at the first processing node; and
conflating the first set and the second set into the conflated set further comprises:
changing a state of the first node to a conflating state;
sending, from the first node to the second node, a root event identifying the first node;
determining, at the second node, that the first node is lexicographically smaller than the second node;
changing a state of the second node to a packed state;
sending, from the second node to the first node, a data event comprising the data for the second node and the data for the third node;
storing the data for the second node and the data for the third node at the first node;
changing the state of the first node to a normal state;
sending, from the first node to each of the second node and the third node, a change-root event identifying the first node;
deleting the data for the second node and the data for the third node from the second node;
setting the second node to be a child node mapped to the first node;
changing the state of the second node to a normal state; and
setting the third node to be a child node mapped to the first node.

### Claim 4 (depends on 2)

The distributed system of claim 2, wherein:
the first conflation event is received at the second processing node; and
conflating the first set and the second set into the conflated set further comprises:
changing a state of the second node to a conflating state;
sending, from the second node to the first node, a first root event identifying the second node;
determining, at the first node, that the first node is lexicographically smaller than the second node;
changing a state of the first node to the conflating state;
sending, from the first node to the second node, a second root event identifying the first node;
changing the state of the second node to a packed state;
sending, from the second node to the first node, a data event comprising the data for the second node and the data for the third node;
storing the data for the second node and the data for the third node at the first node;
changing the state of the first node to a normal state;
sending, from the first node to each of the second node and the third node, a change-root event identifying the first node;
deleting the data for the second node and the data for the third node from the second node;
setting the second node to be a child node mapped to the first node;
changing the state of the second node to a normal state; and
setting the third node to be a child node mapped to the first node.

### Claim 5 (depends on 2)

The distributed system of claim 2, wherein:
the first set further comprises a fourth node that is a child node mapped to the first node;
the fourth node is stored at a fourth processing node of the multiple processing nodes; and
data for the fourth node are stored at the first node.

### Claim 6 (depends on 1)

The distributed system of claim 1, wherein:
the first conflation event is received at the first processing node; and
conflating the first set and the second set into the conflated set further comprises:
changing a state of the first node to a conflating state based on the first conflation event;
receiving, while the state of the first node is the conflating state, a second conflation event at the first processing node identifying the first node and a third node;
adding the second conflation event to a to-be-conflated queue at the first node; and
when the state of the first node changes to a normal state, changing a state of the first node to the conflating state based on the second conflation event.

### Claim 7 (depends on 1)

The distributed system of claim 1, wherein:
the first node is the sole parent node of the first set;
the second node is the sole parent node of the second set;
the first conflation event is received at the first processing node; and
conflating the first set and the second set into the conflated set further comprises:
changing a state of the first node to a conflating state based on the first conflation event;
determining, at the first node, a first conflation hash identifier for the first conflation event;
receiving, while the state of the first node is the conflating state, a second conflation event at a third processing node identifying the second node and a third node, wherein the third node is stored at the third processing node, the third node is a sole parent node of a third set, and the first set, the second set, and the third set are disjoint sets;
changing a state of the third node to the conflating state based on the second conflation event;
determining, at the third node, a second conflation hash identifier for the second conflation event;
sending, from the first node to the second node, a first root event identifying the first node and the first conflation hash identifier;
determining, at the second node, that the first node is lexicographically smaller than the second node;
changing a state of the second node to a packed state;
sending, from the third node to the second node, a second root event identifying the third node and the second conflation hash identifier;
sending, from the second node to the first node, a data event comprising the data for the second node;
sending, from the second node to the third node, a concurrent conflation event comprising the second conflation hash identifier;
sending one or more retries up to a retry limit, from the third node to the second node, for the second root event; and
when the state of the second node changes to a normal state and one of the one or more retries is received at the second node, changing a state of the second node to the conflating state based on the second conflation event.

### Claim 8 (depends on 7)

The distributed system of claim 7, wherein:
the retry limit is randomized to overcome cyclic deadlocks.

### Claim 9 (depends on 1)

The distributed system of claim 1, wherein:
the first set further comprises a third node;
the third node is stored at a third processing node of the multiple processing nodes;
the third node is the sole parent node of the first set;
the second set further comprises a fourth node;
the fourth node is stored at a fourth processing node of the multiple processing nodes;
the fourth node is the sole parent node of the second set;
the first node is a child node mapped to the third node;
the second node is a child node mapped to the fourth node;
data for the first node and data for the third node are stored at the third node; and
data for the second node and data for the fourth node are stored at the fourth node.

### Claim 10 (depends on 9)

The distributed system of claim 9, wherein:
the first conflation event is received at the first processing node; and
conflating the first set and the second set into the conflated set further comprises:
determining, at the first node, that a parent of the first node is the third node;
sending, from the first node to the third node, a second conflation event identifying the third node and the second node;
changing a state of the third node to a conflating state;
sending, from the third node to the second node, a first root event identifying the third node;
determining, at the second node, that a parent of the second node is the fourth node;
sending, from the second node to the fourth node, a second root event identifying the third node;
determining, at the fourth node, that the third node is lexicographically smaller than the fourth node;
changing a state of the fourth node to a packed state;
sending, from the fourth node to the third node, a data event comprising the data for the second node and the data for the fourth node;
storing the data for the second node and the data for the fourth node at the third node;
changing the state of the third node to a normal state;
sending, from the third node to each of the second node and the fourth node, a change-root event identifying the third node;
deleting the data for the second node and the data for the fourth node from the fourth node;
setting the fourth node to be a child node mapped to the third node;
changing the state of the fourth node to a normal state; and
setting the second node to be a child node mapped to the third node.

### Claim 11

A method comprising:
receiving a first conflation event identifying a first node and a second node, wherein the first node is part of a first set, the first set comprises a sole parent node stored at a first processing node of multiple processing nodes of a distributed system, the second node is part of a second set, the second set comprises a sole parent node stored at a second processing node of the multiple processing nodes, the first and second sets are disjoint sets, and the first conflation event is received at an event-driven stream application at one of the multiple processing nodes; and
conflating the first set and the second set into a conflated set, wherein the conflated set comprises the first and second nodes, wherein the conflated set comprises a sole parent node, and data for each node of the conflated set is stored at the sole parent node of the conflated set at a processing node of the multiple processing nodes.

### Claim 12 (depends on 11)

The method of claim 11, wherein:
the first node is the sole parent node of the first set;
the second node is the sole parent node of the second set;
the first node is lexicographically smaller than the second node;
data for the first node are stored at the first node;
the second set further comprises a third node that is a child node mapped to the second node;
the third node is stored at a third processing node of the multiple processing nodes; and
data for the second node and data for the third node are stored at the second node.

### Claim 13 (depends on 12)

The method of claim 12, wherein:
the first conflation event is received at the first processing node; and
conflating the first set and the second set into the conflated set further comprises:
changing a state of the first node to a conflating state;
sending, from the first node to the second node, a root event identifying the first node;
determining, at the second node, that the first node is lexicographically smaller than the second node;
changing a state of the second node to a packed state;
sending, from the second node to the first node, a data event comprising the data for the second node and the data for the third node;
storing the data for the second node and the data for the third node at the first node;
changing the state of the first node to a normal state;
sending, from the first node to each of the second node and the third node, a change-root event identifying the first node;
deleting the data for the second node and the data for the third node from the second node;
setting the second node to be a child node mapped to the first node;
changing the state of the second node to a normal state; and
setting the third node to be a child node mapped to the first node.

### Claim 14 (depends on 12)

The method of claim 12, wherein:
the first conflation event is received at the second processing node; and
conflating the first set and the second set into the conflated set further comprises:
changing a state of the second node to a conflating state;
sending, from the second node to the first node, a first root event identifying the second node;
determining, at the first node, that the first node is lexicographically smaller than the second node;
changing a state of the first node to the conflating state;
sending, from the first node to the second node, a second root event identifying the first node;
changing the state of the second node to a packed state;
sending, from the second node to the first node, a data event comprising the data for the second node and the data for the third node;
storing the data for the second node and the data for the third node at the first node;
changing the state of the first node to a normal state;
sending, from the first node to each of the second node and the third node, a change-root event identifying the first node;
deleting the data for the second node and the data for the third node from the second node;
setting the second node to be a child node mapped to the first node;
changing the state of the second node to a normal state; and
setting the third node to be a child node mapped to the first node.

### Claim 15 (depends on 12)

The method of claim 12, wherein:
the first set further comprises a fourth node that is a child node mapped to the first node;
the fourth node is stored at a fourth processing node of the multiple processing nodes; and
data for fourth node are stored at the first node.

### Claim 16 (depends on 11)

The method of claim 11, wherein:
the first conflation event is received at the first processing node; and
conflating the first set and the second set into the conflated set further comprises:
changing a state of the first node to a conflating state based on the first conflation event;
receiving, while the state of the first node is the conflating state, a second conflation event at the first processing node identifying the first node and a third node;
adding the second conflation event to a to-be-conflated queue at the first node; and
when the state of the first node changes to a normal state, changing a state of the first node to the conflating state based on the second conflation event.

### Claim 17 (depends on 11)

The method of claim 11, wherein:
the first node is the sole parent node of the first set;
the second node is the sole parent node of the second set;
the first conflation event is received at the first processing node; and
conflating the first set and the second set into the conflated set further comprises:
changing a state of the first node to a conflating state based on the first conflation event;
determining, at the first node, a first conflation hash identifier for the first conflation event;
receiving, while the state of the first node is the conflating state, a second conflation event at a third processing node identifying the second node and a third node, wherein the third node is stored at the third processing node, the third node is a sole parent node of a third set, and the first set, the second set, and the third set are disjoint sets;
changing a state of the third node to the conflating state based on the second conflation event;
determining, at the third node, a second conflation hash identifier for the second conflation event;
sending, from the first node to the second node, a first root event identifying the first node and the first conflation hash identifier;
determining, at the second node, that the first node is lexicographically smaller than the second node;
changing a state of the second node to a packed state;
sending, from the third node to the second node, a second root event identifying the third node and the second conflation hash identifier;
sending, from the second node to the first node, a data event comprising the data for the second node;
sending, from the second node to the third node, a concurrent conflation event comprising the second conflation hash identifier;
sending one or more retries up to a retry limit, from the third node to the second node, for the second root event; and
when the state of the second node changes to a normal state and one of the one or more retries is received at the second node, changing a state of the second node to the conflating state based on the second conflation event.

### Claim 18 (depends on 17)

The method of claim 17, wherein:
the retry limit is randomized to overcome cyclic deadlocks.

### Claim 19 (depends on 11)

The method of claim 11, wherein:
the first set further comprises a third node;
the third node is stored at a third processing node of the multiple processing nodes;
the third node is the sole parent node of the first set;
the second set further comprises a fourth node;
the fourth node is stored at a fourth processing node of the multiple processing nodes;
the fourth node is the sole parent node of the second set;
the first node is a child node mapped to the third node;
the second node is a child node mapped to the fourth node;
data for the first node and data for the third node are stored at the third node; and
data for the second node and data for the fourth node are stored at the fourth node.

### Claim 20 (depends on 19)

The method of claim 19, wherein:
the first conflation event is received at the first processing node; and
conflating the first set and the second set into the conflated set further comprises:
determining, at the first node, that a parent of the first node is the third node;
sending, from the first node to the third node, a second conflation event identifying the third node and the second node;
changing a state of the third node to a conflating state;
sending, from the third node to the second node, a first root event identifying the third node;
determining, at the second node, that a parent of the second node is the fourth node;
sending, from the second node to the fourth node, a second root event identifying the third node;
determining, at the fourth node, that the third node is lexicographically smaller than the fourth node;
changing a state of the fourth node to a packed state;
sending, from the fourth node to the third node, a data event comprising the data for the second node and the data for the fourth node;
storing the data for the second node and the data for the fourth node at the third node;
changing the state of the third node to a normal state;
sending, from the third node to each of the second node and the fourth node, a change-root event identifying the third node;
deleting the data for the second node and the data for the fourth node from the fourth node;
setting the fourth node to be a child node mapped to the third node;
changing the state of the fourth node to a normal state; and
setting the second node to be a child node mapped to the third node.