ParaPLL: Fast Parallel Shortest-path Distance Query on Large-scale Weighted Graphs

ABSTRACT

Determining the shortest-path distance between vertices in the weighted graph is an important problem for a broad range of fields, such as context-aware search and route selection. While many efficient methods for querying shortest-path distance have been proposed, they are poorly suited for parallel architectures, such as multi-core CPUs or computer clusters, due to the strong task dependencies. In this paper, we propose ParaPLL, a new parallelism-friendly framework for fast shortest-path distance query on large-scale weighted graphs. ParaPLL exploits intra-node and inter-node parallelism by using shared memory and message passing paradigms respectively. We also design task assignment and synchronization policies, which allow ParaPLL to reach remarkable speedups compared to state-of-the-art solutions. Moreover, we also prove the correctness of ParaPLL. To the best of our knowledge, ParaPLL is the first parallel framework that utilizing pruned landmark labeling to accelerate shortest-path distance queries on large-scale weighted graphs. Our evaluation results show that ParaPLL is 9.46 times faster than the corresponding serial version on a weighted 0.3M-vertex graph using a 12-core computer. ParaPLL on a 6-node computer cluster can also achieve a speedup of up to 5.6 over the single-node implementation.

References

1. 2018. CAIDA. (2018). http://www.caida.org/data
2. 2018. USA Road Network. (2018). http://www.diag.uniroma1.it/challenge9/data/tiger/
3. 2018. Xeon X5680 Benchmark. (2018). http://ranker.sisoftware.net/
4. Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 349--360.
5. Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan. 2006. Group formation in large social networks: membership, growth, and evolution. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 44--54.
6. Randeep Bhatia, Fang Hao, Murali Kodialam, and TV Lakshman. 2015. Optimized network traffic engineering using segment routing. In Computer Communications (INFOCOM), 2015 IEEE Conference on. IEEE, 657--665.
7. Venkatesan T Chakaravarthy, Fabio Checconi, Prakash Murali, Fabrizio Petrini, and Yogish Sabharwal. 2017. Scalable single source shortest path algorithms for massively parallel systems. IEEE Transactions on Parallel and Distributed Systems 28, 7 (2017), 2031--2045.
8. Yurong Cheng, Ye Yuan, Lei Chen, Guoren Wang, Christophe Giraud-Carrier, and Yongjiao Sun. 2016. Distr: a distributed method for the reachability query over large uncertain graphs. IEEE Transactions on Parallel and Distributed Systems 27, 11 (2016), 3172--3185.
9. Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. 2003. Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32, 5 (2003), 1338--1355.
10. Thomas H Cormen. 2009. Introduction to algorithms. MIT press.
11. Damir Ferizovic.2015. Parallel Pruned Landmark Labeling for Shortest Path Queries on Unit-Weight Networks. Ph.D. Dissertation. National Research Center.
12. Ada Wai-Chee Fu, Huanhuan Wu, James Cheng, and Raymond Chi-Wing Wong. 2013. Is-label: an independent-set based labeling scheme for point-to-point distance querying. Proceedings of the VLDB Endowment 6, 6 (2013), 457--468.
13. Ruoming Jin, Ning Ruan, Yang Xiang, and Victor Lee. 2012. A highway-centric labeling approach for answering distance queries on large sparse graphs. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM, 445--456.
14. Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Predicting positive and negative links in online social networks. In Proceedings of the 19th international conference on World wide web. ACM, 641--650.
15. Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD) 1, 1 (2007), 2.
16. Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, James C Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. ACM, 135--146.
17. Ashwin Paranjape, Austin R Benson, and Jure Leskovec. 2017. Motifs in temporal networks. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. ACM, 601--610.
18. Michalis Potamias, Francesco Bonchi, Carlos Castillo, and Aristides Gionis. 2009. Fast shortest path distance estimation in large networks. In Proceedings of the 18th ACM conference on Information and knowledge management. ACM, 867--876.
19. Kun Qiu, Siyuan Huang, Qiongwen Xu, Jin Zhao, Xin Wang, and Stefano Secci. 2017. ParaCon: A Parallel Control Plane for Scaling Up Path Computation in SDN. IEEE Transactions on Network and Service Management 14, 4 (2017), 978--990.
20. Matthew Richardson, Rakesh Agrawal, and Pedro Domingos. 2003. Trust management for the semantic web. In International semantic Web conference. Springer, 351--368.
21. Antti Ukkonen, Carlos Castillo, Debora Donato, and Aristides Gionis. 2008. Searching the wikipedia with contextual information. In Proceedings of the 17th ACM conference on Information and knowledge management. ACM, 1351--1352.
22. Kai Wang, Guoqing (Harry) Xu, Zhendong Su, and Yu David Liu. 2015. GraphQ: Graph Query Processing with Abstraction Refinement-Scalable and Programmable Analytics over Very Large Graphs on a Single PC.. In USENIX Annual Technical Conference. 387--401.
23. Fang Wei. 2010. TEDI: efficient shortest path query answering on graphs. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. ACM, 99--110.
24. Qiongwen Xu, Xu Zhang, Jin Zhao, Xin Wang, and Tilman Wolf. 2016. Fast shortest-path queries on large-scale graphs. In Network Protocols (ICNP), 2016 IEEE 24th International Conference on. IEEE, 1--10.
25. Sihem Amer Yahia, Michael Benedikt, Laks VS Lakshmanan, and Julia Stoyanovich. 2008. Efficient network aware search in collaborative tagging sites. Proceedings of the VLDB Endowment 1, 1 (2008), 710--721.
26. Xiaofei Zhang and Lei Chen. 2017. Distance-aware selective online query processing over large distributed graphs. Data Science and Engineering 2, 1 (2017), 2--21.
27. Lei Zou, M Tamer Özsu, Lei Chen, Xuchuan Shen, Ruizhe Huang, and Dongyan Zhao. 2014. gStore: a graph-based SPARQL query engine. The VLDB journal 23, 4 (2014), 565--590.

Index Terms

• Computing methodologies

  • Parallel computing methodologies

    • Parallel algorithms

      • Massively parallel algorithms

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Shortest paths