RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine
RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine
复制标题
DOI：
--
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Kai Wang;Zhiqiang Zuo;John Thorpe;Tien Quang Nguyen;G. Xu
中科院分区：
文献类型：
--
作者：
Kai Wang;Zhiqiang Zuo;John Thorpe;Tien Quang Nguyen;G. Xu
图挖掘是图形算法的重要类别，旨在在图中发现诸如集团和图案之类的结构模式。现有的采矿系统（例如阿拉伯式）重点是分布式计算，我们需要大量的计算和内存资源。两项创新：（1）一个丰富的编程模型，使开发人员表达各种各样的采矿任务； - ART分布式采矿/数据系统系统 - Arabesque，Scalemine，Distgraph和BigDatalog-证明Rstream在10节点群集上运行的RSTREAM均优于所有这些，例如，例如，至少以1.7倍的倍数，并且可以使用。在廉价的机器上处理大图。
Graph mining is an important category of graph algorithms that aim to discover structural patterns such as cliques and motifs in a graph. While a great deal of work has been done recently on graph computation such as PageRank, systems support for scalable graph mining is still limited. Existing mining systems such as Arabesque focus on distributed computing and need large amounts of compute and memory resources. We built RStream, the first single-machine, out-of-core mining system that leverages disk support to store intermediate data. At its core are two innovations: (1) a rich programming model that exposes relational algebra for developers to express a wide variety of mining tasks; and (2) a runtime engine that implements relational algebra efficiently with tuple streaming. A comparison between RStream and four state-of-the-art distributed mining/Datalog systems--Arabesque, ScaleMine, DistGraph, and BigDatalog -- demonstrates that RStream outperforms all of them, running on a 10-node cluster, e.g., by at least a factor of 1.7×, and can process large graphs on an inexpensive machine.