Exemplar Queries: A New Way of Searching

Davide Mottin, Matteo Lissandrini, Themis Palpanas, Yannis Velegrakis


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.


Exemplar Queries: A New Way of Searching.”
The VLDB Journal , 25, (6) (): 741-765.

 author = {Mottin, Davide and Lissandrini, Matteo and Velegrakis, Yannis and Palpanas, Themis},
 title = {Exemplar Queries: A New Way of Searching},
 journal = {The VLDB Journal},
 issue_date = {December  2016},
 volume = {25},
 number = {6},
 year = {2016},
 issn = {1066-8888},
 pages = {741--765},
 numpages = {25},
 url = { https://doi.org/10.1007/s00778-016-0429-2 },
 doi = {10.1007/s00778-016-0429-2},
 acmid = {3016789},
 publisher = {Springer-Verlag New York, Inc.},
 address = {Secaucus, NJ, USA},
 keywords = {Exemplar query, Knowledge base, Knowledge graph, Query answering},