Efficient execution of top-K SPARQL queries

Conference paper (2012)

Authors

Sara Magliacane Politecnico di Milano, Vrije Universiteit Amsterdam
A. Bozzon Politecnico di Milano
Emanuele Della Valle Politecnico di Milano
Affiliation
External organisation
More Info
expand_more

Published Date

2012

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

Abstract

Top-k queries, i.e. queries returning the top k results ordered by a user-defined scoring function, are an important category of queries. Order is an important property of data that can be exploited to speed up query processing. State-of-the-art SPARQL engines underuse order, and top-k queries are mostly managed with a materialize-then-sort processing scheme that computes all the matching solutions (e.g. thousands) even if only a limited number k (e.g. ten) are requested. The PARQL-ANK algebra is an extended SPARQL algebra that treats order as a first class citizen, enabling efficient split-and-interleave processing schemes that can be adopted to improve the performance of top-k SPARQL queries. In this paper we propose an incremental execution model for PARQL-ANK queries, we compare the performance of alternative physical operators, and we propose a rank-aware join algorithm optimized for native RDF stores. Experiments conducted with an open source implementation of a PARQL-ANK query engine based on ARQ show that the evaluation of top-k queries can be sped up by orders of magnitude.