Distributed Partial Simulation for Graph Pattern Matching

Simple item page
dc.contributor.authorAissam Aouar
dc.contributor.authorSaı̈d Yahiaoui
dc.contributor.authorLamia Sadeg
dc.contributor.authorNadia Nouali-Taboudjemat
dc.contributor.authorKadda Beghdad Bey
dc.date.accessioned2023-09-09T19:01:23Z
dc.date.available2023-09-09T19:01:23Z
dc.date.issued2022-11-21
dc.description.abstractPattern matching in big graphs is important for different modern applications. Recently, this problem was defined in terms of multiple extensions of graph simulation, to reduce complexity and capture more meaningful results. These results were achieved through the relaxation of commonly used constraint in subgraph isomorphism pattern matching. Nevertheless, these graph simulation variant models are still too strict to provide results in many cases, especially when analyzed graphs contain anomalies and incomplete information. To deal with this issue, we introduce a new graph pattern matching (GPM) method, called partial simulation, capable of retrieving matches despite missing parts of the pattern graph, such as vertices and/or edges. Furthermore, considering the number and inequality of the outputs, we define a relevance function to compute a value expressing how each match vertex respects the pattern graph. Similarly, we define partial dual simulation GPM that returns vertices that satisfy a part of the dual simulation constraints and assigns a relevance value to them. Additionally, we provide distributed scalable algorithms to evaluate the proposed partial simulation methods based on the distributed vertex-centric programming paradigm. Finally, our experiments on real-world data graphs demonstrate the effectiveness of the proposed models and the efficiency of their associated algorithms.
dc.identifier.otherhttps://doi.org/10.1093/comjnl/bxac161
dc.identifier.urihttps://dl.cerist.dz/handle/CERIST/974
dc.language.isoen
dc.publisherThe Computer Journal
dc.subjectBig graphs
dc.subjectGraph pattern matching
dc.subjectGraph simulation
dc.subjectDistributed computing
dc.subjectVertex-centric programming
dc.titleDistributed Partial Simulation for Graph Pattern Matching
dc.typeArticle
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Distributed Partial Simulation for Graph Pattern Matching.pdf
Size:
2.51 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
International Journal Papers