Out-of-core BFS for shortest path graph queries
US12326866B1 · kind B1 · utility
0Cited by
1References
20Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Mar 29, 2024 |
| Grant date | Jun 10, 2025 |
| Priority date | — |
| Expiry date | Mar 29, 2044 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/278
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A breadth first search (BFS) algorithm is provided that uses out-of-core external storage in a memory constrained system. Memory resources are used as long as they are available and external storage is used when necessary due to memory pressure. The BFS algorithm uses a disk-spilling hash-table (DSH) as the visited set and disk-spilling queues (DSQs) as the BFS frontier queue. To get the most out of the DSH, subsequent inserts and lookups must happen in the same DSH partition. To ensure that consecutive lookups happen in the same DSH partition, the BFS frontier queue is partitioned in a manner similar to the DSH partitions.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.