Deakin University
Browse

File(s) under permanent embargo

Optimizing subgraph matching over distributed knowledge graphs using partial evaluation

journal contribution
posted on 2022-09-29, 06:54 authored by Y Song, Y Qin, W Hao, P Liu, Jianxin LiJianxin Li, F M 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.

History

Journal

World Wide Web

Publisher

Springer Science and Business Media LLC

ISSN

1386-145X

eISSN

1573-1413

Language

en

Publication classification

C1 Refereed article in a scholarly journal