Multi-source breadth-first search (Ms-Bfs) technique and graph processing system that applies it
US10949466B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 12, 2019 |
| Grant date | Mar 16, 2021 |
| Priority date | — |
| Expiry date | Dec 12, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/90335
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques herein minimize memory needed to store distances between vertices of a graph for use during a multi-source breadth-first search (MS-BFS). In an embodiment, during each iteration of a first sequence of iterations of a MS-BFS, a computer updates a first matrix that contains elements that use a first primitive integer type having a first width to record a distance from a source vertex of a graph to another vertex. The computer detects that a count of iterations of the first sequence of iterations exceeds a threshold. Responsively, the computer creates a second matrix that contains elements that use a second primitive integer type having a second width that is larger than the first width to record a distance from a source vertex of the graph to another vertex. During each iteration of a second sequence of iterations of the MS-BFS, the computer updates the second matrix.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.