tutorial

PGX.ISO: Parallel and Efficient In-Memory Engine for Subgraph Isomorphism

Authors:

Raghavan Raman,

Oskar van Rest,

Jay BanerjeeAuthors Info & Claims

GRADES'14: Proceedings of Workshop on GRAph Data management Experiences and Systems

Pages 1 - 6

https://doi.org/10.1145/2621934.2621939

Published: 22 June 2014 Publication History

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.

References

[1]

Property graph model. https://github.com/tinkerpop/blueprints/wiki/Property-Graph-Model. {Online; accessed 5/19/2014}.

[2]

M. Bravenboer, K. T. Kalleberg, R. Vermaas, and E. Visser. Stratego/XT 0.17. A language and toolset for program transformation. Science of Computer Programming, 2008.

Digital Library

[3]

O. Erling and I. Mikhailov. In Conference on Social Semantic Web, 2007.

[4]

Y. Guo, Z. Pan, and J. Heflin. Lubm: A benchmark for owl knowledge base systems. Semantic Web Journal, 2005.

Digital Library

[5]

W.-S. Han, J. Lee, and J.-H. Lee. Turboiso: Towards ultrafast and robust subgraph isomorphism search in large graph databases. SIGMOD, 2013.

Digital Library

[6]

S. Hong, H. Chafi, E. Sedlar, and K. Olukotun. Green-Marl: a DSL for easy and efficient graph analysis. In ASPLOS, 2012.

Digital Library

[7]

L. C. L. Kats and E. Visser. The Spoofax language workbench: rules for declarative specification of languages and IDEs. In OOPSLA, 2010.

Digital Library

[8]

J. Lee, W.-S. Han, R. Kasperovics, and J.-H. Lee. An in-depth comparison of subgraph isomorphism algorithms in graph databases. PVLDB, 2013.

Digital Library

[9]

C. Murray. Oracle spatial and graph - rdf semantic graph developer's guide. http://docs.oracle.com/cd/E16655_01/appdev.121/e17895.pdf, 2014. {Online; accessed 5/19/2014}.

[10]

Neo4j. Neo4j, the world's leading graph database. http://www.neo4j.org/, 2013.

[11]

L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell., 2004.

Digital Library

[12]

H. Shang, Y. Zhang, X. Lin, and J. X. Yu. Taming verification hardness: An efficient algorithm for testing subgraph isomorphism. Proc. VLDB Endow., 2008.

Digital Library

[13]

Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li. Efficient subgraph matching on billion node graphs. Proc. VLDB Endow., 2012.

Digital Library

[14]

J. R. Ullmann. An algorithm for subgraph isomorphism. J. ACM, 1976.

Digital Library

[15]

O. van Rest, G. Wachsmuth, J. R. H. Steel, J. G. Süß, and E. Visser. Robust real-time synchronization between textual and graphical editors. In ICMT, 2013.

[16]

W3C. RDF Primer. http://www.w3.org/TR/rdf-primer/, 2004. {Online; accessed 5/19/2014}.

[17]

W3C. SPARQL 1.1 Query Language. http://www.w3.org/TR/sparql11-query/, Mar. 2013. {Online; accessed 5/19/2014}.

Cited By

Sharma AMehta DWu B(2024)Understanding High-Performance Subgraph Pattern Matching: A Systems PerspectiveProceedings of the 7th Joint Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)10.1145/3661304.3661897(1-12)Online publication date: 14-Jun-2024
https://dl.acm.org/doi/10.1145/3661304.3661897
Benachour AYahiaoui SBouhenni SKheddouci HNouali-Taboudjemat N(2024)GPU-accelerated relaxed graph pattern matching algorithmsThe Journal of Supercomputing10.1007/s11227-024-06283-780:15(21811-21836)Online publication date: 16-Jun-2024
https://doi.org/10.1007/s11227-024-06283-7
Firmli SChiadmi D(2023)A Scalable Data Structure for Efficient Graph Analytics and In-Place MutationsData10.3390/data81101668:11(166)Online publication date: 3-Nov-2023
https://doi.org/10.3390/data8110166
Show More Cited By

