Automatic generation of multi-source breadth-first search from high-level graph language
US10133827B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 12, 2015 |
| Grant date | Nov 20, 2018 |
| Priority date | — |
| Expiry date | Dec 20, 2036 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9024
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques are described herein for automatic generation of multi-source breadth-first search (MS-BFS) from high-level graph processing language. In an embodiment, a method involves a computer analyzing original software instructions. The original software instructions are configured to perform multiple breadth-first searches to determine a particular result. Each breadth-first search originates at each of a subset of vertices of a graph. Each breadth-first search is encoded for independent execution. Based on the analyzing, the computer generates transformed software instructions configured to perform a MS-BFS to determine the particular result. Each of the subset of vertices is a source of the MS-BFS. In an embodiment, parallel execution of the MS-BFS is regulated with batches of vertices. In an embodiment, the original software instructions are expressed in Green-Marl graph analysis language. In an embodiment, the transformed software instructions are expressed in a general purpose programming language such as C, C++, Python, or Java.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.