Efficient execution of top-K SPARQL queries

Sara Magliacane, Alessandro Bozzon, Emanuele Della Valle

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

28 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationThe Semantic Web, ISWC 2012
Subtitle of host publication11th International Semantic Web Conference, Proceedings
Number of pages17
Publication statusPublished - 2012
Externally publishedYes
Event11th International Semantic Web Conference, ISWC 2012 - Boston, MA, United States
Duration: 11 Nov 201215 Nov 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7649 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Conference11th International Semantic Web Conference, ISWC 2012
CountryUnited States
CityBoston, MA

Fingerprint Dive into the research topics of 'Efficient execution of top-K SPARQL queries'. Together they form a unique fingerprint.

Cite this