Exemplar queries: a new way of searching

Davide Mottin, Matteo Lissandrini, Yannis Velegrakis, Themis Palpanas

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Modern search engines employ advanced techniques that go beyond the structures that strictly satisfy the query conditions in an effort to better capture the user intentions. In this work, we introduce a novel query paradigm that considers a user query as an example of the data in which the user is interested. We call these queries exemplar queries. We provide a formal specification of their semantics and show that they are fundamentally different from notions like queries by example, approximate queries and related queries. We provide an implementation of these semantics for knowledge graphs and present an exact solution with a number of optimizations that improve performance without compromising the result quality. We study two different congruence relations, isomorphism and strong simulation, for identifying the answers to an exemplar query. We also provide an approximate solution that prunes the search space and achieves considerably better time performance with minimal or no impact on effectiveness. The effectiveness and efficiency of these solutions with synthetic and real datasets are experimentally evaluated, and the importance of exemplar queries in practice is illustrated.
Original languageEnglish
Pages (from-to)741-765
Number of pages25
JournalVLDB Journal
Volume25
Issue number6
DOIs
Publication statusPublished - Dec 2016

Keywords

  • Exemplar query
  • Knowledge base
  • Knowledge graph
  • Query answering

Fingerprint

Dive into the research topics of 'Exemplar queries: a new way of searching'. Together they form a unique fingerprint.

Cite this