Interactive Learning for Diverse Top-k Set

The top-k query is a representative multi-criteria decision-making operator that assists users in finding the best k tuples based on their criteria. However, it has certain limitations in the query process and the final output. First, the query process requires users to specify their criteria explicitly and accurately in advance, which may be difficult for some users. Second, the final output often lacks diversity, which potentially leads to user dissatisfaction. To address these limitations, in this paper, we propose an enhanced top-k query by incorporating an interactive learning framework and a diversity mechanism, expecting to return a diverse output that aligns with the user's criterion, even if the criterion is not specified in advance.

We study our problem progressively. Initially, we examine a special case where tuples are described by two scoring attributes. We present the TDIA algorithm that is asymptotically optimal regarding the user effort needed for interaction. Then, we move on to the general case where tuples are described by multiple scoring attributes. We propose the HDIA algorithm which is asymptotically optimal w.r.t. the number of questions asked in expectation. Experiments were conducted on synthetic and real datasets. The results show that our algorithms can return a diverse output while requiring less user effort than existing ones.