Fast detection of vertex-connectivity with distance constraint
US10831829B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 9, 2018 |
| Grant date | Nov 10, 2020 |
| Priority date | — |
| Expiry date | Apr 26, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9532
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Embodiments perform real-time vertex connectivity checks in graph data representations via a multi-phase search process. This process includes an efficient first search phase using landmark connectivity data that is generated during a preprocessing phase. Landmark connectivity data maps the connectivity of a set of identified landmarks in a graph to other vertices in the graph. Upon determining that the subject vertices are not closely related via landmarks, embodiments implement a second search phase that performs a brute-force search for connectivity, between the subject vertices, among the graph's non-landmark vertices. This brute-force search prevents exploration of cyclical paths by recording the vertices on a currently-explored path in a stack data structure. The second search phase is automatically aborted upon detecting that the non-landmark vertices in the graph are over a threshold density. In this case, embodiments perform a third search phase involving either a modified breadth-first search or modified bidirectional search.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.