ASAP: Fast, Approximate Graph Pattern Mining at Scale
ASAP: Fast, Approximate Graph Pattern Mining at Scale
复制标题
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
A. Iyer;Zaoxing Liu;Xin Jin;S. Venkataraman;V. Braverman;I. Stoica
中科院分区：
文献类型：
--
作者：
A. Iyer;Zaoxing Liu;Xin Jin;S. Venkataraman;V. Braverman;I. Stoica
虽然人们对处理具有底层图结构的数据有着极大的兴趣，但现有的分布式图处理系统需要几分钟甚至几小时来挖掘图上的简单模式。本文介绍了一个用于图模式挖掘的快速近似计算引擎ASAP。ASAP利用图近似理论中最先进的结果，并将其扩展到分布式设置中的一般图形模式。为了使用户能够在结果准确性和延迟之间进行权衡，我们提出了一种新的方法来为给定的计算构建错误延迟配置文件（ELP）。我们已经在一个通用的分布式并行平台上实现了ASAP，并在几个图形模式上对其进行了广泛的评估。我们的实验结果表明，ASAP优于现有的精确模式挖掘解决方案高达77倍。此外，ASAP可以扩展到具有数十亿条边的图形，而无需大型集群。
While there has been a tremendous interest in processing data that has an underlying graph structure, existing distributed graph processing systems take several minutes or even hours to mine simple patterns on graphs. This paper presents ASAP, a fast, approximate computation engine for graph pattern mining. ASAP leverages state-of-the-art results in graph approximation theory, and extends it to general graph patterns in distributed settings. To enable the users to navigate the tradeoff between the result accuracy and latency, we propose a novel approach to build the Error-Latency Profile (ELP) for a given computation. We have implementedASAP on a general-purpose distributed dataflow platform and evaluated it extensively on several graph patterns. Our experimental results show that ASAP outperforms existing exact pattern mining solutions by up to 77×. Further, ASAP can scale to graphs with billions of edges without the need for large clusters.