<p>this research appears to be active in a more applied sense than the theoretical one you mention (ie oracles etc) with "data streaming" algorithms which attempt to work with very large data through "sliding windows", with many graph algorithms considered, but it is indeed relatively new/recent, fitting in with <a href="http://en.wikipedia.org/wiki/Big_data" rel="nofollow">"big data"</a> research directions.</p>

<ul>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.2582" rel="nofollow">Tradeoff Algorithms in Streaming Models</a>, Andrea Ribichini, p7:</li>
</ul>

<blockquote>
  <p>We have devised several algorithms for fundamental graph problems in the
  W-Stream model, including connected components, minimum spanning tree,
  biconnected components and single-source shortest paths. To the best of
  our knowledge, our algorithms are the first to allow effective space/passes
  tradeoffs for such problems in a data streaming setting.</p>
</blockquote>

<p>this ref includes other refs/surveys which might be helpful.</p>

<blockquote>
  <p>Despite the heavy restrictions imposed by the [classical streaming] model, major success has
  been achieved for several data sketching and statistics problems, for which
  a constant number of passes and polylogarithmic working memory have
  been proven enough to find approximate solutions (see [4, 16, 17] and the
  extensive bibliographies in [7, 29]).</p>
</blockquote>

<p>also: </p>

<ul>
<li><a href="http://dl.acm.org/citation.cfm?id=1644021" rel="nofollow">Trading off space for passes in graph streaming problems</a>
Camil Demetrescu,
Irene Finocchi,
Andrea Ribichini</li>
</ul>

CC BY-SA 3.0
2013-03-07T18:18:16.213Z
2013-03-07T18:18:16.213Z
vzn
<p>In their paper <a href="http://kaashoek.org/~petar/behind/oracles-zwick-stoc01.pdf">Approximate Distance Oracles</a>, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(2k-1)$-approximate distance between any pair of  vertices in the graph.</p>

<p>At a fundamental level, this construction achieves a space-approximation trade-off --- one can reduce the space requirements at the cost of a lower "quality" of the solution.</p>

<blockquote>
  <p>What other graph problems exhibit such a trade-off between space and approximation?</p>
</blockquote>

<p>I am interested in the case of both static and dynamic, weighted and unweighted, undirected and directed graphs.</p>

<p>Thanks.</p>

CC BY-SA 3.0
2013-03-04T07:46:59.010Z
Trade-off usually means a lower bound: if you make one thing smaller, then the other needs to be larger.  Do you want an upper bound result (as in your example), or a lower bound result?
Yoshio Okamoto
CC BY-SA 3.0
2013-03-04T09:07:48.707Z
@YoshioOkamoto - An upper bound can "achieve" a trade-off --- an upper bound may not mean that the trade-off is essential (which is a lower bound question), but it can achieve one. Is that right? Irrespective of that, I am interested in both lower bounds and upper bounds.
Rachit
<ds.algorithms><graph-theory><approximation-algorithms><space-complexity>
Space-approximation Trade-off
Rachit
# Space-approximation Trade-off

(Asked by: username_0 on 2013-03-01)

In their paper [Approximate Distance Oracles](http://kaashoek.org/~petar/behind/oracles-zwick-stoc01.pdf), Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(2k-1)$-approximate distance between any pair of vertices in the graph.

At a fundamental level, this construction achieves a space-approximation trade-off --- one can reduce the space requirements at the cost of a lower "quality" of the solution.

> What other graph problems exhibit such a trade-off between space and approximation?

I am interested in the case of both static and dynamic, weighted and unweighted, undirected and directed graphs.

Thanks.

**Tags:** ds.algorithms, graph-theory, approximation-algorithms, space-complexity

> **Comments:**
> **username_1**: Trade-off usually means a lower bound: if you make one thing smaller, then the other needs to be larger.  Do you want an upper bound result (as in your example), or a lower bound result?  
> **username_0**: @YoshioOkamoto - An upper bound can "achieve" a trade-off --- an upper bound may not mean that the trade-off is essential (which is a lower bound question), but it can achieve one. Is that right? Irrespective of that, I am interested in both lower bounds and upper bounds.  

---

## 1 answers

### Answer by username_2 on 2013-03-07. Score: -2

this research appears to be active in a more applied sense than the theoretical one you mention (ie oracles etc) with "data streaming" algorithms which attempt to work with very large data through "sliding windows", with many graph algorithms considered, but it is indeed relatively new/recent, fitting in with ["big data"](http://en.wikipedia.org/wiki/Big_data) research directions.

* [Tradeoff Algorithms in Streaming Models](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.2582), Andrea Ribichini, p7:

> We have devised several algorithms for fundamental graph problems in the
> W-Stream model, including connected components, minimum spanning tree,
> biconnected components and single-source shortest paths. To the best of
> our knowledge, our algorithms are the first to allow effective space/passes
> tradeoffs for such problems in a data streaming setting.

this ref includes other refs/surveys which might be helpful.

> Despite the heavy restrictions imposed by the [classical streaming] model, major success has
> been achieved for several data sketching and statistics problems, for which
> a constant number of passes and polylogarithmic working memory have
> been proven enough to find approximate solutions (see [4, 16, 17] and the
> extensive bibliographies in [7, 29]).

also:

* [Trading off space for passes in graph streaming problems](http://dl.acm.org/citation.cfm?id=1644021)
  Camil Demetrescu,
  Irene Finocchi,
  Andrea Ribichini


---

