Exemplar queries: a new way of searching

Davide Mottin, Matteo Lissandrini*, Yannis Velegrakis, Themis Palpanas

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

45 Citations (Scopus)


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
JournalVLDB Journal
Issue number6
Pages (from-to)741-765
Number of pages25
Publication statusPublished - 1 Dec 2016
Externally publishedYes


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


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

Cite this