A subgraph matching algorithm based on subgraph index for knowledge graph

The problem of subgraph matching is one fundamental issue in graph search,which is NP-Complete problem.Recently,subgraph matching has become a popular research topic in the field of knowledge graph analysis,which has a wide range of applications including question answering and semantic search.In this paper,we study the problem of subgraph matching on knowledge graph.Specifically,given a query graph q and a data graph G,the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of q on G.Knowledge graph is formed as a directed labeled multi-graph having multiple edges between a pair of vertices and it has more dense semantic and structural features than general graph.To accelerate subgraph matching on knowledge graph,we propose a novel subgraph matching algorithm based on subgraph index for knowledge graph,called as FGqT-Match.The subgraph matching algorithm consists of two key designs.One design is a subgraph index of matching-driven flow graph(FGqT),which reduces redundant calculations in advance.Another design is a multi-label weight matrix,which evaluates a near-optimal matching tree for minimizing the intermediate candidates.With the aid of these two key designs,all subgraph isomorphic mappings are quickly conducted only by traversing FGqj.Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.

Matching suitable feature construction for SAR images based on evolutionary synthesis strategy

In the paper,a set of algorithms to construct synthetic aperture radar（SAR）matching suitable features are frstly proposed based on the evolutionary synthesis strategy.During the process,on the one hand,the indexes of primary matching suitable features（PMSFs）are designed based on the characteristics of image texture,SAR imaging and SAR matching algorithm,which is a process involving expertise;on the other hand,by designing a synthesized operation expression tree based on PMSFs,a much more flexible expression form of synthesized features is built,which greatly expands the construction space.Then,the genetic algorithm-based optimized searching process is employed to search the synthesized matching suitable feature（SMSF）with the highest effciency,largely improving the optimized searching effciency.In addition,the experimental results of the airborne synthetic aperture radar ortho-images of C-band and P-band show that the SMSFs gained via the algorithms can reflect the matching suitability of SAR images accurately and the matching probabilities of selected matching suitable areas of ortho-images could reach 99±0.5%.