[
https://issues.apache.org/jira/browse/FLINK-2634?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14742888#comment-14742888
]
ASF GitHub Bot commented on FLINK-2634:
---------------------------------------
Github user vasia commented on the pull request:
https://github.com/apache/flink/pull/1105#issuecomment-139958798
Hi,
I agree with @fhueske that we should consider porting the existing DataSet
example to the Gelly library. The algorithm is a bit different and it's not
very clear (at least to me) which one would be the most efficient. The DataSet
implementation applies the optimization that grouping happens on vertices with
low degrees. The one we currently have in Gelly (and this one) applies the
optimization that the vertex with the lowest ID will be the one detecting the
triangle.
@andralungu, we have chosen these implementations for your thesis in order
to test a specific method and prove a point. This doesn't necessarily mean that
this is the most efficient way to implement triangle counting. Ideally, we
should analyze the complexity of each implementation and run experiments to
determine which one is best to add to the library.
Also, we should definitely support any `Key` type and value types and we
should update existing library methods that assume a particular type for no
good reason.
> Add a Vertex-centric Version of the Tringle Count Library Method
> ----------------------------------------------------------------
>
> Key: FLINK-2634
> URL: https://issues.apache.org/jira/browse/FLINK-2634
> Project: Flink
> Issue Type: Task
> Components: Gelly
> Affects Versions: 0.10
> Reporter: Andra Lungu
> Assignee: Andra Lungu
> Priority: Minor
>
> The vertex-centric version of this algorithm receives an undirected graph as
> input and outputs the total number of triangles formed by the graph's edges.
> The implementation consists of three phases:
> 1). Select neighbours with id greater than the current vertex id.
> 2). Propagate each received value to neighbours with higher id.
> 3). Compute the number of Triangles by verifying if the final vertex contains
> the sender's id in its list.
> As opposed to the GAS version, all these three steps will be performed via
> message passing.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
