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
