Systems and methods for general-purpose temporal graph computing
US11164348B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 29, 2020 |
| Grant date | Nov 2, 2021 |
| Priority date | — |
| Expiry date | Jul 25, 2040 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06Q50/01
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Systems and methods are provided for performing temporal graph computing. One method may comprise receiving an input temporal graph that have a plurality of edges with each edge connecting from one vertex instance to another vertex instance, generating in-vertices and out-vertices for each vertex instance, merging the in-vertices and out-vertices into hub vertices for each vertex instance and generating a directed acyclic graph (DAG), receiving a minimum path problem, and scanning the DAG once to provide a solution to the minimum path problem. The merging of vertices and generation of the DAG may be performed by sorting all out-vertices using a 2-dimensional radix sort, generating a respective set of hub vertices for each vertex instance, relabeling the in-vertices and the out-vertices to their respective hub vertices for each vertex instance by a parallel binary search and updating edges affected by the relabeling, and assembling relabeled edges and vertices.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.