HBMax: Optimizing Memory Efficiency for Parallel Influence Maximization on Multicore Architectures
HBMax: Optimizing Memory Efficiency for Parallel Influence Maximization on Multicore Architectures
复制标题
DOI：
10.1145/3559009.3569647
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Xinyu Chen;Marco Minutoli;Jiannan Tian;M. Halappanavar;A. Kalyanaraman;Dingwen Tao
中科院分区：
文献类型：
--
作者：
Xinyu Chen;Marco Minutoli;Jiannan Tian;M. Halappanavar;A. Kalyanaraman;Dingwen Tao
影响力最大化的目标是在一个网络中选择k个最有影响力的顶点或种子，其中影响力是由给定的扩散过程定义的。虽然计算最优种子集是NP难的，但仍然存在有效的近似算法。然而，即使是最先进的并行实现也受到采样步骤的限制，该步骤会产生大量的内存占用。这反过来又限制了问题的大小、影响范围和近似质量。在这项工作中，我们研究了在大型现实社会网络上的IMM(通过鞅的影响最大化)算法中收集反向可达性信息的采样过程的内存占用。提出了一种基于Ripples的高效内存优化方法(HBMax)，这是一种最先进的多线程并行影响最大化解决方案。我们的方法HBMax使用算法收集的部分反向可达(RR)集来学习图的特征。然后，使用霍夫曼编码或位图编码对中间反向可达性信息进行压缩，并对部分解码的数据进行查询，或直接对压缩数据进行查询，以保留通过压缩获得的内存节约。考虑到NUMA架构，我们在CPU核上扩展了我们的解决方案，在不损失精度的情况下将内存占用减少了82.1%，平均加速比为6.3%(编码开销被内存减少带来的性能提升所抵消)。对于最大的测试图Twitter7(有14亿条边)，HBMax可以达到5.9倍的压缩比和2.2倍的加速比。
Influence maximization aims to select k most-influential vertices or seeds in a network, where influence is defined by a given diffusion process. Although computing optimal seed set is NP-Hard, efficient approximation algorithms exist. However, even state-of-the-art parallel implementations are limited by a sampling step that incurs large memory footprints. This in turn limits the problem size reach and approximation quality. In this work, we study the memory footprint of the sampling process collecting reverse reachability information in the IMM (Influence Maximization via Martingales) algorithm over large real-world social networks. We present a memory-efficient optimization approach (called HBMax) based on Ripples, a state-of-the-art multi-threaded parallel influence maximization solution. Our approach, HBMax, uses a portion of the reverse reachable (RR) sets collected by the algorithm to learn the characteristics of the graph. Then, it compresses the intermediate reverse reachability information with Huffman coding or bitmap coding, and queries on the partially decoded data, or directly on the compressed data to preserve the memory savings obtained through compression. Considering a NUMA architecture, we scale up our solution on 64 CPU cores and reduce the memory footprint by up to 82.1% with average 6.3% speedup (encoding overhead is offset by performance gain from memory reduction) without loss of accuracy. For the largest tested graph Twitter7 (with 1.4 billion edges), HBMax achieves 5.9× compression ratio and 2.2× speedup.