This thesis examines the performance of triangle counting algorithms in memory hierarchy systems when dealing with random graphs. The objective is to assess the effectiveness of cache-optimized algorithms in processing large-scale graph data compared to traditional algorithms designed for RAM. The thesis initially presents and investigates the MinBucket algorithm both theoretically and experimentally, contrasting its performance with that of the trivial algorithm in power-law random graphs generated using the Erased Configuration Model. The experiments measure both execution time and the number of I/O operations on the CPU cache memory. Subsequently, experimental comparisons are made between the MinBucket algorithm and a randomized cache-aware algorithm, utilizing power-law random ECM graphs, uniformly distributed random graphs, and real-world graphs, adjusting hyperparameters and comparing execution times and cache misses. The experimental results demonstrate the superior performance of cache-aware algorithms over MinBucket when applied to power-law distributed graphs. This highlights the potential of memory hierarchy-optimized algorithms to significantly enhance computation speed compared to traditional algorithms for this category of graphs, suggesting a promising direction for future algorithm development.

An experimental evaluation of triangle counting algorithms with random graphs in hierarchical memory architectures

PERON, CLAUDIO
2023/2024

Abstract

This thesis examines the performance of triangle counting algorithms in memory hierarchy systems when dealing with random graphs. The objective is to assess the effectiveness of cache-optimized algorithms in processing large-scale graph data compared to traditional algorithms designed for RAM. The thesis initially presents and investigates the MinBucket algorithm both theoretically and experimentally, contrasting its performance with that of the trivial algorithm in power-law random graphs generated using the Erased Configuration Model. The experiments measure both execution time and the number of I/O operations on the CPU cache memory. Subsequently, experimental comparisons are made between the MinBucket algorithm and a randomized cache-aware algorithm, utilizing power-law random ECM graphs, uniformly distributed random graphs, and real-world graphs, adjusting hyperparameters and comparing execution times and cache misses. The experimental results demonstrate the superior performance of cache-aware algorithms over MinBucket when applied to power-law distributed graphs. This highlights the potential of memory hierarchy-optimized algorithms to significantly enhance computation speed compared to traditional algorithms for this category of graphs, suggesting a promising direction for future algorithm development.
2023
An experimental evaluation of triangle counting algorithms with random graphs in hierarchical memory architectures
triangle counting
memory hierarchy
random graphs
File in questo prodotto:
File Dimensione Formato  
Claudio Peron - Thesis.pdf

accesso aperto

Dimensione 609.86 kB
Formato Adobe PDF
609.86 kB Adobe PDF Visualizza/Apri

The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12608/65948