Grass: An efficient method for RDF subgraph matching

Xuedong Lyu, Xin Wang, Yuan-Fang Li, Zhiyong Feng, Junhu Wang

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    3 Citations (Scopus)

    Abstract

    Resource Description Framework (RDF) is a standard data model of the Semantic Web, and it has been widely adopted in various domains in recent years for data and knowledge representation. Unlike queries on relational databases, most of queries applied on RDF data are known as graph queries, expressed in the SPARQL language. Subgraph matching, a basic SPARQL operation, is known to be NP-complete. Coupled with the rapidly increasing volumes of RDF data, it makes efficient graph query processing a very challenging problem. This paper primarily focuses on providing an index scheme and corresponding algorithms that support the efficient solution of such queries. We present a subgraph matching query engine based on the FFD-index which is an indexing mechanism encoding a star subgraph into a bit string. A SPARQL query graph is decomposed into several star query subgraphs which can be efficiently processed benefiting from succinct FFD-index data structure. Extensive evaluation shows that our approach outperforms RDF-3X and gStore on solving subgraph matching.

    Original languageEnglish
    Title of host publicationWeb Information Systems Engineering - WISE 2015: 16th International Conference, Proceedings, Part I
    EditorsJianyong Wang, Wojciech Cellary, Dingding Wang, Hua Wang, Shu-Ching Chen, Tao Li, Yanchun Zhang
    Place of PublicationCham Switzerland
    PublisherSpringer
    Pages108-122
    Number of pages15
    Volume9418
    ISBN (Print)9783319261898
    DOIs
    Publication statusPublished - 2015
    EventInternational Conference on Web Information Systems Engineering 2015 - Miami, United States of America
    Duration: 1 Nov 20153 Nov 2015
    Conference number: 16th
    http://www4.cis.fiu.edu/wise2015/
    http://www.springer.com/gp/book/9783319261867 (Conference Proceedings)

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume9418
    ISSN (Print)03029743
    ISSN (Electronic)16113349

    Conference

    ConferenceInternational Conference on Web Information Systems Engineering 2015
    Abbreviated titleWISE 2015
    CountryUnited States of America
    CityMiami
    Period1/11/153/11/15
    Internet address

    Keywords

    • Graph-based index
    • RDF
    • Subgraph isomorphism

    Cite this

    Lyu, X., Wang, X., Li, Y-F., Feng, Z., & Wang, J. (2015). Grass: An efficient method for RDF subgraph matching. In J. Wang, W. Cellary, D. Wang, H. Wang, S-C. Chen, T. Li, & Y. Zhang (Eds.), Web Information Systems Engineering - WISE 2015: 16th International Conference, Proceedings, Part I (Vol. 9418, pp. 108-122). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9418). Springer. https://doi.org/10.1007/978-3-319-26190-4_8