Dynamic asynchronous traversals for distributed graph queries
US11675785B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 31, 2020 |
| Grant date | Jun 13, 2023 |
| Priority date | — |
| Expiry date | Jan 31, 2040 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/289
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques are described for enabling in-memory execution of any-sized graph data query by utilizing both depth first search (DFS) principles and breadth first search (BFS) principles to control the amount of memory used during query execution. Specifically, threads implementing a graph DBMS switch between a BFS mode of data traversal and a DFS mode of data traversal. For example, when a thread detects that there are less than a configurable threshold number of intermediate results in memory, the thread enters BFS-based traversal techniques to increase the number of intermediate results in memory. When the thread detects that there are at least the configurable threshold number of intermediate results in memory, the thread enters DFS mode to produce final results, which generally works to move the intermediate results that are currently available in memory to final query results, thereby reducing the number of intermediate results in memory.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.