Exemplar queries: a new way of searching

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

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

45 Citationer (Scopus)

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.

OriginalsprogEngelsk
TidsskriftVLDB Journal
Vol/bind25
Udgave nummer6
Sider (fra-til)741-765
Antal sider25
ISSN1066-8888
DOI
StatusUdgivet - 1 dec. 2016
Udgivet eksterntJa

Fingeraftryk

Dyk ned i forskningsemnerne om 'Exemplar queries: a new way of searching'. Sammen danner de et unikt fingeraftryk.

Citationsformater