Open Problems:4 - Revision history

Krzysztof Onak at 01:37, 7 March 2013

2013-03-07T01:37:58Z

Krzysztof Onak at 04:55, 16 November 2012

2012-11-16T04:55:49Z

Krzysztof Onak at 02:08, 16 November 2012

2012-11-16T02:08:42Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak at 20:16, 19 September 2012

2012-09-19T20:16:20Z

New page

{{DISPLAYTITLE:Problem 4: Deterministic Summary Structures}}
{{Infobox
|label1 = Proposed by
|data1 = Sumit Ganguly
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/4
}}
Given a stream of elements of the form $(i,\delta)$ where $i\in [n]$ and $\delta\in \{-1,1\}$ define the frequency of an element to be $f_i=\sum_{(i,\delta)} \delta$. We wish to find estimates $\hat{f}_i$ for each $f_i$ such that
\[|\hat{f}_i-f_i|\leq \epsilon L_1\]
where $L_1=\sum_i |f_i|$.
The Count-Min algorithm is a randomized $O(\epsilon^{-1} \log (mn) \log \delta^{-1})$-space algorithm that returns such estimates with probability $1-\delta$ {{cite|CormodeM-05}}. This is nearly optimal as the space lower bound is $O(\epsilon^{-1} \log (m) \log \epsilon n)$ {{cite|Ganguly-06}}.

However, in practice it is desirable to have deterministic algorithms rather than randomized algorithms. Using a deterministic collection of primes {{cite|Muthukrishnan-06}}, Ganguly {{cite|Ganguly-06}} devised a deterministic $O(\phi^{-2}\epsilon^{-1} \log^2(mn))$-space algorithm that returned all items $i$ with $|f_i|\geq \phi L_1$ and no $j$ satisfying $|f_j|\leq (1-\epsilon)\phi L_1$. While this algorithm has the advantage of being deterministic, it uses more space than the Count-Min algorithm. Does there exist a deterministic algorithm that uses the same amount of space as Count-Min? Such an algorithm would lead to space-efficient algorithms for a range of problems including hierarchical heavy hitters, estimating inner product sizes, approximately optimal $B$-bucket histograms etc. Unfortunately, we conjecture that no such algorithm exists. Either an algorithm or lower bound would be very interesting.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Sumit Ganguly

@@ Line 1: / Line 1: @@
 {{Header
- |number=4
+|title=Deterministic Summary Structures
- |title=Deterministic Summary Structures
+|source=kanpur06
- |source=kanpur06
+|who=Sumit Ganguly
 }}
 Given a stream of elements of the form $(i,\delta)$ where $i\in [n]$ and $\delta\in \{-1,1\}$ define the frequency of an element to be $f_i=\sum_{(i,\delta)} \delta$. We wish to find estimates $\hat{f}_i$ for each $f_i$ such that

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