flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (FLINK-2661) Add a Node Splitting Technique to Overcome the Limitations of Skewed Graphs
Date Mon, 14 Sep 2015 19:32:45 GMT

    [ https://issues.apache.org/jira/browse/FLINK-2661?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14744092#comment-14744092

ASF GitHub Bot commented on FLINK-2661:

Github user andralungu closed the pull request at:


> Add a Node Splitting Technique to Overcome the Limitations of Skewed Graphs
> ---------------------------------------------------------------------------
>                 Key: FLINK-2661
>                 URL: https://issues.apache.org/jira/browse/FLINK-2661
>             Project: Flink
>          Issue Type: Task
>          Components: Gelly
>    Affects Versions: 0.10
>            Reporter: Andra Lungu
>            Assignee: Andra Lungu
> Skewed graphs raise unique challenges to computation models such as Gelly's vertex-centric
or GSA iterations. This is mainly because of the fact that these approaches uniformly process
vertices regardless of their degree distribution. 
> In vertex-centric, for instance, a skewed node will take more time to process its neighbors
compared to the other nodes in the graph. The first will act as a straggler causing the latter
to remain idle until it finishes its computation. 
> This issue can be mitigated by splitting a high-degree node into subnodes and evenly
distributing the edges to the the resulted subvertices. The computation will then be performed
on the split vertex. 
> To this end, we should add a Splitting API on top of Gelly which can help:
> - determine skewed nodes 
> - split them
> - merge them back at the end of the computation, given a user defined combiner.
> To illustrate the usage of these methods, we should add an example as well as a separate
entry in the documentation.

This message was sent by Atlassian JIRA

View raw message