Minimal interaction search: Multi-way search with item categories

Sandilya Bhamidipati, Branislav Kveton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationIntelligent Techniques for Web Personalization and Recommendation - Papers from the 2013 AAAI Workshop, Technical Report
PublisherAI Access Foundation
Number of pages7
ISBN (Print)9781577356226
StatePublished - 2013
Event2013 AAAI Workshop - Bellevue, WA, United States
Duration: Jul 14 2013Jul 15 2013

Publication series

NameAAAI Workshop - Technical Report


Other2013 AAAI Workshop
Country/TerritoryUnited States
CityBellevue, WA

ASJC Scopus subject areas

  • Engineering(all)

Cite this