Graph Edit Similarity Query Based on Partitioned Filtering-Incremental Verification
The Graph Edit Similarity Query problem refers to querying all data graphs from the graph set G that have Graph Edit Distance(GED)within a given threshold τ from the query graph q.Since GED computation is an NP-Hard problem,most existing studies use a filtering-verification framework for querying,and the A*-GED algorithm is used to verify the graphs that fail to be filtered out.In this paper,we propose the Partitioned Filtering-Incremental Verification(PFIV)framework to deal with the graph similarity query problem,which enhances the filtering effect and speeds up the verification speed.First,two partitioning strategies are proposed in the filtering stage to speed up the partitioning.(1)Mapping vertex order strategy:during the partitioning process,the mapping order of vertices during partitioning is proposed based on the feature information and structure information of the graph to filter out dissimilar graphs as soon as possible and reduce the computation;(2)Partitioning end condition strategy:during the partitioning process,the partitioning end condition is set to speed up the filtering of dissimilar graphs.Secondly,an incremental verification strategy is proposed in the validation stage,using the mapping results retained in the filtering stage to design the state space tree for incremental verification and speed up the computation in the validation stage.Finally,it is verified through a large number of experiments that PFIV can efficiently handle the graph edit similar query problem,and the query efficiency is improved by 8%～17%compared with the original algorithm,and the effectiveness of the proposed strategy is demonstrated.
graph similarGEDpartitioned filteringincremental verificationgraph data
万方数据
维普
