Open Problems:5 - Revision history

128.30.9.27 at 21:20, 11 November 2014

2014-11-11T21:20:06Z

Krzysztof Onak at 01:38, 7 March 2013

2013-03-07T01:38:28Z

Krzysztof Onak at 04:57, 16 November 2012

2012-11-16T04:57:54Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak at 20:41, 19 September 2012

2012-09-19T20:41:33Z

New page

{{DISPLAYTITLE:Problem 5: Characterizing Sketchable Distances}}
{{Infobox
|label1 = Proposed by
|data1 = Sudipto Guha and Piotr Indyk
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/5
}}
Some of the early successes in developing algorithms for the data stream model
related to estimating $L_p$ norms {{cite|FeigenbaumKSV-02|Indyk-00|AlonMS-99}} and the “Hamming norm”
$L_0$ {{cite|CormodeDIM-03}}.
What other distances, or more generally “measures of dissimilarity,” can be
approximated in the data stream model? Do all sketchable distances essentially
arise as norms, specially, if deletions are allowed? Note that the set
similarity distance (symmetric difference over union) can be
estimated in the streaming model in the absence of deletions {{cite|BroderCFM-00}}.

Recent work provides some preliminary results {{cite|GuhaIM-07}}. Let $f=(f_1,
\ldots, f_n)$ and $g=(g_1, \ldots, g_n)$ be two frequency vectors defined by a
stream in the usual way.
Consider a distance $d(f,g)= \sum_i \phi(f_i,g_i)$ where $\phi:\mathbb N \times
\mathbb N \rightarrow \mathbb R^+$ and $\phi(x,x)=0$.
If there exist $a,b,c\in \mathbb N$ such that
\[ \max \left (
\frac{\phi(a+c,a)}{\phi(b+c,b)} ,
\frac{\phi(a,a+c)}{\phi(b,b+c)}
\right )> \alpha^2\]
then it can be shown that any one-pass $\alpha$-approximation of $d(f,g)$
requires $\Omega(n)$ space where the stream defining $f$ and $g$ has length
$O(n(a+b+c))$. Similar results hold for multiple-pass algorithms and for
probabilistic divergences of the form $d(f,g)= \sum_i \phi(p_i,q_i)$ where
$p_i=f_i/L_1(f)$ and $q_i=g_i/L_1(g)$. These results suggest that for a
distance $d$ to be sketchable, $d(x,y)$ needs to be some function of $x-y$.
In particular, they show that multiplicative approximation of all $f$-divergences and Bregman divergences, such as Kullback-Leibler
and Hellinger, requires $\Omega(n)$ space with $L_1$ and $L_2^2$ being notable exceptions.

← Older revision		Revision as of 21:20, 11 November 2014
Line 30:		Line 30:
	In particular, they show that multiplicative approximation of all $f$-divergences and Bregman divergences, such as Kullback-Leibler		In particular, they show that multiplicative approximation of all $f$-divergences and Bregman divergences, such as Kullback-Leibler
	and Hellinger, requires $\Omega(n)$ space with $L_1$ and $L_2^2$ being notable exceptions.		and Hellinger, requires $\Omega(n)$ space with $L_1$ and $L_2^2$ being notable exceptions.
		+
		+	==Update==
		+	It was shown that for '''norms''' small sketches are equivalent to good embeddings into $\ell_{1 - \varepsilon}$ {{cite\|AndoniKR-14}}.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Sudipto Guha and Piotr Indyk

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 5: Characterizing Sketchable Distances}}
+{{Header
-{{Infobox
+|title=Characterizing Sketchable Distances
-|label1 = Proposed by
+|source=kanpur06
-|data1 = Sudipto Guha and Piotr Indyk
+|who=Sudipto Guha and Piotr Indyk
 }}
 Some of the early successes in developing algorithms for the data stream model

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