Workload-Aware Subgraph Query Caching and Processing in Large Graphs
Workload-Aware Subgraph Query Caching and Processing in Large Graphs
复制标题
DOI：
10.1109/icde.2019.00190
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Yongjiang Liang;Peixiang Zhao
中科院分区：
文献类型：
--
作者：
Yongjiang Liang;Peixiang Zhao
子图查询q从数据图g中找到其所有子图同构嵌入作为输出，已经成为大型图中的现代声明式查询的核心。在本文中，我们利用查询工作负载信息的可用性来解决子图查询，W = {w1，...，wn}，其中W中的wi是先前发出的查询，其所有子图同构嵌入预先缓存。我们引入了一个工作负载感知的子图查询框架，WaSQ，利用查询工作负载子图查询重写，搜索计划细化，部分结果重用，和假阳性过滤，以促进整个子图查询过程。在现实世界的图中的实验研究表明，WaSQ实现了显着的和一致的性能增益相比，最先进的，工作负载无关的解决方案，大规模的子图查询。
A subgraph query q that finds as output all its subgraph-isomorphic embeddings from a data graph g has been core to modern declarative querying in large graphs. In this paper, we address subgraph queries with the availability of query workload information, W = {w1,..., wn}, where wi in W is a previously issued query with all its subgraph-isomorphic embeddings cached beforehand. We introduce a workload-aware subgraph querying framework, WaSQ, that leverages query workload for subgraph query rewriting, search plan refinement, partial results reusing, and false positive filtering towards facilitating the whole subgraph querying process. Experimental studies in real-world graphs demonstrate that WaSQ achieves significant and consistent performance gains in comparison with state-of-the-art, workload-oblivious solutions for large-scale subgraph querying.