TY - GEN
T1 - Efficient execution of top-K SPARQL queries
AU - Magliacane, Sara
AU - Bozzon, Alessandro
AU - Della Valle, Emanuele
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84868533573&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-35176-1-22
DO - 10.1007/978-3-642-35176-1-22
M3 - Conference contribution
AN - SCOPUS:84868533573
SN - 978-3-642-35175-4
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 344
EP - 360
BT - The Semantic Web, ISWC 2012
T2 - 11th International Semantic Web Conference, ISWC 2012
Y2 - 11 November 2012 through 15 November 2012
ER -