[GIRAPH-96] Support for Graphs with Huge adjacency lists

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 0.1.0
• Component/s: bsp
• Assignee: Unassigned
• Reporter: UNUSED
• Created: 17/Nov/11 14:49
• Updated: 12/May/20 18:23
• Resolved: 12/May/20 18:23

Description

Currently the vertex initialize() method is passed the complete adjacency list as a HashMap. All the current concrete implementations of Vertex iterate over the adjacency list and recreate new Data Structures within the Vertex instance to hold/manipulate the adjacency list. This would seize to be feasible once the size of the adjacency list becomes really huge.

I propose storing the adjacency list and all vertex information (and incoming messages ?) in a distributed data store such as HBase. The adjacency list can be lazily loaded via HBase Scans. I was thinking of an HBase schema where the row Id is a concatenation of VertexID+OutboundVertexId with a single column containing the edge.

Issue Links

• is related to: GIRAPH-153 HBase/Accumulo Input and Output formats
• relates to: GIRAPH-94 Loading vertex ranges from HBase