PROJECT TITLE :

Subgraph Matching with Effective Matching Order and Indexing

ABSTRACT:

When a query graph is compared to a data graph, the subgraph matching operation locates all embeddings in the data graph that are identical to the query graph. Modern algorithms accomplish their work by first generating a tree-structured index on the data graph based on the query graph, then ordering the vertices path-by-path within the tree, and finally enumerating the embeddings in the order in which they are found in the query graph. The performance of such path-based ordering and tree-structured index-based enumeration is inherently limited, according to our findings, because there is no consideration given to the edges that connect the vertices of tree paths. We propose an approach that generates the matching order based on a cost model that takes into consideration both the edges among the query vertices and the number of candidates. This will allow us to address the issue at hand. In addition, we perform enumeration according to the matching order by using a bigraph index that we create for candidate vertices and their selected neighbors in the data graph. This index is used to create the bigraph index. Our research using real-world and fabricated datasets demonstrates that the performance of our approach is orders of magnitude higher than that of the current gold standard.