Towards a Distributed Large-Scale Dynamic Graph Data Store
Towards a Distributed Large-Scale Dynamic Graph Data Store
复制标题
DOI：
10.1109/ipdpsw.2016.189
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Keita Iwabuchi;Scott Sallinen;R. Pearce;B. V. Essen;M. Gokhale;S. Matsuoka
中科院分区：
文献类型：
--
作者：
Keita Iwabuchi;Scott Sallinen;R. Pearce;B. V. Essen;M. Gokhale;S. Matsuoka
在许多图形应用中，图形的结构随时间动态地改变，并且可能需要真实的时间分析。然而，构建一个大型图是昂贵的，大多数大型图的研究并没有集中在动态图的数据结构，而是一个静态的。为了解决这个问题，我们提出了DegAwareRHH，一个高性能的动态图形数据存储，旨在通过利用具有高数据局部性的紧凑哈希表来扩展存储大型无标度图形。我们扩展DegAwareRHH多个进程和分布式内存，并使用新兴的“大数据HPC”系统（如LLNL的Catalyst集群）在大型无标度图上执行动态图构建。我们证明了DegAwareRHH处理请求流的速度比最先进的共享内存动态图处理框架快206.5倍，当这两种实现都使用24个线程/进程来构建具有10亿个边缘插入请求和5400万个边缘删除请求的图时。DegAwareRHH还实现了每秒超过20亿条边插入请求的处理速率，使用128个计算节点来构建包含1280亿条边的大规模Web图，这是我们所知的最大的开源真实的图形数据集。
In many graph applications, the structure of the graph changes dynamically over time and may require real time analysis. However, constructing a large graph is expensive, and most studies for large graphs have not focused on a dynamic graph data structure, but rather a static one. To address this issue, we propose DegAwareRHH, a high performance dynamic graph data store designed for scaling out to store large, scale-free graphs by leveraging compact hash tables with high data locality. We extend DegAwareRHH for multiple processes and distributed memory, and perform dynamic graph construction on large scale-free graphs using emerging 'Big Data HPC' systems such as the Catalyst cluster at LLNL. We demonstrate that DegAwareRHH processes a request stream 206.5x faster than a state-of-the-art shared-memory dynamic graph processing framework, when both implementations use 24 threads/processes to construct a graph with 1 billion edge insertion requests and 54 million edge deletion requests. DegAwareRHH also achieves a processing rate of over 2 billion edge insertion requests per second using 128 compute nodes to construct a large-scale web graph, containing 128 billion edges, the largest open-source real graph dataset to our knowledge.