A subgraph query algorithm based on two-step mapping on vertex to decision feature

To solve the problem of subgraph query processing in large graph databases, the paper gives a two-step node to decision feature mapping (NDFM) indexed structure, named the NDFM-Index, and based on it, proposes a subgraph query processing algorithm. The NDFM-Index uses the mapping between key nodes, with the distribution of neighbors labels, and decision features to get the indexed features which are included by query graph avoiding enumeration method. The results of theoretical analysis and experimental evaluation show that the proposed method not only avoids the enumeration method of getting subgraphs of query graph, but also effectively reduces the subgraph isomorphism tests between the query graph and graphs in candidate answer set in verification stage.