2020/05/16 by Hyokun Yun, Michael Froh, Yun, Hyokun +9
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Machine Learning (cs.LG) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2005.07893
openalex publication_date 2020/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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.