Lightweight temporal graph management engine

Patent metadata

Field	Value
Publication number	US-2016125095-A1
Application number	US-201514932873-A
Country	US
Kind code	A1
Filing date	Nov 4, 2015
Priority date	Nov 5, 2014
Publication date	May 5, 2016
Grant date	—

Abstract

A method and system are provided. The method includes storing, in a memory, temporal data for a temporal graph. The memory includes a temporal graph storage structure having a set of buckets. The temporal data stored in the buckets includes respective data segments implemented using graph edges. Each of the graph edges has a start time and an end time associated therewith. The method further includes the methods, performed by a processor, of: forming an index that categorizes the graph edges based on the end times of the graph edges; positioning the graph edges within respective ones of the buckets for storage using the index such that the graph edges are positioned in the respective ones of the buckets in a chronological order that is based on the end times; and accessing the temporal graph storage structure using the index responsive to a temporal graph query.

First claim

1 . A method, comprising:
storing, in a memory, temporal data for a temporal graph using a temporal graph storage structure having a set of buckets, the temporal data stored in the buckets including respective data segments implemented using graph edges, each of the graph edges having a start time and an end time associated therewith; forming, by a processor, an index that categorizes the graph edges based on the end times of the graph edges; positioning, by the processor, the graph edges within respective ones of the buckets for storage using the index such that the graph edges are positioned in the respective ones of the buckets in a chronological order that is based on the end times; and accessing, by the processor, the temporal graph storage structure using the index responsive to a temporal graph query.

2 . The method of claim 1 , wherein each of the buckets in the set uses respectively different lower bounds and upper bounds on the start times of the graph edges in order to partition the graph edges into the respective ones of the buckets.

3 . The method of claim 2 , wherein, subsequent to graph edge partitioning into the respective ones of the buckets, any of the graph edges in each of the respective ones of the buckets are arranged in a chronologically descending order that is based on the end times of the graph edges.

4 . The method of claim 2 , wherein a modified b+ tree index is used to implement the lower bounds and the upper bounds.

5 . The method of claim 1 , further comprising processing at least one temporal duration snapshot query by forming at least one temporal duration snapshot, the at least one temporal duration snapshot including at least one of a covering snapshot, a persisting snapshot, and an existing snapshot, wherein:
all graph edges in the covering snapshot have start times and end times within a given timeframe; all graph edges in the persisting snapshot are active during the entire given timeframe; and all graph edges in the existing snapshot are active during at least a portion of the given timeframe.

6 . The method of claim 5 , further comprising acquiring at least one consecutive sequence of buckets that includes a set of candidate graph edges in the temporal duration snapshot and verifying that each graph edge in the sequence belongs to the temporal duration snapshot.

7 . The method of claim 5 , further comprising processing at least one temporal duration delta query based on at least one difference between two temporal duration snapshots.

8 . The method of claim 5 , further comprising processing at least one temporal path query by forming at least one temporal path that includes a sequence of at least some of the graph edges wherein, for any two consecutive graph edges in the sequence, a destination node for a previous graph edge is the same as a source node of a later graph edge.

9 . The method of claim 5 , further comprising processing a temporal single source shortest path query by determining a path with an earliest arrival time as a temporal shortest path for use in responding to the temporal single source shortest path query.

10 . The method of claim 9 , further comprising, during the temporal single source shortest path query, inputting a temporal graph, a source node, and a time duration, and outputting a minimal ending traversal time at a subsequent node with respect to the source node through a valid temporal path.

11 . A system, comprising:
a memory for storing temporal data for a temporal graph using a temporal graph storage structure having a set of buckets, the temporal data stored in the buckets including respective data segments implemented using graph edges, each of the graph edges having a start time and an end time associated therewith; and a processor configured to:
form an index that categorizes the graph edges based on the end times of the graph edges;
position the graph edges within respective ones of the buckets for storage using the index such that the graph edges are positioned in the respective ones of the buckets in a chronological order that is based on the end times; and
access the temporal graph storage structure using the index responsive to a temporal graph query.

12 . The system of claim 11 , wherein each of the buckets in the set uses respectively different lower bounds and upper bounds on the start times of the graph edges in order to partition the graph edges into the respective ones of the buckets.

13 . The system of claim 12 , wherein, subsequent to graph edge partitioning into the respective ones of the buckets, any of the graph edges in each of the respective ones of the buckets are arranged in a chronologically descending order that is based on the end times of the graph edges.

14 . The system of claim 12 , wherein a modified b+ tree index is used to implement the lower bounds and the upper bounds.

15 . The system of claim 11 , wherein the processor is further configured to process at least one temporal duration snapshot query by forming at least one temporal duration snapshot, the at least one temporal duration snapshot including at least one of a covering snapshot, a persisting snapshot, and an existing snapshot, wherein:
all graph edges in the covering snapshot have start times and end times within a given timeframe; all graph edges in the persisting snapshot are active during the entire given timeframe; and all graph edges in the existing snapshot are active during at least a portion of the given timeframe.

16 . The system of claim 15 , wherein the processor is further configured to acquire at least one consecutive sequence of buckets that includes a set of candidate graph edges in the temporal duration snapshot and verify that each graph edge in the sequence belongs to the temporal duration snapshot.

17 . The system of claim 15 , wherein the processor is further configured to process at least one temporal duration snapshot query based on at least one difference between two temporal duration snapshots.

18 . The system of claim 17 , wherein the processor is further configured to process at least one temporal path query by forming at least one temporal path that includes a sequence of at least some of the graph edges wherein, for any two consecutive graph edges in the sequence, a destination node for a previous graph edge is the same as a source node of a later graph edge.

19 . The system of claim 15 , wherein the processor is further configured to process a temporal single source shortest path query by determining a path with an earliest arrival time as a temporal shortest path for use in responding to the temporal single source shortest path query.

20 . The system of claim 19 , wherein, during the temporal single shortest path query, the processor is further configured to input a temporal graph, a source node, and a time duration, and output a minimal ending traversal time at a subsequent node with respect to the source node through a valid temporal path.

Assignees

• Nec Lab America Inc

Inventors

• Xu Fengyuan

Classifications

• G06F16/9024 Primary

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

• G06F17/30958 Primary

  Physics · mapped topic

• G06F17/30979

  Physics · mapped topic

• G06F17/30321

  Physics · mapped topic

• G06F17/30598

  Physics · mapped topic