Grass: An efficient method for RDF subgraph matching

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

doi:10.1007/978-3-319-26190-4_8

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 proceeding › Conference Paper › Research › peer-review

7 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 language	English
Title of host publication	Web Information Systems Engineering - WISE 2015: 16th International Conference, Proceedings, Part I
Editors	Jianyong Wang, Wojciech Cellary, Dingding Wang, Hua Wang, Shu-Ching Chen, Tao Li, Yanchun Zhang
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	108-122
Number of pages	15
Volume	9418
ISBN (Print)	9783319261898
DOIs	https://doi.org/10.1007/978-3-319-26190-4_8
Publication status	Published - 2015
Event	International Conference on Web Information Systems Engineering 2015 - Miami, United States of America Duration: 1 Nov 2015 → 3 Nov 2015 Conference number: 16th http://www4.cis.fiu.edu/wise2015/ https://link.springer.com/book/10.1007/978-3-319-26190-4 (Conference Proceedings)

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9418
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	International Conference on Web Information Systems Engineering 2015
Abbreviated title	WISE 2015
Country/Territory	United States of America
City	Miami
Period	1/11/15 → 3/11/15
Internet address	http://www4.cis.fiu.edu/wise2015/ https://link.springer.com/book/10.1007/978-3-319-26190-4 (Conference Proceedings)

Keywords

Graph-based index
RDF
Subgraph isomorphism

Access to Document

10.1007/978-3-319-26190-4_8

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

Lyu, Xuedong ; Wang, Xin ; Li, Yuan-Fang et al. / Grass : An efficient method for RDF subgraph matching. Web Information Systems Engineering - WISE 2015: 16th International Conference, Proceedings, Part I. editor / Jianyong Wang ; Wojciech Cellary ; Dingding Wang ; Hua Wang ; Shu-Ching Chen ; Tao Li ; Yanchun Zhang. Vol. 9418 Cham Switzerland : Springer, 2015. pp. 108-122 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{77400891f8854bc7ac240364fc395964,

title = "Grass: An efficient method for RDF subgraph matching",

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.",

keywords = "Graph-based index, RDF, Subgraph isomorphism",

author = "Xuedong Lyu and Xin Wang and Yuan-Fang Li and Zhiyong Feng and Junhu Wang",

year = "2015",

doi = "10.1007/978-3-319-26190-4_8",

language = "English",

isbn = "9783319261898",

volume = "9418",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "108--122",

editor = "Jianyong Wang and Wojciech Cellary and Dingding Wang and Hua Wang and Shu-Ching Chen and Tao Li and Yanchun Zhang",

booktitle = "Web Information Systems Engineering - WISE 2015: 16th International Conference, Proceedings, Part I",

note = "International Conference on Web Information Systems Engineering 2015, WISE 2015 ; Conference date: 01-11-2015 Through 03-11-2015",

url = "http://www4.cis.fiu.edu/wise2015/, https://link.springer.com/book/10.1007/978-3-319-26190-4",

}

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, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9418, Springer, Cham Switzerland, pp. 108-122, International Conference on Web Information Systems Engineering 2015, Miami, Florida, United States of America, 1/11/15. https://doi.org/10.1007/978-3-319-26190-4_8

Grass: An efficient method for RDF subgraph matching. / Lyu, Xuedong; Wang, Xin; Li, Yuan-Fang et al.
Web Information Systems Engineering - WISE 2015: 16th International Conference, Proceedings, Part I. ed. / Jianyong Wang; Wojciech Cellary; Dingding Wang; Hua Wang; Shu-Ching Chen; Tao Li; Yanchun Zhang. Vol. 9418 Cham Switzerland: Springer, 2015. p. 108-122 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9418).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Grass

T2 - International Conference on Web Information Systems Engineering 2015

AU - Lyu, Xuedong

AU - Wang, Xin

AU - Li, Yuan-Fang

AU - Feng, Zhiyong

AU - Wang, Junhu

N1 - Conference code: 16th

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Graph-based index

KW - RDF

KW - Subgraph isomorphism

UR - http://www.scopus.com/inward/record.url?scp=84958545005&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-26190-4_8

DO - 10.1007/978-3-319-26190-4_8

M3 - Conference Paper

SN - 9783319261898

VL - 9418

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 108

EP - 122

BT - Web Information Systems Engineering - WISE 2015: 16th International Conference, Proceedings, Part I

A2 - Wang, Jianyong

A2 - Cellary, Wojciech

A2 - Wang, Dingding

A2 - Wang, Hua

A2 - Chen, Shu-Ching

A2 - Li, Tao

A2 - Zhang, Yanchun

PB - Springer

CY - Cham Switzerland

Y2 - 1 November 2015 through 3 November 2015

ER -

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

Grass: An efficient method for RDF subgraph matching

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this