Abstract
Triangle counting is a graph algorithm that calculates the number of triangles in a graph, the number of triangles is a key metric for a large number of graph algorithms. Traditional triangle counting algorithms are divided into vertex-iterator and edge-iterator when traversing the graph. As the scale of graph data grows, the use of CPU with other architectural platforms for triangle counting has become mainstream. Our accelerating method proposes an algorithm for triangle counting on a single machine GPU, and performs a two-dimensional partition algorithm for large-scale graph data, in order to ensure that large graph data can be correctly loaded into GPU memory and the independence of each partition to obtain the right result. According to the high concurrency of GPU, a bit-wise operation intersection algorithm is proposed. We experiment with our algorithm to verify that our method effectively speeds up triangle counting algorithm on a single-machine GPU.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chen, P.-L., Chou, C.-K., Chen, M.-S.: Distributed algorithms for k-truss decomposition. In: 2014 IEEE International Conference on Big Data (Big Data), pp. 471–480. IEEE (2014)
Li, X., Chang, L., Zheng, K., Huang, Z., Zhou, X.: Ranking weighted clustering coefficient in large dynamic graphs. World Wide Web 20, 855–883 (2017). https://doi.org/10.1007/s11280-016-0420-2
Bisson, M., Fatica, M.: High performance exact triangle counting on GPUs. IEEE Trans. Parallel Distrib. Syst. 28(12), 3501–3510 (2017)
Qi, X., Wang, M., Wen, Y., Zhang, H., Yuan, X.: Weighted cost model for optimized query processing. In: Zhao, X., Yang, S., Wang, X., Li, J. (eds.) WISA 2022. LNCS, vol. 13579, pp. 473–484. Springer International Publishing, Cham (2022). https://doi.org/10.1007/978-3-031-20309-1_42
Shun, J., Tangwongsan, K.: Multicore triangle computations without tuning. In: 2015 IEEE 31st International Conference on Data Engineering, pp. 149–160. IEEE (2015)
Giechaskiel, I., Panagopoulos, G., Yoneki, E.: PDTL: parallel and distributed triangle listing for massive graphs. In: 2015 44th International Conference on Parallel Processing, pp. 370–379. IEEE (2015)
Wang, X., et al.: Triangle counting accelerations: from algorithm to in-memory computing architecture. IEEE Trans. Comput. 71(10), 2462–2472 (2021)
Wang, L., Wang, Y., Yang, C., Owens, J.D.: A comparative study on exact triangle counting algorithms on the GPU. In: Proceedings of the ACM Workshop on High Performance Graph Processing, pp. 1–8 (2016)
Green, O., et al.: Logarithmic radix binning and vectorized triangle counting. In: 2018 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–7. IEEE (2018)
Hu, Y., Liu, H., Huang, H.H.: TriCore: parallel triangle counting on GPUs. In: SC 2018: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 171–182. IEEE (2018)
Pandey, S., et al.: TRUST: triangle counting reloaded on GPUs. IEEE Trans. Parallel Distrib. Syst. 32(11), 2646–2660 (2021)
Polak, A.: Counting triangles in large graphs on GPU. In: 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 740–746. IEEE (2016)
Kolda, T.G., Pinar, A., Plantenga, T., Seshadhri, C., Task, C.: Counting triangles in massive graphs with MapReduce. SIAM J. Sci. Comput. 36(5), S48–S77 (2014)
Huang, J., Wang, H., Fei, X., Wang, X., Chen, W.: TC-Stream: large-scale graph triangle counting on a single machine using GPUs. IEEE Trans. Parallel Distrib. Syst. 33(11), 3067–3078 (2022)
Hu, L., Zou, L., Liu, Y.: Accelerating triangle counting on GPU. In: Li, G., Li, Z., Idreos, S., Srivastava, D. (eds.) SIGMOD 2021: International Conference on Management of Data, Virtual Event, China, 20–25 June 2021, pp. 736–748. ACM (2021)
Acknowledgments
The authors are very grateful to the anonymous reviewers for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Lin, L., Ouyang, D., He, Z., Li, C. (2023). Parallelize Accelerated Triangle Counting Using Bit-Wise on GPU. In: Yuan, L., Yang, S., Li, R., Kanoulas, E., Zhao, X. (eds) Web Information Systems and Applications. WISA 2023. Lecture Notes in Computer Science, vol 14094. Springer, Singapore. https://doi.org/10.1007/978-981-99-6222-8_46
Download citation
DOI: https://doi.org/10.1007/978-981-99-6222-8_46
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-99-6221-1
Online ISBN: 978-981-99-6222-8
eBook Packages: Computer ScienceComputer Science (R0)