Dynamic Graph Pattern Matching in Medical Knowledge Graphs
Xun Du, Zhenchao Tao, Lei Li · 2022
As the study of graph pattern matching (GPM) attracts more and more scholars, the research of GPM in the medical field begins to emerge, from protein structure analysis to breast cancer classification diagnosis, and GPM is more and more widely adopted. However, in medical knowledge graphs (MKG), when the pattern graph dynamically changes, to obtain the matching results of the changed pattern graph, the traditional method has to carry out global matching instead of local matching, which causes a waste of resources and takes a lot of time. To quickly return the matching results of the dynamic pattern graph in MKGs, in this paper, we introduce a caching mechanism to cache the previous matching results and propose a new longest common path matching (M-LCPM) algorithm based on multithreading. The algorithm only performs partial matching on the changed pattern graph and can quickly obtain the matching result. Considering that the M-LCPM algorithm cannot get matching results when the pattern graph changes completely and there may be missing matching subgraphs when the M-LCPM algorithm performs matching, we optimize the M-LCPM algorithm and propose the M-LCPM-Enhance algorithm. Experimental results on two data sets show that our dynamic algorithm is more efficient than existing algorithms.