GraphBlast: multi-feature graphs database searching

Graphs model web relationships, biomedical and chemical data. In all these domains, a key role is played by systems that search for all exact or approximate occurrences of a query graph. To deal efficiently with graph searching advanced methods for indexing, representation and matching of graphs are needed. Several systems have been pro- posed. However, none of them has been recognized to be the best for all classes of graphs. This paper presents GraphBlast. The system implements efficient graph searching algorithms together with advanced filtering techniques. It allows to select candidate subgraphs rather than entire graphs. It implements an effective data storage based also on low-support data mining. A distributed version of the proposed systems is sketched. GraphBlast is compared with Frowns, Graph- Grep and gIndex. Experiments show that GraphBlast outperforms all the compared systems both on real and synthetic databases. The proposed low-support mining technique which applies to any searching system also allows a significantly indexing space reduction.