Parallel edge scan for single-source earliest-arrival in temporal graphs

Patent metadata

Field	Value
Publication number	US-10360263-B2
Application number	US-201715658674-A
Country	US
Kind code	B2
Filing date	Jul 25, 2017
Priority date	Jul 25, 2017
Publication date	Jul 23, 2019
Grant date	Jul 23, 2019

Abstract

Methods, systems, and computer-readable storage media for receiving data representative of the temporal graph, the data representing vertices, edges between vertices, and temporal features, determining a set of earliest-arrival dependencies, each earliest arrival dependency including an earliest feasible edge between vertices from a list of edges of the temporal graph, providing data representative of an edge-scan-dependency graph (ESD-graph) based on the data representative of the temporal graph, and the set of earliest-arrival dependencies, the ESD-graph including vertices representing edges of the temporal graph, and edges representing earliest-arrival dependencies between vertices, providing data representative of a level-assigned ESD-graph including a level assigned to each vertex of the ESD-graph, and determining earliest-arrival times between a source vertex, and each vertex of the temporal graph by executing a parallel edge scan of the level-assigned ESD-graph.

First claim

What is claimed is:

1. A computer-implemented method for determining earliest-arrival times in a temporal graph, the method being executed by one or more processors and comprising:
receiving, by the one or more processors, data representative of the temporal graph, the data representing vertices, edges between vertices, and temporal features;
determining, by the one or more processors, a set of earliest-arrival dependencies, each earliest-arrival dependency comprising an earliest feasible edge between vertices from a list of edges of the temporal graph;
providing, by the one or more processors, data representative of an edge-scan-dependency graph (ESD-graph) based on the data representative of the temporal graph, and the set of earliest-arrival dependencies, the ESD-graph comprising vertices representing edges of the temporal graph, and edges representing earliest-arrival dependencies between vertices;
providing, by the one or more processors, data representative of a level-assigned ESD-graph comprising a property level assigned to each vertex of the ESD-graph; and
determining, by the one or more processors, for a particular departure time, the earliest-arrival times between a source vertex, and each vertex of the temporal graph by executing a parallel edge scan of the level-assigned ESD-graph such that all edges of a respective property level are scanned in parallel.

2. The method of claim 1 , wherein executing the parallel edge scan comprises, for each level, perform an atomic scan operation for each edge in parallel.

3. The method of claim 2 , wherein the atomic scan operation comprises updating a tentative earliest arrival time of a destination vertex an edge if a starting time associated with the edge exceeds the tentative earliest arrival time of an origin vertex of the edge, and an ending time associated with the edge is greater than the tentative earliest arrival time of the destination vertex.

4. The method of claim 3 , wherein updating is performed by compare-and-swap (CAS).

5. The method of claim 1 , further comprising storing all temporal edges of the ESD-graph in memory using a single array.

6. The method of claim 1 , further comprising storing sets of temporal edges in respective arrays, at least one array comprising edges from multiple level, and are ordered based on level within the at least one array.

7. The method of claim 6 , wherein a number of arrays is equal to a number of threads that execute the parallel edge scan.

8. A non-transitory computer-readable storage medium coupled to one or more processors and having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations for parallel edge scan for determining earliest-arrival times in a temporal graph, the operations comprising:
receiving data representative of the temporal graph, the data representing vertices, edges between vertices, and temporal features;
determining a set of earliest-arrival dependencies, each earliest arrival dependency comprising an earliest feasible edge between vertices from a list of edges of the temporal graph;
providing data representative of an edge-scan-dependency graph (ESD-graph) based on the data representative of the temporal graph, and the set of earliest-arrival dependencies, the ESD-graph comprising vertices representing edges of the temporal graph, and edges representing earliest-arrival dependencies between vertices;
providing data representative of a level-assigned ESD-graph comprising a property level assigned to each vertex of the ESD-graph; and
determining, for a particular departure time, the earliest-arrival times between a source vertex, and each vertex of the temporal graph by executing a parallel edge scan of the level-assigned ESD-graph such that all edges of a respective property level are scanned in parallel.

9. The non-transitory computer-readable storage medium of claim 8 , wherein executing the parallel edge scan comprises, for each level, perform an atomic scan operation for each edge in parallel.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the atomic scan operation comprises updating a tentative earliest arrival time of a destination vertex an edge if a starting time associated with the edge exceeds the tentative earliest arrival time of an origin vertex of the edge, and an ending time associated with the edge is greater than the tentative earliest arrival time of the destination vertex.

11. The non-transitory computer-readable storage medium of claim 10 , wherein updating is performed by compare-and-swap (CAS).

12. The non-transitory computer-readable storage medium of claim 8 , wherein operations further comprise storing all temporal edges of the ESD-graph in memory using a single array.

13. The non-transitory computer-readable storage medium of claim 8 , wherein operations further comprise storing sets of temporal edges in respective arrays, at least one array comprising edges from multiple level, and are ordered based on level within the at least one array.

14. The non-transitory computer-readable storage medium of claim 13 , wherein a number of arrays is equal to a number of threads that execute the parallel edge scan.

15. A system, comprising:
a computing device; and
a computer-readable storage device coupled to the computing device and having instructions stored thereon which, when executed by the computing device, cause the computing device to perform operations for parallel edge scan for determining earliest-arrival times in a temporal graph, the operations comprising:
receiving data representative of the temporal graph, the data representing vertices, edges between vertices, and temporal features;
determining a set of earliest-arrival dependencies, each earliest arrival dependency comprising an earliest feasible edge between vertices from a list of edges of the temporal graph;
providing data representative of an edge-scan-dependency graph (ESD-graph) based on the data representative of the temporal graph, and the set of earliest-arrival dependencies, the ESD-graph comprising vertices representing edges of the temporal graph, and edges representing earliest-arrival dependencies between vertices;
providing data representative of a level-assigned ESD-graph comprising a property level assigned to each vertex of the ESD-graph; and
determining, for a particular departure time, the earliest-arrival times between a source vertex, and each vertex of the temporal graph by executing a parallel edge scan of the level-assigned ESD-graph such that all edges of a respective property level are scanned in parallel.

16. The system of claim 15 , wherein executing the parallel edge scan comprises, for each level, perform an atomic scan operation for each edge in parallel.

17. The system of claim 16 , wherein the atomic scan operation comprises updating a tentative earliest arrival time of a destination vertex an edge if a starting time associated with the edge exceeds the tentative earliest arrival time of an origin vertex of the edge, and an ending time associated with the edge is greater than the tentative earliest arrival time of the destination vertex.

18. The system of claim 17 , wherein updating is performed by compare-and-swap (CAS).

19. The system of claim 15 , wherein operations further comprise storing all temporal edges of the ESD-graph in memory using a single array.

20. The system of claim 15 , wherein operations further comprise storing sets of temporal edges in respecti

Assignees

• Sap Se

Inventors

• Ni Peng
• Wang Chen

Classifications

• G06F16/1858

  Parallel file systems, i.e. file systems supporting multiple processors · CPC title

• G06F11/3608 Primary

  using formal methods, e.g. model checking, abstract interpretation (theorem proving G06N5/013) · CPC title

• G06F16/9024 Primary

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

• G06F16/2477

  Temporal data queries · CPC title

• G06F16/212

  with details for data modelling support · CPC title