Raffaele Di Natale
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Raffaele Di Natale has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Alfredo Ferro
Department of Clinical and Experimental Medicine, Bioinformatics Unit, University of Catania, Catania, Italy
1 shared publication - Alfredo Pulvirenti
University of Catania
1 shared publication - Dennis Shasha
Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA
1 shared publication - Misael Mongiovì
Institute of Cognitive Sciences and Technologies, National Research Council (CNR-ISTC)
1 shared publication - Rosalba Giugno
Department of Computer Science, University of Verona, Verona, Italy
1 shared publication
Latest Publications
- Open Access
- 19 February 2010
- Published by Springer Nature in BMC Bioinformatics
- Vol. 11 (1) , 96
SING: Subgraph search In Non-homogeneous Graphs
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, which can be a small subgraph, subtree or path. Each graph in the database is annotated with the set of all its features. The key point is to make use of feature locality information. This idea is used to both improve the filtering performance and speed up the subgraph isomorphism task. Conclusions: Extensive tests on chemical compounds, biological networks and synthetic graphs show that the proposed system outperforms the most popular systems in query time over databases of medium and large graphs. Other specific tests show that the proposed system is effective for single large graphs.
- 19 February 2010
- Published by Springer Nature in BMC Bioinformatics
- Vol. 11 (1) , 96
Open AccessSING: Subgraph search In Non-homogeneous Graphs
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, which can be a small subgraph, subtree or path. Each graph in the database is annotated with the set of all its features. The key point is to make use of feature locality information. This idea is used to both improve the filtering performance and speed up the subgraph isomorphism task. Conclusions: Extensive tests on chemical compounds, biological networks and synthetic graphs show that the proposed system outperforms the most popular systems in query time over databases of medium and large graphs. Other specific tests show that the proposed system is effective for single large graphs.