Martin J. Strauss, AT&T Shannon Labs, Florham Park
April 23, 4:30 PM, Rutgers Univ. CORE 431
Abstract.
Consider an array, A, of N values, defined implicitly by a
stream of updates of the form
"add/subtract 3 to/from A[5]".
Our goal is to produce, on demand, a nearly optimal B-bucket
histogram for A (piecewise-constant approximation to A), by
making good choices for bucket boundaries and heights. We
give a data structure that produces a histogram H such that,
with high probability,
||A-H|| <= (1+epsilon)||A-Hopt||,
where Hopt is the best possible B-bucket histogram under L1
or L2 norm ||*||. For each of three costs: total space,
time to process an update, and time to produce a
histogram on demand, our data structure uses resources
polynomial in (B*log(N)/epsilon).
Joint work with Anna C. Gilbert, Sudipto Guha, Piotr Indyk,
Yannis Kotidis, and S. Muthukrishnan.