Space-Constrained Dynamic Covering

Abstract

In this paper, we identify a fundamental algorithmic problem that we term space-constrained dynamic covering (SCDC), arising in many modern-day web applications, including ad-serving and online recommendation systems in eBay and Netflix. Roughly speaking, SCDC applies two restrictions to the well-studied Max-Coverage problem: Given an integer $k$, $\X=\{1,2,\ldots,n\}$ and $\I=\{S_1, \ldots, S_m\}$, $S_i\subseteq \X$, find $\J\subseteq \I$, such that $|\J|\leq k$ and $ (\union_{S\in \J} S)$ is as large as possible. The two restrictions applied by SCDC are: (1) Dynamic: At query-time, we are given a \emph{query} $Q\subseteq \X$, and our goal is to find $\J$ such that $Q\bigcap (\union_{S\in \J} S)$ 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)$, sometimes even as little as $O((m+n)polylog(mn))$ space. The goal of SCDC is to maintain a small data structure so as to answer most dynamic queries with high accuracy. We present algorithms and complexity results for SCDC. We present deterministic and probabilistic near-tight upper and lower bounds on the approximation ratio of SCDC as a function of the amount of space available. 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. Finally, we study a practical subclass of SCDC allowing more accurate solutions despite limited storage space.