Interactive Search with Mixed Attributes

The problem of extracting the user's favorite tuple from a large dataset attracts a lot of attention in the database community. Existing studies attempt to search for the target tuple with the help of user interaction. Specifically, they ask a user several questions, each of which consists of two tuples and asks the user to indicate which one s/he prefers. Based on the feedback, the user preference is learned implicitly and the target tuple w.r.t. the learned preference is returned. However, they mainly consider datasets with numerical attributes (e.g., price). In practice, tuples can also be described by categorical attributes (e.g., color), where there is no trivial order in the attribute values. Even if the categorical attributes can be reduced into numerical ones using conventional strategies (e.g., one-hot encoding), existing methods do not work well. In this paper, we study how to find the user's favorite tuple from datasets with mixed attributes (including both numerical and categorical attributes) by interacting with the user.

We study our problem progressively. Firstly, we inquiry a special case in which tuples are only described by categorical attributes. We present algorithm SP-Tree that asks an asymptotically optimal number of questions. Secondly, we explore the general case in which tuples are described by numerical and categorical attributes. We propose algorithm GE-Graph that performs well theoretically and empirically. Experiments are conducted on synthetic and real datasets. The results show that our algorithms outperform existing ones on both the execution time and the number of questions asked. Under typical settings, we reduce dozens of questions asked and speed up by several orders of magnitude.