Abstract | ||
---|---|---|
Subgraph isomorphism, or finding matching patterns in a graph, is a classic graph problem that has many practical use cases. There are even commercialized solutions for this problem such as RDF databases with their support for SPARQL queries. In this paper, we present an efficient, parallel in-memory solution to this problem. Our solution exploits efficient data representations as well as algorithmic extensions, both tailored for parallel, in-memory processing. Moreover, when processing RDF data, we reduce the problem size by converting certain nodes and edges into properties. We also propose a new graph query language where such a conversion can be encoded. Our evaluation shows that our solution can achieve significant performance boost over an existing secondary storage based RDF database. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1145/2621934.2621939 | GRADES |
Keywords | Field | DocType |
design,graphs and networks,experimentation,systems,measurement,performance | Graph database,Query language,Use case,Maximum common subgraph isomorphism problem,Computer science,SPARQL,Theoretical computer science,Subgraph isomorphism problem,RDF,Auxiliary memory | Conference |
Citations | PageRank | References |
7 | 0.52 | 9 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Raghavan Raman | 1 | 235 | 10.70 |
Oskar van Rest | 2 | 52 | 3.31 |
Sungpack Hong | 3 | 864 | 33.20 |
Zhe Wu | 4 | 55 | 5.93 |
Hassan Chafi | 5 | 1118 | 61.11 |
Jay Banerjee | 6 | 984 | 422.56 |