Optimizing subgraph matching over distributed knowledge graphs using partial evaluation
Version 2 2024-06-02, 14:34Version 2 2024-06-02, 14:34
Version 1 2022-09-29, 06:54Version 1 2022-09-29, 06:54
journal contribution
posted on 2024-06-02, 14:34authored byY Song, Y Qin, W Hao, P Liu, Jianxin Li, FM Choudhury, X Wang, Q Zhang
AbstractThe partial evaluation and assembly framework has recently been applied for processing subgraph matching queries over large-scale knowledge graphs in the distributed environment. The framework is implemented on the master-slave architecture, endowed with outstanding scalability. However, there are two drawbacks of partial evaluation: if the volume of intermediate results is large, a large number of repeated partial matches will be generated; and the assembly computation handled by the master would be a bottleneck. In this paper, we propose an optimal partial evaluation algorithm and a filter method to reduce partial matches by exploring the computing characteristics of partial evaluation and assembly framework. (1) An index structure named inner boundary node index (IBN-Index) is constructed to prune for graph exploration to improve the searching efficiency of the partial evaluation phase. (2) The boundary characteristics of local partial matches are utilized to construct a boundary node index (BN-Index) to reduce the number of local partial matches. (3) The experimental results over benchmark datasets show that our approach outperforms the state-of-the-art methods.