Author:
(1) Subhajit Sahu, IIIT Hyderabad, Hyderabad, Telangana, India ([email protected]).
Table of Links
Abstract and 1 Introduction
2 Related Work
3 Preliminaries
4 Approach
5.1 Experimental Setup
5.2 Performance of Dynamic Frontier PageRank
5.3 Strong Scaling of Dynamic Frontier PageRan
6 Conclusion, Acknowledgments, and References
6. CONCLUSION
ACKNOWLEDGMENTS
I would like to thank Prof. Kishore Kothapalli, Prof. Sathya Peri, and Prof. Hemalatha Eedi for their support.
REFERENCES
[1] R. Andersen, F. Chung, and K. Lang. 2007. Local partitioning for directed graphs using pagerank. In in Proc. WAW. 166–178.
[2] Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. 2010. Fast incremental and personalized pagerank. arXiv preprint arXiv:1006.2880 (2010).
[3] Bahman Bahmani, Ravi Kumar, Mohammad Mahdian, and Eli Upfal. 2012. Pagerank on an evolving graph. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. 24–32.
[4] Klaus Berberich, Srikanta Bedathur, Gerhard Weikum, and Michalis Vazirgiannis. 2007. Comparing apples and oranges: normalized pagerank for evolving graphs. In Proceedings of the 16th international conference on world wide web. 1145–1146.
[5] Yen-Yu Chen, Qingqing Gan, and Torsten Suel. 2004. Local methods for estimating pagerank values. In Proceedings of the thirteenth ACM international conference on Information and knowledge management. 381–389.
[6] S. Chien, C. Dwork, R. Kumar, and D. Sivakumar. 2001. Towards Exploiting Link Evolution.
[7] P. Desikan, N. Pathak, J. Srivastava, and V. Kumar. 2005. Incremental Page Rank Computation on Evolving Graphs. In Special Interest Tracks and Posters of the 14th International Conference on World Wide Web (Chiba, Japan) (WWW ’05). Association for Computing Machinery, New York, NY, USA, 1094–1095. https://doi.org/10.1145/1062745.1062885
[8] L. Dhulipala, G.E. Blelloch, and J. Shun. 2019. Low-latency graph streaming using compressed purely-functional trees. In ACM SIGPLAN PLDI. 918–934.
[9] H. Dubey and N. Khare. 2022. Fast parallel computation of PageRank scores with improved convergence time. IJDMMM 14, 1 (2022), 63–88.
[10] A. Fender, N. Thejaswi, and B. Rees. [n. d.]. rapidsai/nvgraph. https://github. com/rapidsai/nvgraph/blob/main/cpp/src/pagerank.cu#L149
[11] P. Garg and K. Kothapalli. 2016. STIC-D: Algorithmic Techniques For Efficient Parallel Pagerank Computation on Real-World Graphs. In Proceedings of the 17th International Conference on Distributed Computing and Networking – ICDCN ’16. ACM Press, 1—10.
[12] H. Giri, M. Haque, and D. Banerjee. 2020. HyPR: Hybrid Page Ranking on Evolving Graphs. In Proc. IEEE 27th International Conference on High Performance Computing, Data, and Analytics (HiPC). 62–71.
[13] Kyung Soo Kim and Yong Suk Choi. 2015. Incremental iteration method for fast pagerank computation. In Proceedings of the 9th International Conference on Ubiquitous Information Management and Communication. 1–5.
[14] S. Kolodziej, M. Aznaveh, M. Bullock, J. David, T. Davis, M. Henderson, Y. Hu, and R. Sandstrom. 2019. The SuiteSparse matrix collection website interface. The Journal of Open Source Software 4, 35 (Mar 2019), 1244.
[15] A.N. Langville and C.D. Meyer. 2006. A reordering for the PageRank problem. SIAM SISC 27, 6 (2006), 2112–2120.
[16] J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. (06 2014).
[17] NVIDIA Corporation. 2019. nvGRAPH Library User’s Guide. https://docs.nvidia. com/cuda/archive/10.1/pdf/nvGRAPH_Library.pdf
[18] Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi. 2015. Efficient pagerank tracking in evolving networks. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 875–884.
[19] L. Page, S. Brin, R. Motwani, and T. Winograd. 1999. The PageRank citation ranking: Bringing order to the web. Technical Report. Stanford InfoLab.
[20] R.P. Pashikanti and S. Kundu. 2022. FPPR: fast pessimistic (dynamic) PageRank to update PageRank in evolving directed graphs on network changes. SNAM 12, 1 (2022), 141.
[21] S.J. Plimpton and K.D. Devine. 2011. MapReduce in MPI for large-scale graph algorithms. Parallel Comput. 37, 9 (2011), 610–632.
[22] Subhajit Sahu, Kishore Kothapalli, and Dip Sankar Banerjee. 2022. Dynamic Batch Parallel Algorithms for Updating PageRank. In 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 1129–1138.
[23] A. Sarma, A. Molla, G. Pandurangan, and E. Upfal. 2013. Fast Distributed PageRank Computation. In Distributed Computing and Networking. Springer Berlin Heidelberg, Berlin, Heidelberg, 11–26.
[24] Zexing Zhan, Ruimin Hu, Xiyue Gao, and Nian Huai. 2019. Fast incremental pagerank on dynamic networks. In International Conference on Web Engineering. Springer, 154–168.
[25] T. Zhang. 2017. Efficient incremental pagerank of evolving graphs on GPU. In IEEE ICCSEC. 1232–1236.
