Keyword pattern graph relaxation for selective result space expansion on linked data

Ananya Dass, Cem Aksoy, Aggeliki Dimitriou, Dimitri Theodoratos

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

6 Scopus citations


Keyword search is a popular technique for querying the ever growing repositories of RDF graph data. In recent years different approaches leverage a structural summary of the graph data to address the typical keyword search related problems. These approaches compute queries (pattern graphs) corresponding to alternative interpretations of the keyword query and the user selects one that matches her intention to be evaluated against the data. Though promising, these approaches suffer from a drawback: because summaries are approximate representations of the data, they might return empty answers or miss results which are relevant to the user intent. In this paper, we present a novel approach which combines the use of the structural summary and the user feedback with a relaxation technique for pattern graphs. We leverage pattern graph homomorphisms to define relaxed pattern graphs that are able to extract more results potentially of interest to the user. We introduce an operation on pattern graphs and we show that it can produce all relaxed pattern graphs. To guarantee that the result pattern graphs are as close to the initial pattern graph as possible, we devise different metrics to measure the degree of relaxation of a pattern graph.We design an algorithm that computes relaxed pattern graphs with non-empty answers in relaxation order. Finally, we run experiments to measure the effectiveness of our ranking of relaxed pattern graphs and the efficiency of our system.

Original languageEnglish (US)
Title of host publicationEngineering the Web in the Big Data Era - 15th International Conference, ICWE 2015, Proceedings
EditorsFlavius Frasincar, Geert-Jan Houben, Philipp Cimiano, Daniel Schwabe
PublisherSpringer Verlag
Number of pages20
ISBN (Electronic)9783319198897
StatePublished - 2015
Event15th International Conference on Web Engineering, ICWE 2015 - Rotterdam, Netherlands
Duration: Jun 23 2015Jun 26 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other15th International Conference on Web Engineering, ICWE 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Keyword pattern graph relaxation for selective result space expansion on linked data'. Together they form a unique fingerprint.

Cite this