A New Way of Searching

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».

Search engines are continuously employing advanced techniques that aim to capture user intentions and provide results that go beyond the data that simply satisfy the query conditions. Examples include the personalized results, related searches, similarity search, popular and relaxed queries. 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», and claim that they can play an important role in dealing with the information deluge. We provide a formal specification of the semantics of such queries and show that they are fundamentally different from notions like queries by example, approximate and related queries.

We provide an implementation of these semantics for graph-based data and present an exact solution with a number of optimizations that improve performance without compromising the quality of the answers. We study two different congruence relations, isomorphism and strong simulation, for retrieving the answers to an exemplar query, and we provide solutions for both. We also provide an approximate solution that prunes the search space and achieves considerably better time-performance with minimal or no impact on effectiveness. We experimentally evaluate the effectiveness and efficiency of these solutions with synthetic and real datasets, and illustrate the usefulness of exemplar queries in practice.

Source Code

You may freely use this code for research purposes, provided that you properly acknowledge the authors using the following reference:

Davide Mottin, Matteo Lissandrini, Yannis Velegrakis, Themis Palpanas.
"Exemplar Queries: A New Way of Searching."
The VLDB Journal (2016) 25: 741.


See the Project Code

Freebase Snapshot

Freebase was a knowledge base containing data about varous topics, composed mainly by its community members. It also contained semi-structured data harvested from many sources, including individual, user-submitted wiki contributions. Freebase.com was officially shut down on 2 May 2016.

We downloaded a data-dump, cleaned from non-relevant meta-data, and normalized it. Our software is the only one currently known to run on the largest available snapshot of the freebase graph, comprising more than 300M facts.
We share here The Freebase ExQ Data Dump: see the details of our snapshot

Query Dataset

We extracted 100 queries from the AOL query log and mapped to equivalent graphs of Freebase entities and relationships and/or attributes.
Download Query-Set