Statistics

Algorithm

Data mining

Graph

Artificial intelligence

Matching (statistics)

Line graph

Time complexity

Mathematics

Computer science

Graph isomorphism

Pattern matching

Big data

Theoretical computer science

Vertex (graph theory)

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