Method of distributed graph loading for minimal communication and good balance via lazy materialization and directory indirection using indexed tabular representation
US11561780B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 13, 2020 |
| Grant date | Jan 24, 2023 |
| Priority date | — |
| Expiry date | Aug 3, 2041 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9024
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques herein minimally communicate between computers to repartition a graph. In embodiments, each computer receives a partition of edges and vertices of the graph. For each of its edges or vertices, each computer stores an intermediate representation into an edge table (ET) or vertex table. Different edges of a vertex may be loaded by different computers, which may cause a conflict. Each computer announces that a vertex resides on the computer to a respective tracking computer. Each tracking computer makes assignments of vertices to computers and publicizes those assignments. Each computer that loaded conflicted vertices transfers those vertices to computers of the respective assignments. Each computer stores a materialized representation of a partition based on: the ET and vertex table of the computer, and the vertices and edges that were transferred to the computer. Edges stored in the materialized representation are stored differently than edges stored in the ET.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.