R2DF framework for ranked path queries over weighted RDF graphs

Juan P. Cedeño, Kasim Candan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Resource Description Framework (RDF) is a semantic web specification that aims to support conceptual modeling of information about resources in the form of a triples of facts. In this paper, we note that, although RDF provides mechanisms to encode meta-information (such as source, trust, or certainty) about facts recorded in the knowledge base, existing RDF query languages and RDF stores fail to support key primitives needed in a large class of knowledge applications which associate utilities or costs on the available knowledge statements. To address this shortcoming, we propose a novel R2DF framework for utility ranked resource descriptions. We first propose a simple ranked RDF (R2DF) specification to enhance RDF triples with an application specific weight (e.g. cost). We then propose a SPARankQL query language specification, which includes a set of novel primitives on top of the SPARQL language to express top-k queries using traditional query patterns as well as novel flexible path predicates. An extended query processor engine, AR2Q, leverages novel index structures to support efficient ranked path search and includes query optimization strategies based on two key metrics: (a) proximity and (b) sub-result inter-arrival time. Experiments show that the use of these two metrics has significant impacts on the performance of top-k queries over R2DF graphs: in particular, the proximity measure helps reduce the number of path matches that need to be considered, whereas the inter-arrival measure reduces the overall execution time significantly especially when used along with proximity. The proposed strategies help obtain query plans close to optimal.

Original languageEnglish (US)
Title of host publicationWIMS'11 - Proceedings of the International Conference on Web Intelligence, Mining and Semantics
StatePublished - 2011
Event1st International Conference on Web Intelligence, Mining and Semantics, WIMS'11 - Sogndal, Norway
Duration: May 25 2011May 27 2011

Publication series

NameACM International Conference Proceeding Series


Other1st International Conference on Web Intelligence, Mining and Semantics, WIMS'11

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'R2DF framework for ranked path queries over weighted RDF graphs'. Together they form a unique fingerprint.

Cite this