Handling out-of-order data during stream processing and persisting it in a temporal graph database

Patent metadata

Field	Value
Publication number	US-11983222-B2
Application number	US-202217933386-A
Country	US
Kind code	B2
Filing date	Sep 19, 2022
Priority date	Aug 27, 2020
Publication date	May 14, 2024
Grant date	May 14, 2024

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.

First claim

The invention claimed is:

1. A non-transitory computer readable medium comprising instructions stored thereon, which when executed by at least one processor, causes the 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 existing data for the graph element having a next modification time (NMT) being greater than a timestamp of the new data; and
insert the new data into the temporal graph.

2. The non-transitory computer readable medium of claim 1 , further comprising instructions which when executed by the at least one processor, causes the at least one processor to:
in response to the timestamp being greater than a modification time (MT) of the existing data and the NMT is set to max time, create a new record to insert the new data, set the NMT of the existing data to the timestamp, and set an NMT of the new record to the max time.

3. The non-transitory computer readable medium of claim 1 , further comprising instructions which when executed by the at least one processor, causes the at least one processor to:
in response to the timestamp being equal to a modification time (MT) of the existing data, insert the new data by merging the new data into the existing data.

4. The non-transitory computer readable medium of claim 1 , further comprising instructions which when executed by the at least one processor, causes the at least one processor to:
in response to the timestamp being greater than a modification time (MT) of the existing data and the NMT is not set to max time, create a new record to insert the new data, set an NMT of the new record to the NMT of the existing data and set the NMT of the existing data to the timestamp.

5. The non-transitory computer readable medium of claim 1 , further comprising instructions which when executed by the at least one processor, causes the at least one processor to:
in response to the timestamp being less than a modification time (MT) of the existing data, create a new record to insert the new data and set an NMT of the new record to the MT of the existing data.

6. The non-transitory computer readable medium of claim 1 , further comprising instructions which when executed by the at least one processor, causes the at least one processor to:
determine that the temporal graph does not store the existing data for the graph element having the NMT being greater than the timestamp of the new data; and
create a new record to insert the new data and set an NMT of the new record to max time.

7. 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.

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

9. A system comprising:
at least one processor;
a memory with instructions stored thereon, which when executed by the at least one processor, causes the 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 existing data for the graph element having a next modification time (NMT) being greater than a timestamp of the new data; and
insert the new data into the temporal graph.

10. The system of claim 9 , further comprising instructions which when executed by the at least one processor, causes the at least one processor to:
in response to the timestamp being greater than a modification time (MT) of the existing data and the NMT is set to max time, create a new record to insert the new data, set the NMT of the existing data to the timestamp, and set an NMT of the new record to the max time.

11. The system of claim 9 , further comprising instructions which when executed by the at least one processor, causes the at least one processor to:
in response to the timestamp being equal to a modification time (MT) of the existing data, insert the new data by merging the new data into the existing data.

12. The system of claim 9 , further comprising instructions which when executed by the at least one processor, causes the at least one processor to:
in response to the timestamp being greater than a modification time (MT) of the existing data and the NMT is not set to max time, create a new record to insert the new data, set an NMT of the new record to the NMT of the existing data and set the NMT of the existing data to the timestamp.

13. The system of claim 9 , further comprising instructions which when executed by the at least one processor, causes the at least one processor to:
in response to the timestamp being less than a modification time (MT) of the existing data, create a new record to insert the new data and set an NMT of the new record to the MT of the existing data.

14. The system of claim 9 , further comprising instructions which when executed by the at least one processor, causes the at least one processor to:
determine that the temporal graph does not store the existing data for the graph element having the NMT being greater than the timestamp of the new data; and
create a new record to insert the new data and set an NMT of the new record to max time.

15. The system of claim 9 , 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.

16. The system of claim 9 , wherein each of the edges represent a relationship between interconnecting devices in the computer network.

17. A method comprising:
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 existing data for the graph element having a next modification time (NMT) being greater than a timestamp of the new data; and
insert the new data into the temporal graph.

18. The method of claim 17 , further comprising:
in response to the timestamp being greater than a modification time (MT) of the existing data and the NMT is set to max time, creating a new record to insert the new data, set the NMT of the existing data to the timestamp, and set an NMT of the new record to the max time.

19. The method of claim 17 , further comprising:
in response to the timestamp being equal to a modification time (MT) of the existing data, inserting the new data by merging the new data into the existing data.

20. The method of claim 17 , further comprising:
in response to the timestamp being greater than a modification time (MT) of the existing data and the NMT is not set to max time, creating a new record to insert the new data, set an NMT of the new record to the NMT of the existing data and set the NMT of the existing data to the timestamp.

Assignees

• Cisco Tech Inc

Inventors

• Raghavendra Arun Kumar
• NARAYANAN Bhalaji
• Nethi Ramesh
• Simhadri Mehar

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title

• G06F16/24568

  Data stream processing; Continuous queries · CPC title