  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 in eBay and Netflix.
Roughly speaking, SDC applies two restrictions to the well-studied Max-Coverage
problem: Given an integer k, X={1,2,...,n} and I={S_1, ..., S_m}, S_i a subset
of X, find a subset J of I, such that |J| <= k and the union of S in J is as
large as possible. The two restrictions applied by SDC are: (1) Dynamic: At
query-time, we are given a query Q, a subset of X, and our goal is to find J
such that the intersection of Q with the union of S in J is as large as
possible; (2) 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. The goal of SDC is to maintain a small data
structure so as to answer most dynamic queries with high accuracy. We call such
a scheme a Coverage Oracle.
  We present algorithms and complexity results for coverage oracles. We present
deterministic and probabilistic near-tight upper and lower bounds on the
approximation ratio of SDC as a function of the amount of space available to
the oracle. Our lower bound results show that to obtain constant-factor
approximations we need Omega(mn) space. Fortunately, our upper bounds present
an explicit tradeoff between space and approximation ratio, allowing us to
determine the amount of space needed to guarantee certain accuracy.
