# US 2022/0067099 A1 · Handling out-of-order data during stream processing and persisting it in a temporal graph database

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

- Number: US 2022/0067099 A1
- Document ID: US20220067099A1
- Status: Published application
- Kind: A1
- Application number: 17/077,511
- Filed: 2020-10-22
- Published: 2022-03-03
- Earliest claimed: 2020-08-27
- Assignees: Cisco Technology, Inc.
- Applicants: Cisco Technology, Inc.
- Inventors: Arun Kumar Raghavendra; Bhalaji Narayanan; Ramesh Nethi; Mehar Simhadri
- Web page: https://patentgrep.com/patent/US20220067099A1

## CPC

- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 16/24568: {Data stream processing; Continuous queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present technology addresses deficiencies associated with common practices for handling out of order data in a streaming data database. An aspect of the present technology is avoid storing out of order data in a snapshot but just store the out of order data as additional data linked to the temporal graph. The present technology receives out of order data and records a modification time for the data and a next modification time for the data that equals a timestamp of data previously stored in the database. If there is also data in the database for a time earlier than the timestamp of the out of order data, the earlier data is adjusted so that its next modification time matches the timestamp of the out of order data.

## Claims

### Claim 1

A non-transitory computer readable medium comprising instructions stored thereon, the instructions are effective to cause at least one processor to:
receive new data pertaining to a graph element in a temporal graph, the temporal graph comprising different types of graph elements including vertices and edges, for storing information of a computer network;
determine that the temporal graph already stores second data for the graph element having a timestamp denoting a second time, wherein the new data was recorded at a first time that is the same or earlier than the second time; and
insert the new data into the temporal graph by recording data for the graph element in a temporal graph database with a timestamp for the new data denoting the first time and a next modification time for the new data that denotes the second time.

### Claim 2 (depends on 1)

The non-transitory computer readable medium of claim 1, comprising further instructions that are effective to cause the at least one processor to:
prior to the insertion of the new data into the temporal graph, determine that the temporal graph already stores third data for the graph element having a timestamp for the third data denoting a third time and that has a next modification time for the third data that denotes the second time, wherein the first time that is associated with the new data is after the third time, but prior to the second time; and
update the next modification time for the third data to denote the first time.

### Claim 3 (depends on 1)

The non-transitory computer readable medium of claim 1, wherein the determination that the temporal graph already stores second data for the graph element having a timestamp denoting a second time involves determining that the new data is earlier than any timestamp associated with data for the graph element in the temporal graph.

### Claim 4 (depends on 1)

The non-transitory computer readable medium of claim 1, comprising further instructions that are effective to cause the at least one processor to:
determine that the first time equals the second time, and thereby no update to the second data is necessary.

### Claim 5 (depends on 1)

The non-transitory computer readable medium of claim 1, comprising further instructions that are effective to cause the at least one processor to:
receive a request to produce a snapshot of a portion of the temporal graph, wherein the request identifies one or more data elements and a specified time for which to produce the snapshot; and
search the temporal graph for all data that has a modification time less than or equal to the specified time coupled with a next modification time greater than the specified time.

### Claim 6 (depends on 1)

The non-transitory computer readable medium of claim 1, comprising further instructions that are effective to cause the at least one processor to:
receive a request to produce a current snapshot of a portion of the temporal graph, wherein the request identifies one or more data elements; and
search the temporal graph for all data that has a next modification time set to the maximum value.

### Claim 7 (depends on 1)

The non-transitory computer readable medium of claim 1, wherein each of the vertices represent at least one of interconnecting devices in the computer network or metric elements representing operational information related to the interconnecting devices.

### Claim 8 (depends on 1)

The non-transitory computer readable medium of claim 1, wherein each of the edges represent a relationship between interconnecting devices in the computer network.

### Claim 9

A method:
receiving new data pertaining to a graph element in a temporal graph, the temporal graph comprising different types of graph elements including vertices and edges, for storing information of a computer network;
determining that the temporal graph already stores second data for the graph element having a timestamp denoting a second time, wherein the new data was recorded at a first time that is the same or earlier than the second time; and
inserting the new data into the temporal graph by recording data for the graph element in a temporal graph database with a timestamp for the new data denoting the first time and a next modification time for the new data that denotes the second time.

### Claim 10 (depends on 9)

The method of claim 9, comprising:
prior to the insertion of the new data into the temporal graph, determining that the temporal graph already stores third data for the graph element having a timestamp for the third data denoting a third time and that has a next modification time for the third data that denotes the second time, wherein the first time that is associated with the new data is after the third time, but prior to the second time; and
update the next modification time for the third data to denote the first time.

### Claim 11 (depends on 9)

The method of claim 9, wherein the determination that the temporal graph already stores second data for the graph element having a timestamp denoting a second time involves determining that the new data is earlier than any timestamp associated with data for the graph element in the temporal graph.

### Claim 12 (depends on 9)

The method of claim 9, comprising:
determining that the first time equals the second time, and thereby no update to the second data is necessary.

### Claim 13 (depends on 9)

The method of claim 9, comprising:
receiving a request to produce a snapshot of a portion of the temporal graph, wherein the request identifies one or more data elements and a specified time for which to produce the snapshot; and
searching the temporal graph for all data that has a modification time less than or equal to the specified time coupled with a next modification time greater than the specified time.

### Claim 14 (depends on 9)

The method of claim 9, comprising:
receiving a request to produce a current snapshot of a portion of the temporal graph, wherein the request identifies one or more data elements; and
searching the temporal graph for all data that has a next modification time set to a maximum value.

### Claim 15

A system comprising:
at least one non-transitory computer readable medium comprising instructions stored thereon; and
at least one processor effective to executing the instructions such that when executed the instructions are effective to cause at least one processor to:
receive new data pertaining to a graph element in a temporal graph, the temporal graph comprising different types of graph elements including vertices and edges, for storing information of a computer network;
determine that the temporal graph already stores second data for the graph element having a timestamp denoting a second time, wherein the new data was recorded at a first time that is the same or earlier than the second time; and
insert the new data into the temporal graph by recording data for the graph element in a temporal graph database with a timestamp for the new data denoting the first time and a next modification time for the new data that denotes the second time.

### Claim 16 (depends on 15)

The system of claim 15, comprising further instructions that are effective to cause the at least one processor to:
prior to the insertion of the new data into the temporal graph, determine that the temporal graph already stores third data for the graph element having a timestamp for the third data denoting a third time and that has a next modification time for the third data that denotes the second time, wherein the first time that is associated with the new data is after the third time, but prior to the second time; and
update the next modification time for the third data to denote the first time.

### Claim 17 (depends on 15)

The system of claim 15, wherein the determination that the temporal graph already stores second data for the graph element having a timestamp denoting a second time involves determining that the new data is earlier than any timestamp associated with data for the graph element in the temporal graph.

### Claim 18 (depends on 15)

The system of claim 15, comprising further instructions that are effective to cause the at least one processor to:
determine that the first time equals the second time, and thereby no update to the second data is necessary.

### Claim 19 (depends on 15)

The system of claim 15, comprising further instructions that are effective to cause the at least one processor to:
receive a request to produce a snapshot of a portion of the temporal graph, wherein the request identifies one or more data elements and a specified time for which to produce the snapshot; and
search the temporal graph for all data that has a modification time less than or equal to the specified time coupled with a next modification time greater than the specified time.

### Claim 20 (depends on 15)

The system of claim 15, comprising further instructions that are effective to cause the at least one processor to:
receive a request to produce a current snapshot of a portion of the temporal graph, wherein the request identifies one or more data elements; and
search the temporal graph for all data that has a next modification time set to a maximum value.
