Bookshelf Problem: A Human-in-the-Loop Approach for Data Grouping without Complete Information
Emi Sakurai · iConference 2016 Proceedings · 2016
The problem of dividing a given set of data items into groups in the situation that the given input is not su cient to solve it has a wide range of applications. However, the problem cannot be solved by computers alone. This paper defines the Bookshelf problem to deal with such a problem and discusses how to solve the problem with the help of humans. Intuitively, the Bookshelf problem is as follows. Given a set of books with tags and a book cabinet with N shelves, we need to construct N groups of books s.t. all books in each group share at least one common tag. However, the given tags and their connections to books may not be su cient to make groups, and we have to find the missing tags and connections. This paper proposes a systematic human-in-the-loop method that uses two types of microtasks to solve the problem, and experimentally shows that human intelligence is e ective to avoid the worst-case search.