Big data

Line graph

Algorithm

Statistics

Theoretical computer science

Vertex (graph theory)

Time complexity

Crystal structure

Isomorphism (crystallography)

Data mining

Computer science

Graph isomorphism

Graph

Mathematics

Subgraph isomorphism problem

Artificial intelligence

Crystallography

Matching (statistics)

Chemistry

Pattern matching

ACM Computing Surveys

Besides its NP-completeness, the strict constraints of subgraph isomorphism are making it impractical for graph pattern matching (GPM) in the context of big data. As a result, relaxed GPM models have emerged as they yield interesting results in a polynomial time. However, massive graphs generated by mostly social networks require a distributed storing and processing of the data over multiple machines, thus, requiring GPM to be revised by adopting new paradigms of big graphs processing, e.g., Think-Like-A-Vertex and its derivatives. This article discusses and proposes a classification of distributed GPM approaches with a narrow focus on the relaxed models.

A Survey on Distributed Graph Pattern Matching in Massive Graphs