A Survey on Distributed Graph Pattern Matching in Massive Graphs

Bouhenni, Sarra; Yahiaoui, Saïd; Nouali-Taboudjemat, Nadia; Kheddouci, Hamamache

A Survey on Distributed Graph Pattern Matching in Massive Graphs

Date

2021-02

Authors

Bouhenni, Sarra

Yahiaoui, Saïd

Nouali-Taboudjemat, Nadia

Kheddouci, Hamamache

Publisher

ACM

Abstract

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.

Keywords

Theory of computation, Distributed algorithms, Graph algorithms analysis, Computing methodologies, Graph pattern matching

URI

https://dl.cerist.dz/handle/CERIST/965

Collections

International Journal Papers

Full item page