GraphMini: Accelerating Graph Pattern Matching Using Auxiliary Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917602666741760 |
|---|---|
| author | Liu, Juelin Polisetty, Sandeep Guan, Hui Serafini, Marco |
| author_facet | Liu, Juelin Polisetty, Sandeep Guan, Hui Serafini, Marco |
| contents | Graph pattern matching is a fundamental problem encountered by many common graph mining tasks and the basic building block of several graph mining systems.
This paper explores for the first time how to proactively prune graphs to speed up graph pattern matching by leveraging the structure of the query pattern and the input graph.
We propose building auxiliary graphs, which are different pruned versions of the graph, during query execution.
This requires careful balancing between the upfront cost of building and managing auxiliary graphs and the gains of faster set operations.
To this end, we propose GraphMini, a new system that uses query compilation and a new cost model to minimize the cost of building and maintaining auxiliary graphs and maximize gains.
Our evaluation shows that using GraphMini can achieve one order of magnitude speedup compared to state-of-the-art subgraph enumeration systems on commonly used benchmarks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_01050 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | GraphMini: Accelerating Graph Pattern Matching Using Auxiliary Graphs Liu, Juelin Polisetty, Sandeep Guan, Hui Serafini, Marco Databases Performance Graph pattern matching is a fundamental problem encountered by many common graph mining tasks and the basic building block of several graph mining systems. This paper explores for the first time how to proactively prune graphs to speed up graph pattern matching by leveraging the structure of the query pattern and the input graph. We propose building auxiliary graphs, which are different pruned versions of the graph, during query execution. This requires careful balancing between the upfront cost of building and managing auxiliary graphs and the gains of faster set operations. To this end, we propose GraphMini, a new system that uses query compilation and a new cost model to minimize the cost of building and maintaining auxiliary graphs and maximize gains. Our evaluation shows that using GraphMini can achieve one order of magnitude speedup compared to state-of-the-art subgraph enumeration systems on commonly used benchmarks. |
| title | GraphMini: Accelerating Graph Pattern Matching Using Auxiliary Graphs |
| topic | Databases Performance |
| url | https://arxiv.org/abs/2403.01050 |