<p>The first paper to prove bounds for more than 1 pass was my paper with Jayram and Amit from SODA'08. Then there is the paper that Warren mentioned, which improves the bounds by a cleaner proof.</p>

<p>In short, we understand the dependence if you allow constants in front of the number of passes. Of course, these constants are in the exponent, so you can ask for a precise understanding. My main complaint is that the model of multipass streaming is not all that well motivated.</p>

<p>The more intriguing question is whether we can prove a branching program lower bound. Can it be that even for a bounded space algorithm that can access memory as it pleases, the best strategy is to just do multipass streaming?</p>

<p>The answer appears to be affirmative, and we have some partial progress towards proving it.</p>

CC BY-SA 2.5
2010-10-22T10:34:55.687Z
I think multipass streaming *is* a natural model in following kind of experiments: You use randomised sampling to do statistical testing (e.g., permutation testing). You run billions of experiments; each experiment gets random numbers from a PRNG and produces some output values. Then you want to compute medians, histograms, etc., of these values. You don't have efficient random access to your stream of outputs and you don't have memory to store everything. However, you *can* re-play the stream; just reset your PRNG with the same seed and re-run your algorithm.
Jukka Suomela
CC BY-SA 2.5
2010-10-22T14:16:32.790Z
We can all agree that the best is having upper bounds in the multipass streaming model and matching lower bounds in for some relevant family of branching programs.
MassimoLauria
CC BY-SA 2.5
2010-10-22T03:45:23.200Z
2010-10-22T03:45:23.200Z
Mihai
<p>Try this paper by Chan in a recent SODA: <a href="http://portal.acm.org/citation.cfm?id=1721842&amp;dl=ACM">http://portal.acm.org/citation.cfm?id=1721842&amp;dl=ACM</a> .</p>

<p>A quick Google search also found the following paper that looks possibly relevant, but I haven't read it: <a href="http://portal.acm.org/citation.cfm?id=1374470">http://portal.acm.org/citation.cfm?id=1374470</a> .</p>

CC BY-SA 2.5
2010-10-21T19:10:27.503Z
Thank you, the second paper seems to give a partial answer to my question.  Such answer is not present in earlier papers I was aware of.
MassimoLauria
CC BY-SA 2.5
2010-10-21T18:28:48.920Z
2010-10-21T18:28:48.920Z
Warren Schudy
<p>In a classic paper <a href="http://dx.doi.org/10.1016/0304-3975(80)90061-4">Munro and Paterson</a> study the problem of how much storage is required for an algorithm to find the median in a randomly sorted array.  In particular they focus on the following model:</p>

<p>the input is read from left to right for a number P of times.</p>

<p>It is shown that $O(n^{\frac{1}{2P}})$ memory cells are sufficient, but the corresponding lower bound is only known for P=1.  I haven't seen any result for P>1.  Is anyone aware of such lower bounds?  </p>

<p>Notice that the main difficulty here is that at the second pass the input is not randomly ordered anymore.</p>

<ds.algorithms><space-bounded><data-streams>
Storage requirements for median selection (two passes algorithms)
MassimoLauria
# Storage requirements for median selection (two passes algorithms)

(Asked by: username_0 on 2010-10-21)

In a classic paper [Munro and Paterson](http://dx.doi.org/10.1016/0304-3975(80)90061-4) study the problem of how much storage is required for an algorithm to find the median in a randomly sorted array. In particular they focus on the following model:

the input is read from left to right for a number P of times.

It is shown that $O(n^{\frac{1}{2P}})$ memory cells are sufficient, but the corresponding lower bound is only known for P=1. I haven't seen any result for P>1. Is anyone aware of such lower bounds?

Notice that the main difficulty here is that at the second pass the input is not randomly ordered anymore.

**Tags:** ds.algorithms, space-bounded, data-streams


---

## 2 answers

### Answer by username_3 on 2010-10-21. Score: 14 | Accepted answer

Try this paper by Chan in a recent SODA: <http://portal.acm.org/citation.cfm?id=1721842&dl=ACM> .

A quick Google search also found the following paper that looks possibly relevant, but I haven't read it: <http://portal.acm.org/citation.cfm?id=1374470> .

> **Comments:**
> **username_0**: Thank you, the second paper seems to give a partial answer to my question.  Such answer is not present in earlier papers I was aware of.  

---

### Answer by username_1 on 2010-10-22. Score: 18

The first paper to prove bounds for more than 1 pass was my paper with Jayram and Amit from SODA'08. Then there is the paper that Warren mentioned, which improves the bounds by a cleaner proof.

In short, we understand the dependence if you allow constants in front of the number of passes. Of course, these constants are in the exponent, so you can ask for a precise understanding. My main complaint is that the model of multipass streaming is not all that well motivated.

The more intriguing question is whether we can prove a branching program lower bound. Can it be that even for a bounded space algorithm that can access memory as it pleases, the best strategy is to just do multipass streaming?

The answer appears to be affirmative, and we have some partial progress towards proving it.

> **Comments:**
> **username_2**: I think multipass streaming *is* a natural model in following kind of experiments: You use randomised sampling to do statistical testing (e.g., permutation testing). You run billions of experiments; each experiment gets random numbers from a PRNG and produces some output values. Then you want to compute medians, histograms, etc., of these values. You don't have efficient random access to your stream of outputs and you don't have memory to store everything. However, you *can* re-play the stream; just reset your PRNG with the same seed and re-run your algorithm.  
> **username_0**: We can all agree that the best is having upper bounds in the multipass streaming model and matching lower bounds in for some relevant family of branching programs.  

---

