Dynamic Covering for Recommendation Systems
Venue
CIKM (2012)
Publication Year
2012
Authors
Ioannis Antonellis, Anish Das Sarma, Shaddin Dughmi
BibTeX
Abstract
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.
