HyGraph: a subgraph isomorphism algorithm for efficiently querying big graph databases

Asiler M. Yazıcı A. George R.
December 2022 Springer Science and Business Media Deutschland GmbH

Journal of Big Data
2022 #9 Issue 1

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 large memory resources. In this paper, we describe a new subgraph isomorphism approach, the HyGraph algorithm, that is efficient both in querying and with memory requirements for index creation. We compare the HyGraph algorithm with two popular existing approaches, GraphQL and Cypher using complexity measures and experimentally using three big graph data sets—(1) a country-level population database, (2) a simulated bank database, and (3) a publicly available World Cup big graph database. It is shown that the HyGraph solution performs significantly better (or equally) than competing algorithms for the query operations on these big databases, making it an excellent candidate for subgraph isomorphism queries in real scenarios.

Exact matching algorithm , Graph database , Neo4j databases , Query graph search , Subgraph isomorphism problem

Text of the article Перейти на текст статьи

Department of Computer Engineering, Middle East Technical University, Dumlupınar Bulvarı, Ankara, 06800, Turkey
Department of Cyber-Physical Systems, Clark Atlanta University, 223 James Brawley Drive, Atlanta, 30314, United States
Department of Computer Science, School of Science and Technology, Nazarbayev University, Dastana, Kazakhstan

Department of Computer Engineering
Department of Cyber-Physical Systems
Department of Computer Science

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026