Name
Abstract | ||
|---|---|---|
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.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3299869.3300068 | Proceedings of the 2019 International Conference on Management of Data |
Keywords | Field | DocType |
data analytics, regret minimization, user interaction | Data mining,Data analysis,Regret minimization,Computer science,Artificial intelligence,Machine learning | Conference |
ISSN | ISBN | Citations |
0730-8078 | 978-1-4503-5643-5 | 2 |
PageRank | References | Authors |
0.36 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Xie | 1 | 20 | 7.20 |
| Raymond Chi-Wing Wong | 2 | 1305 | 85.98 |
| Ashwin Lall | 3 | 215 | 15.31 |