Strongly Truthful Interactive Regret Minimization

Autor: Min Xie, Ashwin Lall, Raymond Chi-Wing Wong
Rok vydání: 2019
Předmět:
Zdroj: SIGMOD Conference
DOI: 10.1145/3299869.3300068
Popis: When faced with a database containing millions of tuples, an end user might be only interested in finding his/her (close to) favorite tuple in the database. Recently, a regret minimization query was proposed to obtain a small subset from the database that fits the user's needs, which are expressed through an unknown utility function. Specifically, it minimizes the "regret'' level of a user, which we quantify as the regret ratio if s/he gets the best tuple in the selected subset but not the best tuple among all tuples in the database. We study how to enhance the regret minimization query with user interactions : when presented with a small number of tuples (which can be artificial tuples or true tuples inside the database), a user is asked to indicate the tuple s/he favors the most among them. In particular, we are also interested in the special case of determining the favorite tuple for a user in the entire database with a small amount of interaction, measured by the number of questions we ask the user. Different from the previous work which displays artificial tuples to users, we achieve a stronger result in this paper by always displaying true tuples in the database. Specifically, we present a generic framework for interactive regret minimization, under which we propose algorithms that ask an asymptotically optimal number of questions in 2-dimensional spaces and algorithms with provable performance guarantees in d-dimensional spaces ($d \geq 2$) where each dimension corresponds to a description of a tuple. Experiments on real and synthetic datasets showed that our algorithms outperform the existing one by locating the favorite tuple and guaranteeing a small regret ratiowith much fewer questions.
Databáze: OpenAIRE
Externí odkaz: