Tiering as a Stochastic Submodular Optimization Problem
This work addresses the efficiency and generalization issues in tiering for information retrieval systems, offering a novel optimization approach that could improve system performance for users, though it appears incremental as it builds on existing methodologies with a new formulation.
The paper tackled the problem of selecting documents for high-priority tiers in large-scale information retrieval systems, which previously relied on static query sets and generalized poorly to future traffic, by formulating it as a stochastic submodular optimization problem and developing efficient algorithms to maximize generalization performance.
Tiering is an essential technique for building large-scale information retrieval systems. While the selection of documents for high priority tiers critically impacts the efficiency of tiering, past work focuses on optimizing it with respect to a static set of queries in the history, and generalizes poorly to the future traffic. Instead, we formulate the optimal tiering as a stochastic optimization problem, and follow the methodology of regularized empirical risk minimization to maximize the \emph{generalization performance} of the system. We also show that the optimization problem can be cast as a stochastic submodular optimization problem with a submodular knapsack constraint, and we develop efficient optimization algorithms by leveraging this connection.