Uploaded image for project: 'Spark'
  1. Spark
  2. SPARK-30432

reduce degree recomputation in StronglyConnectedComponents

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: In Progress
    • Priority: Major
    • Resolution: Unresolved
    • Affects Version/s: 3.1.0
    • Fix Version/s: None
    • Component/s: GraphX
    • Labels:
      None

      Description

       

      So the computation happens every time in the do-while loop, the first time the outer while loop executes. although just once per do-while loop after, it seems, but It does reduce a lot of recomputation;because every time it jump out of the do-while loop,there are no vertices have only out-degree or in-degree,so it's no need to recompute degree to tag the vertices true.

      I have done a small code proposal, because there is a problem when the pregel executions have done,  the degree no need to be recomputed.

       

      for example,the Email-EuAll  data set:http://snap.stanford.edu/data/email-EuAll.html

      do-while loop execute 10 times,and the reduce logic happend 2 times;so it would be helpful when computing StronglyConnectedComponents to reduce degree computation.

       

      I created a branch in my fork: https://github.com/xs-li/spark/blob/master/graphx/src/main/scala/org/apache/spark/graphx/lib/StronglyConnectedComponents.scala

       

      I hope you can consider this small code proposal.

      Thank you very much,

      Best regards,

      xs-li

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              lx-li xiaosen
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated: