BB-graph: a new subgraph isomorphism algorithm for querying big graph databases

Download
2016
Asiler, Merve
With the 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 related studies 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, their pruning techniques are inadequate. Therefore, they result in poor performance. Moreover, some of those algorithms need large indices that cause extra 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 large data structures. 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 for most of the query types.

Suggestions

Data integration over horizontally partitioned databases in service-oriented data grids
Sunercan, Hatice Kevser Sönmez; Çiçekli, Fehime Nihan; Alpdemir, Mahmut Nedim; Department of Computer Engineering (2010)
Information integration over distributed and heterogeneous resources has been challenging in many terms: coping with various kinds of heterogeneity including data model, platform, access interfaces; coping with various forms of data distribution and maintenance policies, scalability, performance, security and trust, reliability and resilience, legal issues etc. It is obvious that each of these dimensions deserves a separate thread of research efforts. One particular challenge among the ones listed above tha...
HyGraph: a subgraph isomorphism algorithm for efficiently querying big graph databases
Asiler, Merve; Yazıcı, Adnan; George, Roy (2022-04-01)
The big graph database provides strong modeling capabilities and efficient querying for complex applications. Subgraph isomorphism which finds exact matches of a query graph in the database efficiently, is a challenging problem. Current subgraph isomorphism approaches mostly are based on the pruning strategy proposed by Ullmann. These techniques have two significant drawbacks- first, they are unable to efficiently handle complex queries, and second, their implementations need the large indexes that require ...
BB-PLUS: an efficient approach for subgraph isomorphism problem in big graph databases
Taşkomaz, Ezgi; Yazıcı, Adnan; Department of Computer Engineering (2019)
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 appr...
An intelligent fuzzy object-oriented database framework for video database applications
Özgür, Nezihe Burcu; Yazıcı, Adnan; Department of Computer Engineering (2007)
Video database applications call for flexible and powerful modeling and querying facilities, which require an integration or interaction between database and knowledge base technologies. It is also necessary for many real life video database applications to incorporate uncertainty, which naturally occurs due to the complex and subjective semantic content of video data. In this thesis study, firstly, a fuzzy conceptual data model is introduced to represent the semantic content of video data. UML (Unified Mod...
Semantic information-based alternative plan generation for multiple query optimization
Polat, Faruk; Alhajj, R (Elsevier BV, 2001-09-01)
This paper addresses the impact of semantic information about queries on alternative plan generation (APG) for multiple query optimization (MQO). MQO covers optimizing the execution of a set of queries together where each query in the set to be optimized has several alternative execution plans. A multiple query optimizer selects an alternative plan for each query to obtain an optimal global execution plan. Our approach uses information such as common relations, common possible joins and common conditions to...
Citation Formats
M. Asiler, “BB-graph: a new subgraph isomorphism algorithm for querying big graph databases,” M.S. - Master of Science, Middle East Technical University, 2016.