期刊
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
卷 35, 期 6, 页码 6405-6420出版社
IEEE COMPUTER SOC
DOI: 10.1109/TKDE.2022.3175800
关键词
Query processing; Search problems; Indexes; Graph query; temporal graphs; subgraph isomorphism search
In this paper, a new problem of seeking stable subgraph isomorphisms for a query graph in a temporal graph is studied. A pruning-based search algorithm using new pruning tricks is developed to solve the problem. To improve efficiency, a novel index structure called BCCIndex is proposed, which is based on bi-connected component decomposition of the query graph. Extensive experiments on real-life datasets demonstrate the efficiency and effectiveness of the algorithms.
In this paper, we study a new problem of seeking stable subgraph isomorphisms for a query graph in a temporal graph. To solve our problem, we first develop a pruning-based search algorithm using several new pruning tricks to prune the unpromising matching results during the search procedure. To further improve the efficiency, we propose a novel index structure called BCCIndex, based on an idea of bi-connected component decomposition of the query graph, which can efficiently support the stable subgraph isomorphism search. Equipped with the BCCIndex, we present an efficient query processing algorithm based on a carefully designed tree join technique. We conduct extensive experiments to evaluate our algorithms on four large real-life datasets, and the results demonstrate the efficiency and effectiveness of our algorithms.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据