SING: subgraph search in non-homogeneous graphs.

ABSTRACT:

Background

Finding the subgraphs of a graph database that are isomorphic to a given query graph has practical applications in several fields, from cheminformatics to image understanding. Since subgraph isomorphism is a computationally hard problem, indexing techniques have been intensively exploited to speed up the process. Such systems filter out those graphs which cannot contain the query, and apply a subgraph isomorphism algorithm to each residual candidate graph. The applicability of such systems is limited to databases of small graphs, because their filtering power degrades on large graphs.

Results

In this paper, SING (Subgraph search In Non-homogeneous Graphs), a novel indexing system able to cope with large graphs, is presented. The method uses the notion of feature,

SUBMITTER: Di Natale R 

PROVIDER: S-EPMC2850364 | biostudies-literature | 2010 Feb

REPOSITORIES: biostudies-literature