XReason: A semantic approach that reasons with patterns to answer XML keyword queries

Keyword search is a popular technique which allows querying multiple data sources on the web without having full knowledge of their structure. This flexibility comes with a drawback: usually, even though a large number of results match the user's request only few of them are relevant to her intent. Since data on the web are often in tree-structured form, several approaches have been suggested in the past which attempt to exploit the structural properties of the data in order to filter out irrelevant results and return meaningful answers. This is certainly a difficult task, and depending on the type of dataset, these approaches show low precision and/or recall. In this paper, we introduce an original approach for answering keyword queries called XReason. XReason identifies structural patterns in the keyword matches and reasons with them in order to return meaningful results and to rank them with respect to their relevance. Our semantics shows a non-monotonic behavior and in the presence of additional patterns, it is able to better converge to the users intent. We design an efficient stack-based algorithm for evaluating keyword queries on tree structured data, and we run experiments to evaluate its efficiency and the effectiveness of our semantics as a filtering and ranking system. Our results show that our approach shows better performance than the other approaches in many cases of real and benchmark datasets.