You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@giraph.apache.org by Mohit Mohit Daga <md...@kth.se> on 2022/03/22 22:27:36 UTC

Idea for a Google Summer of Code Project

Hej,

My name is Mohit Daga. I am a PhD student at KTH - Sweden. I study theory of distributed graph algorithms. In the theory community, a model called the Congested Clique model [0] is exactly similar to the vertex centric model of Giraph. Through this email, I  would like to pitch a project idea for this year's GSOC. In the year 2013, I did a GSOC project with another org: BRLCAD [1]. I discussed doing a project with Giraph last year too, but due to a pandemic related issue,  I could not finish the proposal. I sincerely  apologise for that.

The main problems that are studied in the theory of distributed graph algorithms - community (henceforth, theory community) are minimum cuts, the shortest paths, minimum spanning trees etc. Now choosing "the one" out of them is tricky, unless we find some applications.  I discussed this last year with *Dionysios* and *Claudio*. I got some suggestions from them.

The shortest path problem has an application in **designing recommender system** [2]. Plus additionally, we already have many results in the theory community for the shortest path problems in the congested clique model (the model that is vertex centric, and  exactly similar to Giraph).

**To add to the excitement, a 2021 results claim O(log^2 log n) round algorithm [3] for all pair the shortest path (APSP)**. Here, rounds are similar to the iterations.

My work is mainly in the theoretical side. My PhD graduation is around November 2023. IMHO, the recent papers appearing in A* conferences in theory community (eg. PODC, STOC, FOCS, and SODA), in relation with the distributed graph algorithm could lead to some  very good practical results. A lot of them, I believe, have not been tried (happy to be corrected), also they are very recent. A  result [5] on APSP is so simple, and uses **randomization** to give provable guarantees on finding weighted APSP. Though appears  for a different model.

In this email, I just wanted to basically say a "Hi". I shall work more towards preparing an application, in the coming weeks. In the meanwhile, any comments or suggestions would be super useful.

Cheers!
Mohit Daga


[0] https://www.cs.tau.ac.il/~roshman/papers/podc14_clique.pdf
[1] https://brlcad.org/wiki/User:Level_zero/index
[2]  https://towardsdatascience.com/shortest-path-similarity-a-fresh-breath-to-item-based-recommendations-9ac3d6ba7240
[3] https://dl.acm.org/doi/pdf/10.1145/3409964.3461784   
[4] https://giraph.apache.org/intro.html
[5] https://arxiv.org/pdf/1811.03337.pdf
[6] PODC https://www.podc.org/ STOC  http://acm-stoc.org/ FOCS: http://ieee-focs.org/ SODA https://www.siam.org/conferences/cm/conference/soda21    

Re: Idea for a Google Summer of Code Project

Posted by SS J <su...@gmail.com>.
Thank you for your update

On Wed, 23 Mar 2022, 3:57 am Mohit Mohit Daga, <md...@kth.se> wrote:

> Hej,
>
> My name is Mohit Daga. I am a PhD student at KTH - Sweden. I study theory
> of distributed graph algorithms. In the theory community, a model called
> the Congested Clique model [0] is exactly similar to the vertex centric
> model of Giraph. Through this email, I  would like to pitch a project idea
> for this year's GSOC. In the year 2013, I did a GSOC project with another
> org: BRLCAD [1]. I discussed doing a project with Giraph last year too, but
> due to a pandemic related issue,  I could not finish the proposal. I
> sincerely  apologise for that.
>
> The main problems that are studied in the theory of distributed graph
> algorithms - community (henceforth, theory community) are minimum cuts, the
> shortest paths, minimum spanning trees etc. Now choosing "the one" out of
> them is tricky, unless we find some applications.  I discussed this last
> year with *Dionysios* and *Claudio*. I got some suggestions from them.
>
> The shortest path problem has an application in **designing recommender
> system** [2]. Plus additionally, we already have many results in the theory
> community for the shortest path problems in the congested clique model (the
> model that is vertex centric, and  exactly similar to Giraph).
>
> **To add to the excitement, a 2021 results claim O(log^2 log n) round
> algorithm [3] for all pair the shortest path (APSP)**. Here, rounds are
> similar to the iterations.
>
> My work is mainly in the theoretical side. My PhD graduation is around
> November 2023. IMHO, the recent papers appearing in A* conferences in
> theory community (eg. PODC, STOC, FOCS, and SODA), in relation with the
> distributed graph algorithm could lead to some  very good practical
> results. A lot of them, I believe, have not been tried (happy to be
> corrected), also they are very recent. A  result [5] on APSP is so simple,
> and uses **randomization** to give provable guarantees on finding weighted
> APSP. Though appears  for a different model.
>
> In this email, I just wanted to basically say a "Hi". I shall work more
> towards preparing an application, in the coming weeks. In the meanwhile,
> any comments or suggestions would be super useful.
>
> Cheers!
> Mohit Daga
>
>
> [0] https://www.cs.tau.ac.il/~roshman/papers/podc14_clique.pdf
> [1] https://brlcad.org/wiki/User:Level_zero/index
> [2]
> https://towardsdatascience.com/shortest-path-similarity-a-fresh-breath-to-item-based-recommendations-9ac3d6ba7240
> [3] https://dl.acm.org/doi/pdf/10.1145/3409964.3461784
> [4] https://giraph.apache.org/intro.html
> [5] https://arxiv.org/pdf/1811.03337.pdf
> [6] PODC https://www.podc.org/ STOC  http://acm-stoc.org/ FOCS:
> http://ieee-focs.org/ SODA
> https://www.siam.org/conferences/cm/conference/soda21