BEAD: Batched Evaluation of Iterative Graph Queries with Evolving Analytics Demands
BEAD: Batched Evaluation of Iterative Graph Queries with Evolving Analytics Demands
复制标题
DOI：
10.1109/bigdata50022.2020.9378211
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Abbas Mazloumi;Chengshuo Xu;Zhijia Zhao;Rajiv Gupta
中科院分区：
文献类型：
--
作者：
Abbas Mazloumi;Chengshuo Xu;Zhijia Zhao;Rajiv Gupta
同时评估分布式系统上的一批迭代图查询可以使多个查询的高通信和计算成本摊销。批次大小数百个查询。在本文中，我们通过开发珠子大大扩展了适用的方案，该方案是在不断发展的分析需求的情况下支持批处理的系统。随着图形数据集的演变，添加了时间，更多的顶点（例如，用户）和边缘（例如，交互）。珠子提供的超级效率的关键在于一系列增量评估技术，该技术利用了先验请求的结果来“快速”对当前请求的评估。我们进行了比较Multyra中珠子中的珠子中的批处理的实验多个输入图和算法。分别为26.16×和5.66倍。
Simultaneous evaluating a batch of iterative graph queries on a distributed system enables amortization of high communication and computation costs across multiple queries. As demonstrated by our prior work on MultiLyra [BigData’19], batched graph query processing can deliver significant speedups and scale up to batch sizes of hundreds of queries.In this paper, we greatly expand the applicable scenarios for batching by developing BEAD, a system that supports Batching in the presence of Evolving Analytics Demands. First, BEAD allows the graph data set to evolve (grow) over time, more vertices (e.g., users) and edges (e.g., interactions) are added. In addition, as the graph data set evolves, BEAD also allows the user to add more queries of interests to the query batch to accommodate new user demands. The key to the superior efficiency offered by BEAD lies in a series of incremental evaluation techniques that leverage the results of prior request to "fast-foward" the evaluation of the current request.We performed experiments comparing batching in BEAD with batching in MultiLyra for multiple input graphs and algorithms. Experiments demonstrate that BEAD’s batched evaluation of 256 queries, following graph changes that add up to 100K edges to a billion edge Twitter graph and also query changes of up to 32 new queries, outperforms MultiLyra’s batched evaluation by factors of up to 26.16 × and 5.66 × respectively.