Header

UZH-Logo

Maintenance Infos

SPARQL Basic Graph Pattern Optimization Using Selectivity Estimation


Stocker, M; Seaborne, A; Bernstein, A; Kiefer, C; Reynolds, D (2008). SPARQL Basic Graph Pattern Optimization Using Selectivity Estimation. In: 17th International World Wide Web Conference (WWW), Beijing, China, 21 April 2008 - 25 April 2008.

Abstract

In this paper, we formalize the problem of Basic Graph Pattern (BGP) optimization for SPARQL queries and main memory graph implementations of RDF data. We define and analyze the characteristics of heuristics for selectivity-based static BGP optimization. The heuristics range from simple triple pattern variable counting to more sophisticated selectivity estimation techniques. Customized summary statistics for RDF data enable the selectivity estimation of joined triple patterns and the development of efficient heuristics. Using the Lehigh University Benchmark (LUBM), we evaluate the performance of the heuristics for the queries provided by the LUBM and discuss some of them in more details.

Note that the SPARQL versions of the 14 LUBM queries and the University0 data set we used in this paper can be downloaded from here.

Abstract

In this paper, we formalize the problem of Basic Graph Pattern (BGP) optimization for SPARQL queries and main memory graph implementations of RDF data. We define and analyze the characteristics of heuristics for selectivity-based static BGP optimization. The heuristics range from simple triple pattern variable counting to more sophisticated selectivity estimation techniques. Customized summary statistics for RDF data enable the selectivity estimation of joined triple patterns and the development of efficient heuristics. Using the Lehigh University Benchmark (LUBM), we evaluate the performance of the heuristics for the queries provided by the LUBM and discuss some of them in more details.

Note that the SPARQL versions of the 14 LUBM queries and the University0 data set we used in this paper can be downloaded from here.

Statistics

Citations

Downloads

242 downloads since deposited on 29 Jan 2009
39 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Event End Date:25 April 2008
Deposited On:29 Jan 2009 15:25
Last Modified:10 Aug 2017 18:31

Download

Preview Icon on Download
Preview
Filetype: PDF
Size: 1MB