tutorial

Graph Pattern Matching: Do We Have to Reinvent the Wheel?

Authors:

Andrey Gubichev,

Manuel ThenAuthors Info & Claims

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

Pages 1 - 7

https://doi.org/10.1145/2621934.2621944

Published: 22 June 2014 Publication History

Get Access

Abstract

This paper presents an empirical study of how a wide spectrum of systems handle the graph pattern matching problem. Our approach is to take the well-known LUBM benchmark, model it across various domains (relational, RDF, property graph), and execute the benchmark queries on the corresponding systems. We evaluate the systems using a large data instance on a single machine (the largest dataset is LUBM-8000, which contains over 1 billion RDF triples). Additionally, we provide a brief analysis of how different cases of graph pattern matching problem are stressed by the benchmark queries. Our main finding is that, contrary to popular belief and various vendors' claims, modern native graph stores do not necessarily offer a competitive advantage over traditional relational and RDF stores, even for the graph-specific problem of pattern matching. To the best of our knowledge, this is the first independent empirical comparison of different approaches towards pattern matching performed on a large scale graph.

References

[1]

D. D. Abreu, A. Flores, G. Palma, V. Pestana, J. Piñero, J. Queipo, J. Sánchez, and M.-E. Vidal. Choosing between graph databases and rdf engines for consuming and mining linked data. In COLD, 2013.

Google Scholar

[2]

R. Angles, A. Prat-Pérez, D. Dominguez-Sal, and J.-L. Larriba-Pey. Benchmarking database systems for social network applications. In GRADES, page 15, 2013.

Digital Library

Google Scholar

[3]

Y. Guo, Z. Pan, and J. Heflin. LUBM: A Benchmark for OWL Knowledge Base Systems. Web Semant., 3(2-3):158--182, Oct. 2005.

Digital Library

Google Scholar

[4]

S. Jouili and V. Vansteenberghe. An empirical comparison of graph databases. In SocialCom, pages 708--715. IEEE, 2013.

Digital Library

Google Scholar

[5]

P. Macko, D. W. Margo, and M. I. Seltzer. Performance introspection of graph databases. In SYSTOR, page 18, 2013.

Digital Library

Google Scholar

[6]

T. Neumann and G. Moerkotte. Characteristic sets: Accurate cardinality estimation for rdf queries with multiple joins. In ICDE, pages 984--994, 2011.

Digital Library

Google Scholar

[7]

H. Q. Ngo, C. Ré, and A. Rudra. Skew strikes back: new developments in the theory of join algorithms. SIGMOD Record, 42(4):5--16, 2013.

Digital Library

Google Scholar

[8]

M.-D. Pham. Self-organizing structured rdf in monetdb. In ICDE Workshops, pages 310--313, 2013.

Crossref

Google Scholar

[9]

P. Stutz, M. Verman, L. Fischer, and A. Bernstein. Triplerush: A fast and scalable triple store. In SSWS@ISWC, pages 50--65, 2013.

Google Scholar

[10]

A. Welc, R. Raman, Z. Wu, S. Hong, H. Chafi, and J. Banerjee. Graph analysis: do we have to reinvent the wheel? In GRADES, page 7, 2013.

Digital Library

Google Scholar

Cited By

View all

Gaikwad VPatil A(2023)Factoid Question Answering System using Knowledge Graph2023 7th International Conference On Computing, Communication, Control And Automation (ICCUBEA)10.1109/ICCUBEA58933.2023.10392192(1-4)Online publication date: 18-Aug-2023
https://doi.org/10.1109/ICCUBEA58933.2023.10392192
Srivastava SAgrahari SSingh A(2023)Early Spam Detection Using Time-Based Cache in Graph databaseNew Generation Computing10.1007/s00354-023-00223-441:3(607-634)Online publication date: 13-Jun-2023
https://doi.org/10.1007/s00354-023-00223-4
Srivastava SSingh A(2022)Fraud detection in the distributed graph databaseCluster Computing10.1007/s10586-022-03540-326:1(515-537)Online publication date: 24-Jan-2022
https://doi.org/10.1007/s10586-022-03540-3
Show More Cited By

Index Terms

Graph Pattern Matching: Do We Have to Reinvent the Wheel?
1. Information systems
  1. Information systems applications

Recommendations

Graph pattern matching: from intractable to polynomial time

