Title: BB-Graph: A Subgraph Isomorphism Algorithm for Efficiently Querying Big Graph Databases,
Abstract: The big graph database model provides strong modeling for complex
applications and efficient querying. However, it is still a big challenge to
find all exact matches of a query graph in a big graph database, which is known
as the subgraph isomorphism problem. The current subgraph isomorphism
approaches are built on Ullmann's idea of focusing on the strategy of pruning
out the irrelevant candidates. Nevertheless, the existing pruning techniques
need much more improvement to efficiently handle complex queries. Moreover,
many of those existing algorithms need large indices requiring extra memory
consumption. Motivated by these, we introduce a new subgraph isomorphism
algorithm, named as BB-Graph, for querying big graph databases efficiently
without requiring a large data structure to be stored in main memory. We test
and compare our proposed BB-Graph algorithm with two popular existing
approaches, GraphQL and Cypher. Our experiments are done on three different
data sets; (1) a very big graph database of a real-life population database,
(2) a graph database of a simulated bank database, and (3) the publicly
available World Cup big graph database. We show that our solution performs
better than those algorithms mentioned here for most of the query types
experimented on these big databases.