Optimized Distributed Subgraph Matching Algorithm Based on Partition Replication
| Autor: | Peng Pan, Jiali Bin, Ling Yuan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Computer Networks and Communications
Computer science graph partition lcsh:TK7800-8360 02 engineering and technology distributed computing 020204 information systems subgraph matching 0202 electrical engineering electronic engineering information engineering Partition (number theory) Electrical and Electronic Engineering Blossom algorithm 020203 distributed computing Heuristic lcsh:Electronics Graph partition Rule-based system Partition (database) Graph Vertex (geometry) Hardware and Architecture Control and Systems Engineering Signal Processing graph indexing Graph indexing Algorithm MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Electronics, Vol 9, Iss 1, p 184 (2020) Electronics Volume 9 Issue 1 |
| ISSN: | 2079-9292 |
| Popis: | At present, with the explosive growth of data scale, subgraph matching for massive graph data is difficult to satisfy with efficiency. Meanwhile, the graph index used in existing subgraph matching algorithm is difficult to update and maintain when facing dynamic graphs. We propose a distributed subgraph matching algorithm based on Partition Replica (noted as PR-Match) to process the partition and storage of large-scale data graphs. The PR-Match algorithm first splits the query graph into sub-queries, then assigns the sub-query to each node for sub-graph matching, and finally merges the matching results. In the PR-Match algorithm, we propose a heuristic rule based on prediction cost to select the optimal merging plan, which greatly reduces the cost of merging. In order to accelerate the matching speed of the sub-query graph, a vertex code based on the vertex neighbor label signature is proposed, which greatly reduces the search space for the subquery. As the vertex code is based on the increment, the problem that the feature-based graph index is difficult to maintain in the face of the dynamic graph is solved. An abundance of experiments on real and synthetic datasets demonstrate the high efficiency and strong scalability of the PR-Match algorithm when handling large-scale data graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|