Index Terms

PGX.ISO: Parallel and Efficient In-Memory Engine for Subgraph Isomorphism
1. Information systems
  1. Data management systems
    1. Database management system engines
  2. Information systems applications
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

On the Multichromatic Number of s-Stable Kneser Graphs

For positive integers n and s, a subset Sï [n] is s-stable if sï |i-j|ï n-s for distinct i,j∈S . The s-stable r-uniform Kneser hypergraph KGrn,ks-stable is the r-uniform hypergraph that has the collection of all s-stable k-element subsets of [n] as ...
Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes

An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the ...
Forbidden Subgraphs and Weak Locally Connected Graphs

A graph is called H-free if it has no induced subgraph isomorphic to H. A graph is called $$N^i$$Ni-locally connected if $$G[\{ x\in V(G): 1\le d_G(w, x)\le i\}]$$G[{x?V(G):1≤dG(w,x)≤i}] is connected and $$N_2$$N2-locally connected if $$G[\{uv: \{uw, vw\...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GRADES'14: Proceedings of Workshop on GRAph Data management Experiences and Systems

June 2014

79 pages

ISBN:9781450329828

DOI:10.1145/2621934

Program Chairs:
Peter Boncz
CWI
,
Josep Lluis Larriba Pey
UPC Catalunya

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Tutorial
Research
Refereed limited

Conference

SIGMOD/PODS'14

Sponsor:

SIGMOD

SIGMOD/PODS'14: International Conference on Management of Data

June 22 - 27, 2014

UT, Snowbird, USA

Acceptance Rates

Overall Acceptance Rate 29 of 61 submissions, 48%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
304
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sharma AMehta DWu B(2024)Understanding High-Performance Subgraph Pattern Matching: A Systems PerspectiveProceedings of the 7th Joint Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)10.1145/3661304.3661897(1-12)Online publication date: 14-Jun-2024
https://dl.acm.org/doi/10.1145/3661304.3661897
Benachour AYahiaoui SBouhenni SKheddouci HNouali-Taboudjemat N(2024)GPU-accelerated relaxed graph pattern matching algorithmsThe Journal of Supercomputing10.1007/s11227-024-06283-780:15(21811-21836)Online publication date: 16-Jun-2024
https://doi.org/10.1007/s11227-024-06283-7
Firmli SChiadmi D(2023)A Scalable Data Structure for Efficient Graph Analytics and In-Place MutationsData10.3390/data81101668:11(166)Online publication date: 3-Nov-2023
https://doi.org/10.3390/data8110166
Yang ZZhang WLin XZhang YLi S(2023)HGMatch: A Match-by-Hyperedge Approach for Subgraph Matching on Hypergraphs2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00160(2063-2076)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00160
Liang WDong WYuan M(2023)SLF: A passive parallelization of subgraph isomorphismInformation Sciences10.1016/j.ins.2022.12.033623(900-914)Online publication date: Apr-2023
https://doi.org/10.1016/j.ins.2022.12.033
Guo WLi YTan K(2022)Exploiting Reuse for GPU Subgraph EnumerationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.303556434:9(4231-4244)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TKDE.2020.3035564
Zhang XXiao GDuan MChen YLi K(2022)PH-CF: A Phased Hybrid Algorithm for Accelerating Subgraph Matching based on CPU-FPGA Heterogeneous PlatformIEEE Transactions on Industrial Informatics10.1109/TII.2022.3217825(1-11)Online publication date: 2022
https://doi.org/10.1109/TII.2022.3217825
Mhedhbi ALissandrini MKuiper LWaudby JSzárnyas GKalavri VYakovets N(2021)LSQBProceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)10.1145/3461837.3464516(1-11)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3461837.3464516
Yang ZLai LLin XHao KZhang WLi GLi ZIdreos SSrivastava D(2021)HUGE: An Efficient and Scalable Subgraph Enumeration SystemProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457237(2049-2062)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457237
Fan WJin RLiu MLu PTian CZhou J(2020)Capturing associations in graphsProceedings of the VLDB Endowment10.14778/3407790.340779513:12(1863-1876)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407795
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents