[jira] [Closed] (FLINK-2661) Add a Node Splitting Technique to Overcome the Limitations of Skewed Graphs

["Andra Lungu (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/FLINK-2661?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Andra Lungu closed FLINK-2661.
------------------------------
    Resolution: Won't Fix

> 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
(v6.3.4#6332)