AAAI Publications, Workshops at the Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Minimal Interaction Search: Multi-Way Search with Item Categories
Sandilya Bhamidipati, Branislav Kveton, S. Muthukrishnan

Last modified: 2013-06-29


Extensive online collections of content exist, such as music, books, movies, and various others. Search in these collections is typically implemented in two ways, typing attributes of interest into a search box, or progressively navigating through series of menus with item categories to a list of desired items. In this paper, we focus on the latter approach. In particular, we propose a strategy that guides the user to the items of interest in the minimal number of interactions. Therefore, we refer to our technique as minimal interaction search. At each step of the search, we show the user k item categories and ask them to choose the one that matches their preferences, or state that none does. We formalize this problem as multi-way search and propose an algorithm DoubleGreedy that solves the problem efficiently. The item categories in each question can be computed in O(k) time, and any item in the database is found in the worst case in OPTk log(n - 1) e / (e - 1) questions, where n is the total number of items and OPTk is the maximum number of questions asked by the optimal strategy (that uses the smallest number of questions possible in the worst case). We evaluate our method on two datasets of movies and books, and show that the target item can be found very fast.


search;generalized binary search;interactive search

Full Text: PDF