You are viewing a plain text version of this content. The canonical link for it is here.

Posted to dev@flink.apache.org by "Vasia Kalavri (JIRA)" <ji...@apache.org> on 2015/02/11 15:58:12 UTC

[jira] [Created] (FLINK-1526) Add Minimum Spanning Tree library method and example

Vasia Kalavri created FLINK-1526:
------------------------------------

             Summary: Add Minimum Spanning Tree library method and example
                 Key: FLINK-1526
                 URL: https://issues.apache.org/jira/browse/FLINK-1526
             Project: Flink
          Issue Type: Task
          Components: Gelly
            Reporter: Vasia Kalavri
            Assignee: Andra Lungu


This issue proposes the addition of a library method and an example for distributed minimum spanning tree in Gelly.

The DMST algorithm is very interesting because it is quite different from PageRank-like iterative graph algorithms. It consists of distinct phases inside the same iteration and requires a mechanism to detect convergence of one phase to proceed to the next one. Current implementations is vertex-centric models are quite long (>1000 lines) and hard to understand.
You can find a description of the algorithm [here | http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | http://www.vldb.org/pvldb/vol7/p1047-han.pdf].




--
This message was sent by Atlassian JIRA
(v6.3.4#6332)