Finding Best Tuple via Error-prone User Interaction

In the literature of the database community, there are a lot of studies about finding a utility function from a user (representing the user's preference), via interaction with the user by asking a number of questions each requiring him/her to compare 2 points for choosing a more preferred point, in order to find the best tuple in the database containing a lot of tuples. In the real world, the user may make mistakes (carelessly), which means that s/he may answer some of the questions wrongly. Unfortunately, existing interaction algorithms may find the undesirable point based on the wrongly learnt utility function because they assume that all answers from the user are 100% correct. In particular, even if the user answers only 1 wrong answer, the output of the existing algorithms may be far away from the users' real need. Motivated by this, in this paper, we propose a new problem of finding the most interesting point via interaction which is robust to possible mistakes made by a user. Besides, we propose (1) an algorithm that asks an asymptotically optimal number of questions when the dataset contains 2 dimensions and (2) two algorithms with provable performance guarantee when the dataset contains d dimensions where d ≥ 2. Experiments on real and synthetic datasets show that our algorithms outperform the existing ones with a higher accuracy with only a small number of questions asked.