Diversifying top-k Answers in a Query by Example Setting

Grégory Smits (1, 2, 3) , Marie-Jeanne Lesot (4) , Olivier Pivert (5) , Marek Reformat (6)

1 IMT Atlantique - INFO - Département Informatique
2 Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
3 Lab-STICC_MOTEL - Equipe MOTEL
4 LFI - Learning, Fuzzy and Intelligent systems
5 IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires
6 University of Alberta

For a given data base T and a user query Q, the top-k answers are the k tuples from T that best match Q. The integration of a diversity constraint aims at avoiding returning redundant tuples, that are too similar one to another. This paper addresses the diversification question in the Query By Example setting, especially for approaches that can deal with possibly very different representative examples provided by the user. It proposes a new definition for diversity that depends on the query, in order to guarantee that the result set illustrates the diversity of the representative examples provided by the user, covering all components of the query. The paper proposes a numerical measure to assess diversity in that sense, an algorithm to identify such a diversified top-k set, optimising both the query satisfaction and the diversity measure, as well as its integration into a flexible querying approach.

Keywords: Querying by example; diversified top-k answers

Domains: Databases [cs.DB]

Grégory Smits, Marie-Jeanne Lesot, Olivier Pivert, Marek Reformat. Diversifying top-k Answers in a Query by Example Setting. Flexible Query Answering System, Sep 2023, Palma de Mallorca, Spain. ⟨hal-04122580v2⟩