Evaluating Hash Tables for Complex Graph Algorithms: A Parallel Dynamic Community Detection Case Study

• Gabriel G. dos Santos PUCRS
• César A. F. De Rose PUCRS
• Kaio M. Vieira UFMG
• Vinicius dos Santos UFMG

DOI: https://doi.org/10.5753/sscad.2026.34993

Resumo

Community Detection is a widely studied problem in the context of static and dynamic graphs due to its wide range of applications. Although parallel algorithms have been investigated for such problems, the choice of the underlying structures used by implementations receives little spotlight. Dynamic community detection requires repeated insertion, deletion, and access of multiple structures as the graph evolves, making the containers a first-order performance concern. This paper evaluates two hash table implementations as containers for vertices, communities, and edges inside DynaMap, a parallel dynamic community detection algorithm. Through experiments on four real-world graphs, we demonstrate that no single hash table configuration is best for every structure.

Referências

Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P10008.

Dhulipala, L., Blelloch, G. E., and Shun, J. (2019). Low-latency graph streaming using compressed purely-functional trees. In Proceedings of the 40th ACM SIGPLAN conference on programming language design and implementation, pages 918–934.

Ediger, D., McColl, R., Riedy, J., and Bader, D. A. (2012). Stinger: High performance data structure for streaming graphs. In 2012 IEEE Conference on High Performance Extreme Computing, pages 1–5. IEEE.

Fan, Z., Cai, Y., Liu, Z., Guo, J., Fan, X., Yang, T., and Cui, B. (2025). Cuckoograph: A scalable and space-time efficient data structure for large-scale dynamic graphs. In 2025 IEEE 41st International Conference on Data Engineering (ICDE), pages 1265–1277. IEEE.

Feng, G., Meng, X., and Ammar, K. (2015). Distinger: A distributed graph data structure for massive dynamic graph processing. In 2015 IEEE International Conference on Big Data (Big Data), pages 1814–1822. IEEE.

Firmli, S. and Chiadmi, D. (2023). A scalable data structure for efficient graph analytics and in-place mutations. Data, 8(11):166.

GNU Project (2024). Policy-based data structures: Design. [link].

Green, O. and Bader, D. A. (2016). custinger: Supporting dynamic graph algorithms for gpus. In 2016 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–6. IEEE.

Iwabuchi, K., Sallinen, S., Pearce, R., Van Essen, B., Gokhale, M., and Matsuoka, S. (2016). Towards a distributed large-scale dynamic graph data store. In 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 892–901. IEEE.

Jaiyeoba, W. and Skadron, K. (2019). Graphtinker: A high performance data structure for dynamic graph processing. In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 1030–1041. IEEE.

Kilic, O. O., Tallent, N. R., and Friese, R. D. (2020). Rapid memory footprint access diagnostics. In 2020 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 273–284. IEEE.

Leskovec, J. and Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. [link].

Myers, S. A. and Leskovec, J. (2014). The bursty dynamics of the twitter information network. In Proceedings of the 23rd international conference on World wide web, pages 913–924.

Pandey, P., Wheatman, B., Xu, H., and Buluç, A. (2021). Terrace: A hierarchical graph container for skewed dynamic graphs. In Proceedings of the 2021 International Conference on Management of Data (SIGMOD), pages 1372–1385. ACM.

Rosvall, M., Axelsson, D., and Bergstrom, C. T. (2009). The map equation. The European Physical Journal Special Topics, 178(1):13–23.

Santos, G. G., Lakhotia, K., and De Rose, C. A. (2025). Dynamap: A map equation-based parallel algorithm for detecting communities on dynamic graphs. In 2025 IEEE/SBC 37th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), pages 125–135. IEEE.

van der Grinten, A., Predari, M., and Willich, F. (2022). A fast data structure for dynamic graphs based on hash-indexed adjacency blocks. In Proceedings of the 20th International Symposium on Experimental Algorithms (SEA 2022), volume 233 of LIPIcs.

Wheatman, B., Dong, X., Shen, Z., Dhulipala, L., Łacki, J., Pandey, P., and Xu, H. (2024). BYO: A unified framework for benchmarking large-scale graph containers. Proceedings of the VLDB Endowment, 17:2307–2320.

Zhang, F., Zou, L., Zeng, L., and Gou, X. (2020). Dolha-an efficient and exact data structure for streaming graphs. World Wide Web, 23(2):873–903.