Approximately optimal facet value selection

• We define a measure of user effort when searching in a faceted search system.
• We define two models for user drill-down behavior in faceted search systems.
• We show efficient approximation algorithms for minimizing search effort in our models.
• We show our algorithms reduce (simulated) user effort more than existing baselines.
• Our algorithms outperform baselines even when modeling assumptions do not hold.

Multifaceted search is a popular interaction paradigm for discovery and mining applications that allows users to digest, analyze and navigate through multidimensional data. A crucial aspect of faceted search applications is selecting the list of facet values to display to the user following each query. We call this the facet value selection problem.When refining a query by drilling down into a facet value, documents that are associated with that facet value are promoted in the rankings. We formulate facet value selection as an optimization problem aiming to maximize the rank promotion of certain documents. As the optimization problem is NP-Hard, we propose an approximation algorithm for selecting an approximately optimal set of facet values per query.We conducted experiments over hundreds of queries and search results of a large commercial search engine, comparing two flavors of our algorithm to facet value selection algorithms appearing in the literature. The results show that our algorithm significantly outperforms those baseline schemes.