A Dependency-Extended Method of Multi-pattern Matching . . .
187
Fig. 4. Execution time evaluation
time cost of BL algorithm is much faster than M-PM algorithm. In the linear
tread, M-PM algorithm can improve up to 70% of time efficiency compared with
BL algorithm. And execution time of M-PM and BL algorithms is roughly the
same without differences in depth and width. That is, the execution time of
M-PM and BL algorithms is only related to number of RE.
Therefore, execution time about depth of changed query node is described in
Fig. 4c. The total number of REs is same, and the number of REs with different
depths is changed. The deeper depth is, the less number of overlapped subgraph
is. In the linear trend, M-PM algorithm changes very litter and BL algorithm
keeps growing as the depth increases. That is, M-PM algorithm does not change
due to the times of overlapped subgraph increases.
Acknowledgements. This work is supported by the National Natural Science Foundation of China under Grant (No. 61371090, No. 61602076 and No.
61702072). The China Postdoctoral Science Foundation Funded Project (2017M621122
and 2017M611211). The Natural Science Foundation of Liaoning Province(No.
20170540144, No. 20170540232 and No. 20180540003).
References
1. Abadi DJ, Marcus A, Madden S, Hollenbach K (2009) Sw-store: a vertically partitioned DBMS for semantic web data management. VLDB J 18(2):385–406
187
Fig. 4. Execution time evaluation
time cost of BL algorithm is much faster than M-PM algorithm. In the linear
tread, M-PM algorithm can improve up to 70% of time efficiency compared with
BL algorithm. And execution time of M-PM and BL algorithms is roughly the
same without differences in depth and width. That is, the execution time of
M-PM and BL algorithms is only related to number of RE.
Therefore, execution time about depth of changed query node is described in
Fig. 4c. The total number of REs is same, and the number of REs with different
depths is changed. The deeper depth is, the less number of overlapped subgraph
is. In the linear trend, M-PM algorithm changes very litter and BL algorithm
keeps growing as the depth increases. That is, M-PM algorithm does not change
due to the times of overlapped subgraph increases.
Acknowledgements. This work is supported by the National Natural Science Foundation of China under Grant (No. 61371090, No. 61602076 and No.
61702072). The China Postdoctoral Science Foundation Funded Project (2017M621122
and 2017M611211). The Natural Science Foundation of Liaoning Province(No.
20170540144, No. 20170540232 and No. 20180540003).
References
1. Abadi DJ, Marcus A, Madden S, Hollenbach K (2009) Sw-store: a vertically partitioned DBMS for semantic web data management. VLDB J 18(2):385–406