You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@giraph.apache.org by "Arun Suresh (Created) (JIRA)" <ji...@apache.org> on 2011/11/17 15:50:51 UTC
[jira] [Created] (GIRAPH-96) Support for Graphs with Huge adjacency
lists
Support for Graphs with Huge adjacency lists
--------------------------------------------
Key: GIRAPH-96
URL: https://issues.apache.org/jira/browse/GIRAPH-96
Project: Giraph
Issue Type: Improvement
Reporter: Arun Suresh
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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (GIRAPH-96) Support for Graphs with Huge
adjacency lists
Posted by "Gianmarco De Francisci Morales (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/GIRAPH-96?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13152101#comment-13152101 ]
Gianmarco De Francisci Morales commented on GIRAPH-96:
------------------------------------------------------
In my opinion this would make things too complex.
I wouldn't like to keep my graph in HBase to run Giraph on it.
Also, this makes HBase a dependency.
I agree that this is a nice option to have but I wouldn't make it the default.
Finally, a similar goal could be attained by streaming edges to disk and reading them with sequential scans when performing supersteps. This requires no network connection and should be much faster.
You just need good out-of-core data structures and algorithms.
> Support for Graphs with Huge adjacency lists
> --------------------------------------------
>
> Key: GIRAPH-96
> URL: https://issues.apache.org/jira/browse/GIRAPH-96
> Project: Giraph
> Issue Type: Improvement
> Components: bsp
> Affects Versions: 0.70.0
> Reporter: Arun Suresh
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (GIRAPH-96) Support for Graphs with Huge
adjacency lists
Posted by "Jakob Homan (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/GIRAPH-96?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13152392#comment-13152392 ]
Jakob Homan commented on GIRAPH-96:
-----------------------------------
The LinkedIn SNA project I've been meaning to look at for this type of problem is http://sna-projects.com/kamikaze/ for storing compressed integer arrays. This project is being used by the distributed graph team, which has certainly dealt with the issues we're running into.
> Support for Graphs with Huge adjacency lists
> --------------------------------------------
>
> Key: GIRAPH-96
> URL: https://issues.apache.org/jira/browse/GIRAPH-96
> Project: Giraph
> Issue Type: Improvement
> Components: bsp
> Affects Versions: 0.70.0
> Reporter: Arun Suresh
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (GIRAPH-96) Support for Graphs with Huge
adjacency lists
Posted by "Arun Suresh (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/GIRAPH-96?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13152087#comment-13152087 ]
Arun Suresh commented on GIRAPH-96:
-----------------------------------
Looks like Claudio beat me to a similar suggestion [GIRAPH-94|https://issues.apache.org/jira/browse/GIRAPH-94]
My proposal was more for a standard means of storing vertex/adjacency list information. The Giraph framework would handle the storage and would expose APIs which the Vertex reader can use to store the information as it reads the graph. The user would then not be required to subclass a Vertex class and implement the initialize() method. All adjacency list/vertex manipulation would go thru the common data store.
> Support for Graphs with Huge adjacency lists
> --------------------------------------------
>
> Key: GIRAPH-96
> URL: https://issues.apache.org/jira/browse/GIRAPH-96
> Project: Giraph
> Issue Type: Improvement
> Reporter: Arun Suresh
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (GIRAPH-96) Support for Graphs with Huge adjacency
lists
Posted by "Arun Suresh (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/GIRAPH-96?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Arun Suresh updated GIRAPH-96:
------------------------------
Component/s: bsp
Affects Version/s: 0.70.0
> Support for Graphs with Huge adjacency lists
> --------------------------------------------
>
> Key: GIRAPH-96
> URL: https://issues.apache.org/jira/browse/GIRAPH-96
> Project: Giraph
> Issue Type: Improvement
> Components: bsp
> Affects Versions: 0.70.0
> Reporter: Arun Suresh
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (GIRAPH-96) Support for Graphs with Huge
adjacency lists
Posted by "Claudio Martella (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/GIRAPH-96?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13152291#comment-13152291 ]
Claudio Martella commented on GIRAPH-96:
----------------------------------------
it is indeed a nice discussion, the amount of data to be read is the same after all, but we're talking about random i/o here. It's a possibility. Also, answering to Gianmarco, the idea of having an HBase InputReader is the same as the current discussion on supporting Hive, Pig and HCatalog. If you store your data in HBase it can be quite useful, as much as it is not for MR. The lazy-approach could be something to investigate and anyway something that would be necessary only with huge graphs or, as in my case, where we have computations that don't necessarily touch the whole graph.
Good out-of-core data structures/maps are difficult to find around, maybe linkedin's krati or leveldb (but i guess we'd have license issues there).
> Support for Graphs with Huge adjacency lists
> --------------------------------------------
>
> Key: GIRAPH-96
> URL: https://issues.apache.org/jira/browse/GIRAPH-96
> Project: Giraph
> Issue Type: Improvement
> Components: bsp
> Affects Versions: 0.70.0
> Reporter: Arun Suresh
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (GIRAPH-96) Support for Graphs with Huge
adjacency lists
Posted by "Avery Ching (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/GIRAPH-96?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13152203#comment-13152203 ]
Avery Ching commented on GIRAPH-96:
-----------------------------------
The general issue of overloading our memory and working out of core has been discussed a little in GIRAPH-45 as well. I suppose you could implement a BasicVertex that loaded everything on demand from HBase, but I suspect it would be a little slow, but depends on the application.
> Support for Graphs with Huge adjacency lists
> --------------------------------------------
>
> Key: GIRAPH-96
> URL: https://issues.apache.org/jira/browse/GIRAPH-96
> Project: Giraph
> Issue Type: Improvement
> Components: bsp
> Affects Versions: 0.70.0
> Reporter: Arun Suresh
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira