Title

BB-GRAPH: A NEW SUBGRAPH ISOMORPHISM ALGORITHM FOR QUERYING BIG GRAPH DATABASES

Abstract

Abstract

With emergence of the big data concept, the big graph database model has become very popular since it provides very flexible and quick querying for the cases that require costly join operations in RDBMs. However, it is a big challenge to find all exact matches of a query graph in a big database graph, which is known as the subgraph isomorphism problem. Although many studies in this topic already exist in literature, there is not a perfect algorithm that works for all types of queries efficiently since it is an NP-hard problem. The current subgraph isomorphism approaches built on Ullmann’s idea focus on the strategy of pruning out the irrelevant candidates. Nevertheless, for some databases and queries, the pruning techniques that those algorithms use are inadequate to eliminate false cases earlier. Therefore, they result in poor performance, especially for some complex queries. Moreover, some of those algorithms need large data structures that cause extra time and large memory consumption. Motivated by these, we introduce a new subgraph isomorphism algorithm, namely BB-Graph, for querying big database graphs in an efficient manner without requiring a large memory. We test and compare our algorithm with the existing ones, GraphQL and Cypher of Neo4j, on some very big graph database applications and show that our algorithm performs better than them for most of the query types.

Biography:

Supervisor(s)

Supervisor(s)

MERVE ASILER

Date and Location

Date and Location

2016-09-20;09:30:00-A101

Category

Category

MSc_Thesis