Frequent Itemset-based Graph Numbering using Execution Traces for Cache Misses Reduction in Graph Analysis Tasks

Full abstract

Read the full abstract

Graph analysis applications are increasingly used on large-scale datasets, where memory access patterns have a significant impact on performance. In such applications, poor data locality leads to a high number of cache misses, which in turn degrades execution time. To address this issue, several graph numbering techniques have been proposed to reorganize data in memory, mainly based on structural properties of the graph. More recently, execution trace-based approaches such as NumBaClus have been introduced, leveraging clustering techniques to group nodes with similar access patterns. However, these methods do not explicitly capture the co-occurrence of nodes within the same execution contexts. In this paper, we propose NumBaFrIt, a new graph numbering approach based on frequent itemset mining of execution traces. By modeling execution traces as transactional data, our method identifies groups of nodes that are frequently accessed together and reorganizes them in memory to improve data locality. Experimental results show that NumBaFrIt improves base numbering and significantly enhances existing ordering strategies when used as a preprocessing step, leading to better cache efficiency and reduced execution time. This is for example the case on user machine with 3072 KB of cache memory, our proposal got the best cache misses reduction through the combination NumBaFrit-sup70_cn-order with 48.96% compared to 17.15% of cache misses reduction gotten with Cn-order_cl-h (an existing numbering of NumBaClus).