Paper 14 (Research track)

Answers Partitioning and Lazy Joins for Efficient Query Relaxation and Application to Similarity Search

Author(s): Sebastien Ferre

Abstract: Query relaxation has been studied as a way to find approximate
answers when user queries are too specific or do not align well with
the data schema. We are here interested in the application of query
relaxation to similarity search of RDF nodes based on their
description. However, this is challenging because existing
approaches have a complexity that grows in a combinatorial way with
the size of the query and the number of relaxation steps. We
introduce two algorithms, answers partitioning and lazy join, that
together significantly improve the efficiency of query
relaxation. Our experiments show that our approach scales much
better with the size of queries and the number of relaxation steps,
to the point where it becomes possible to relax large node
descriptions in order to find similar nodes. Moreover, the relaxed
descriptions provide explanations for their semantic similarity.

Keywords: Query Relaxation; Approximate Answer; Similarity Search; RDF Graph; Graph Pattern; Partition; Join

Share on

Leave a Reply

Your email address will not be published. Required fields are marked *