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

reduce degree recomputation in StronglyConnectedComponents

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: In Progress
    • Major
    • Resolution: Unresolved
    • 3.1.0
    • None
    • GraphX
    • 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

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

            Dates

              Created:
              Updated: