Minimal interaction search: Multi-way search with item categories

Sandilya Bhamidipati, Branislav Kveton, S. Muthukrishnan

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


    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 15 2013Jul 15 2013

    Publication series

    NameAAAI Workshop - Technical Report


    Conference2013 AAAI Workshop
    Country/TerritoryUnited States
    CityBellevue, WA

    ASJC Scopus subject areas

    • General Engineering


    Dive into the research topics of 'Minimal interaction search: Multi-way search with item categories'. Together they form a unique fingerprint.

    Cite this