Graph pattern matching is typically defined in terms of subgraph isomorphism, which makes it an np-complete problem. Moreover, it requires bijective functions, which are often too restrictive to characterize patterns in emerging applications. We propose ...
A Benchmark Evaluation of Incremental Pattern Matching in Graph Transformation
ICGT '08: Proceedings of the 4th international conference on Graph Transformations

In graph transformation, the most cost-intensive phase of a transformation execution is pattern matching, where those subgraphs of a model graph are identified and matched which satisfy constraints prescribed by graph patterns. Incremental pattern ...
Scalable Pattern Matching over Compressed Graphs via Dedensification
KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

One of the most common operations on graph databases is graph pattern matching (e.g., graph isomorphism and more general types of "subgraph pattern matching"). In fact, in some graph query languages every single query is expressed as a graph matching ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

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]

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

Author Tags

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

11
Total Citations
View Citations
372
Total Downloads

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

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gaikwad VPatil A(2023)Factoid Question Answering System using Knowledge Graph2023 7th International Conference On Computing, Communication, Control And Automation (ICCUBEA)10.1109/ICCUBEA58933.2023.10392192(1-4)Online publication date: 18-Aug-2023
https://doi.org/10.1109/ICCUBEA58933.2023.10392192
Srivastava SAgrahari SSingh A(2023)Early Spam Detection Using Time-Based Cache in Graph databaseNew Generation Computing10.1007/s00354-023-00223-441:3(607-634)Online publication date: 13-Jun-2023
https://doi.org/10.1007/s00354-023-00223-4
Srivastava SSingh A(2022)Fraud detection in the distributed graph databaseCluster Computing10.1007/s10586-022-03540-326:1(515-537)Online publication date: 24-Jan-2022
https://doi.org/10.1007/s10586-022-03540-3
Chaudhuri DRony MLehmann J(2021)Grounding Dialogue Systems via Knowledge Graph Aware Decoding with Pre-trained TransformersThe Semantic Web10.1007/978-3-030-77385-4_19(323-339)Online publication date: 31-May-2021
https://doi.org/10.1007/978-3-030-77385-4_19
Maiolo SEtcheverry LMarotta A(2020)Data Profiling in Property Graph DatabasesJournal of Data and Information Quality10.1145/340947312:4(1-27)Online publication date: 15-Oct-2020
https://dl.acm.org/doi/10.1145/3409473
Dubey MBanerjee DChaudhuri DLehmann J(2018)EARL: Joint Entity and Relation Linking for Question Answering over Knowledge GraphsThe Semantic Web – ISWC 201810.1007/978-3-030-00671-6_7(108-126)Online publication date: 18-Sep-2018
https://doi.org/10.1007/978-3-030-00671-6_7
Sumrall JFletcher GPoulovassilis ASvensson JVejlstrup MVest CWebber J(2017)Investigations on Path Indexing for Graph DatabasesEuro-Par 2016: Parallel Processing Workshops10.1007/978-3-319-58943-5_43(532-544)Online publication date: 28-May-2017
https://doi.org/10.1007/978-3-319-58943-5_43
Gillani SPicard GLaforest F(2016)SPECTRAProceedings of the 28th International Conference on Scientific and Statistical Database Management10.1145/2949689.2949701(1-12)Online publication date: 18-Jul-2016
https://dl.acm.org/doi/10.1145/2949689.2949701
Gillani SPicard GLaforest FGal AWeidlich MKalogeraki VVenkasubramanian N(2016)Continuous graph pattern matching over knowledge graph streamsProceedings of the 10th ACM International Conference on Distributed and Event-based Systems10.1145/2933267.2933306(214-225)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2933267.2933306
Hong SLee SLim SSukumar SVatsavai RNakashima HTaura KLange J(2016)Evaluation of Pattern Matching Workloads in Graph Analysis SystemsProceedings of the 25th ACM International Symposium on High-Performance Parallel and Distributed Computing10.1145/2907294.2907305(263-266)Online publication date: 31-May-2016
https://dl.acm.org/doi/10.1145/2907294.2907305
Show More Cited By

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Graph pattern matching: from intractable to polynomial time

A Benchmark Evaluation of Incremental Pattern Matching in Graph Transformation

Scalable Pattern Matching over Compressed Graphs via Dedensification