BB-PLUS: an efficient approach for subgraph isomorphism problem in big graph databases

Thesis Type: Postgraduate

Institution Of The Thesis: Middle East Technical University, Faculty of Engineering, Department of Computer Engineering, Turkey

Approval Date: 2019

Student: Ezgi Taşkomaz

Consultant: ADNAN YAZICI


Graph databases are flexible NoSQL databases used to efficiently store and query complex dataset. The problem of subgraph isomorphism, finding a pattern in a given graph, is one of the biggest problem of graph databases. Therefore, the goal of this study is to introduce a new approach called BB-Plus, which consists of heuristics to find best matching order using the volatility and size of the database, the type and size of the query as an input in order to improve the performance of the queries. BBPlus approach trims candidate nodes at high level and effectively reduces the size of the problem. The approach is implemented using the Java programming language and graph data structures of Neo4j GDBMS and compared to the state-of-the-art subgraph isomorphism algorithms, namely BB-Graph, Cypher, DualIso, GraphQL, TurboIso and VF3 with three different dataset within the same programming environment. The results of the performance tests show that BB-Plus is an average on 10%, 37% and 4% faster than the other algorithms based on different queries in public WorldCup, Pokec and non-public Population dataset, respectively.