Graph processing using a mutable multilevel graph representation
US9734607B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 10, 2014 |
| Grant date | Aug 15, 2017 |
| Priority date | — |
| Expiry date | Jul 12, 2035 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/10
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A mutable multilevel data structure representing a graph structure may include multiple read-only levels and a single writable level. Each read-only level may include a vertex table (with references to edge tables on the same level or a different level containing elements of adjacency lists for some vertices) and an edge table (with elements of adjacency lists that changed since the previous read-only level). A hybrid variant may switch between a performance-optimized variant (whose edge tables include complete adjacency lists for vertices whose edge sets were modified) and a space-optimized variant (whose edge tables include only newly added adjacency list elements). The vertex tables and/or the writable level may be implemented using copy-on-write arrays, each including an indirection table and multiple fixed-sized data pages. Computations may be run on the read-only levels or on the writable level and read-only levels.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.