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

Download

index.pdf

Date

2016

Author

Asiler, Merve

Metadata

Show full item record

Item Usage Stats

306
views

114
downloads

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.

Subject Keywords

Isomorphisms (Mathematics)., Computer algorithms., Graph algorithms.

URI

http://etd.lib.metu.edu.tr/upload/12620537/index.pdf
https://hdl.handle.net/11511/25887

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

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...
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...
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 ...
Multiobjective evolutionary feature subset selection algorithm for binary classification Deniz Kızılöz, Firdevsi Ayça; Coşar, Ahmet; Dökeroğlu, Tansel; Department of Computer Engineering (2016) This thesis investigates the performance of multiobjective feature subset selection (FSS) algorithms combined with the state-of-the-art machine learning techniques for binary classification problem. Recent studies try to improve the accuracy of classification by including all of the features in the dataset, neglecting to determine the best performing subset of features. However, for some problems, the number of features may reach thousands, which will cause too much computation power to be consumed during t...
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.