Efficient method for indexing data transferred between machines in distributed graph processing systems
US10002205B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 20, 2015 |
| Grant date | Jun 19, 2018 |
| Priority date | — |
| Expiry date | Nov 26, 2036 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/278
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques herein index data transferred during distributed graph processing. In an embodiment, a system of computers divides a directed graph into partitions. The system creates one partition per computer and distributes each partition to a computer. Each computer builds four edge lists that enumerate edges that connect the partition of the computer with a partition of a neighbor computer. Each of the four edge lists has edges of a direction, which may be inbound or outbound from the partition. Edge lists are sorted by identifier of the vertex that terminates or originates each edge. Each iteration of distributed graph analysis involves each computer processing its partition and exchanging edge data or vertex data with neighbor computers. Each computer uses an edge list to build a compactly described range of edges that connect to another partition. The computers exchange described ranges with their neighbors during each iteration.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.