Open Problems:3 - Revision history

Krzysztof Onak at 01:37, 7 March 2013

2013-03-07T01:37:47Z

Krzysztof Onak at 04:55, 16 November 2012

2012-11-16T04:55:18Z

Krzysztof Onak at 02:07, 16 November 2012

2012-11-16T02:07:53Z

Krzysztof Onak: 1 revision

2012-11-08T05:36:46Z

1 revision

Krzysztof Onak at 20:06, 19 September 2012

2012-09-19T20:06:47Z

New page

{{DISPLAYTITLE:Problem 3: $L_\infty$ estimation}}
{{Infobox
|label1 = Proposed by
|data1 = Graham Cormode
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/3
}}
One of the earliest results shown in data streaming is that approximating
$L_ \infty$ of a stream of values requires space proportional to the
dimensionality of the stream.
The hard case used to prove this is when most items in the stream have
frequency of occurrence
1, and approximating $L_ \infty $ is equivalent to testing whether any item
has frequency two or higher.
However, a variation of this problem is routinely studied under the name
“heavy hitters.” Here, the lower bound is avoided by asking to find all items whose
frequencies are greater than some fixed fraction $\phi$ of the total
stream length, and tolerating approximation error $\epsilon$.
Bounds are then provided which are polynomial in $(1/\phi)$ or $(1/\epsilon)$.
A side effect of these algorithms is to estimate $L_ \infty $ of the stream
with error proportional to $\epsilon$ times the $L_1$ or $L_2$ norm of the stream.
Let the stream consist of items specified in $\log m$ bits.
For insert only streams, the best space bound is $O(\epsilon^{-1}(\log m + \log L_1)
)$ {{cite|MisraG-82|MetwallyAA-05}}, for computing
on the difference between two streams the bounds are
$O(\epsilon^{-1}\log m (\log m + \log L_1))$ {{cite|CormodeM-05a}}.
These algorithms approximate the $L_\infty$ distance in the sense above,
but additionally identify a set of items which contribute significantly to
the distance.

The open question is whether it is possible to approximate $L_\infty $ with
additive error in terms of $\epsilon$ times $L_1$ or $L_2$ with less space. In
particular, is it possible to reduce the dependency on $m$, since this is
not needed in the output?
One possible direction is to analyze data structures such as the Count-Min
sketch, from which items frequencies can be estimated and in which $m$ does
not occur in the (word) space
complexity {{cite|CormodeM-05}}.<ref>Formally, $\log m$ does affect the bit space complexity in two places:
the data structure consists of $O(\log 1/\delta)$ hash functions whose
specification requires $O(\log m)$ bits; and $O(\epsilon^{-1} \log 1/\delta)$
counters which in the worst case may count to the $L_1$ norm of the whole
stream—this may perhaps be addressed by using approximate counters.</ref>

==Notes==
<references />

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Graham Cormode

@@ Line 1: / Line 1: @@
 {{Header
- |number=3
+|title=$L_\infty$ estimation
- |title=$L_\infty$ estimation
+|source=kanpur06
- |source=kanpur06
+|who=Graham Cormode
 }}
 One of the earliest results shown in data streaming is that approximating

← Older revision	Revision as of 05:36, 8 November 2012
(No difference)