TY - GEN
T1 - Minimal interaction search
T2 - 2013 AAAI Workshop
AU - Bhamidipati, Sandilya
AU - Kveton, Branislav
AU - Muthukrishnan, S.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84898871026&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84898871026&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84898871026
SN - 9781577356226
T3 - AAAI Workshop - Technical Report
SP - 9
EP - 15
BT - Intelligent Techniques for Web Personalization and Recommendation - Papers from the 2013 AAAI Workshop, Technical Report
PB - AI Access Foundation
Y2 - 15 July 2013 through 15 July 2013
ER -