Accelerating Graph Mining Systems with Subgraph Morphing
Accelerating Graph Mining Systems with Subgraph Morphing
复制标题
DOI：
10.1145/3552326.3567489
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Kasra Jamshidi;Harry Xu;Keval Vora
中科院分区：
文献类型：
--
作者：
Kasra Jamshidi;Harry Xu;Keval Vora
图挖掘应用分析了大图的结构特性。从完全不同的模式的结果中，给定的一组模式的结果，这些模式的价格较低计算。在实践中启用子图形，我们开发了有效的查询转换技术，以及用于不同应用程序的自动结果转换策略。 Automine/ - GraphZero，GraphPi和BigJoin彻底评估表明，子图表可以改善这四个系统的性能分别为34×，10×，18倍和13倍。
Graph mining applications analyze the structural properties of large graphs. These applications are computationally expensive because finding structural patterns requires checking subgraph isomorphism, which is NP-complete. This paper exploits the sub-structural similarities across different patterns by employing Subgraph Morphing to accurately infer the results for a given set of patterns from the results of a completely different set of patterns that are less expensive to compute. To enable Subgraph Morphing in practice, we develop efficient query transformation techniques as well as automatic result conversion strategies for different application scenarios. We have implemented Subgraph Morphing in four state-of-the-art graph mining and subgraph matching systems: Peregrine, AutoMine/- GraphZero, GraphPi, and BigJoin; a thorough evaluation demonstrates that Subgraph Morphing improves the performance of these four systems by 34×, 10×, 18×, and 13×, respectively.