Abstract
Web search engines employ different techniques for broadening the answer sets beyond those data elements that strictly satisfy the user query conditions, in order to ensure they can capture the user intentions. This is necessary either because the query language used by the user is vague and ambitious (i.e., keyword queries), or because the user is inexperienced with the query language, or even because the user is not sure of what he/she is looking for (i.e., navigational queries). We introduce a novel query paradigm that cannot be satisfied by any of the techniques currently used. It assumes that the data described by the user query are only an example from the set of answers that the user is looking for. We call these queries “exemplar queries”. We claim that this is an important class of queries that can play an important role in coping with the current information deluge. We provide a formal specification of the semantics of such queries based on the notion of subgraph isomorphism, and show that they are fundamentally different from the notions of queries by exam- ple, approximate queries and related queries. We present an exact solution with a number of optimizations that improve the time performance without compromising the quality of the answers. We also provide an approximate solution that prunes the search space, achieving considerably better time performance with minimal or no impact on effectiveness. We experimentally evaluate our algorithms with synthetic and real datasets demonstrating not only the effectiveness and efficiency of our proposal, but also its usefulness in practice.
Dataset
We extracted 90 queries from the AOL query log and mapped to equivalent graphs of Freebase entities and relationships and/or attributes
We selected a sample of 50 queries, from the previous set, alongside with the results provided by our system. We annotated them with the appropriate user need for the user study
Source Code
You may freely use this code for research purposes, provided that you properly acknowledge the authors using the following references:Davide Mottin, Matteo Lissandrini, Yannis Velegrakis, Themis Palpanas. Exemplar Queries: A New Way of Searching. International Journal on Very Large Data Bases (VLDBJ), accepted for publication, 2016.
Davide Mottin, Matteo Lissandrini, Yannis Velegrakis, Themis Palpanas. Exemplar Queries: Give me an Example of What You Need. Proceedings of the VLDB Endowment (PVLDB) 7(5):365-376, 2014.
Davide Mottin, Matteo Lissandrini, Yannis Velegrakis, Themis Palpanas. Searching with XQ: the eXemplar Query Search Engine. ACM SIG International conference on Management of Data / Principles of Database Systems (SIGMOD/PODS), Snowbird, UT, USA, 2014.
Matteo Lissandrini, Davide Mottin, Themis Palpanas, Dimitra Papadimitriou, Yannis Velegrakis. Unleashing the Power of Information Graphs. ACM SIGMOD Record 43(4), 2014.