Dynamic covering for recommendation systems
Ioannis Antonellis, Anish Das Sarma, Shaddin Dughmi · 2012
In this paper, we identify a fundamental algorithmic problem that we term succinct dynamic covering (SDC), arising in many modern-day web applications, including ad-serving and online recommendation systems such as in eBay, Netflix, and Amazon. Roughly speaking, SDC applies two restrictions to the well-studied Max-Coverage problem [14]: Given an integer k, X={1,2,...,n}and I={S_1,...,S_m}, S_i subseteq X, find |J| subseteq I, such that |J| < k and (union_S_in_J S) is as large as possible. The two restrictions applied by SDC are: (1)Dynamic: At query-time, we are given a query Q subseteq X, and our goal is to find J such that Q bigcap (union_S_J S) is as large as possible; Space-constrained: We don't have enough space to store (and process) the entire input; specifically, we have o(mn), and maybe as little as O((m+n)polylog(mn))space. A solution to SDC maintains a small data structure, and uses this datastructure to answer most dynamic queries with high accuracy. We call such a scheme a Coverage Oracle.