Computer Science – Data Structures and Algorithms
Scientific paper
2009-12-12
Computer Science
Data Structures and Algorithms
Scientific paper
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.
Antonellis Ioannis
Dughmi Shaddin
Sarma Anish Das
No associations
LandOfFree
Succinct Coverage Oracles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Succinct Coverage Oracles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct Coverage Oracles will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-533106