An FPGA-based Accelerator for Regular Path Queries over Edge-labeled Graphs
An FPGA-based Accelerator for Regular Path Queries over Edge-labeled Graphs
复制标题
DOI：
10.1109/bigdata55660.2022.10020406
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
K. Miura;Ryohei Kobayashi;Toshiyuki Amagasa;H. Kitagawa;N. Fujita;T. Boku
中科院分区：
文献类型：
--
作者：
K. Miura;Ryohei Kobayashi;Toshiyuki Amagasa;H. Kitagawa;N. Fujita;T. Boku
边标记有向图通常用于表示不同应用中的各种信息，例如社交网络、知识图等，正则路径查询（RPQ）允许我们通过与表示为正则表达式的查询模式匹配的标记路径来提取从一个节点到另一个节点可达的节点对。从图中提取复杂的或语义上有意义的信息对我们来说是有用的，但当处理大型图时，它会带来挑战。这是由于中间结果的爆炸性增长导致的长执行时间，但另一方面，某些应用程序需要快速查询执行。为了解决这个问题，我们提出了一个基于FPGA的RPQ加速器。其思想是利用FPGA的并行性，以流水线方式并行遍历目标图和匹配正则路径表达式。为了验证所提出的方法的性能，我们进行了一组实验。从结果中，我们观察到，所提出的方法实现了更短的运行时间的RPQ对社会图提取的真实的世界，高达三个数量级相比，基线方法。
Edge-labeled directed graphs are commonly used to represent various information in different applications, such as social networks, knowledge graphs, etc., and regular path queries (RPQs) allow us to extract pairs of nodes that are reachable from one to another through a labeled path matching with the query pattern represented as a regular expression. It is useful for us to extract complicated or semantically meaningful information from a graph, but it gives rise to a challenge when dealing with large graphs. This is due to the long execution time caused by the explosive growth of intermediate results, but, on the other hand, some applications require fast query executions. To address this problem, we propose an FPGA-based RPQ accelerator. The idea is to exploit FPGA’s parallelism in traversing the target graph and matching the regular path expression in parallel with the pipeline manner. To validate the performance of the proposed method, we conducted a set of experiments. From the results, we observed that the proposed method achieves shorter elapsed times for RPQs against social graphs extracted from the real world, up to three orders of magnitude compared with baseline methods.