Posted by: atri | April 25, 2008
April 18th talk
(Guest post by Yang Wang)
In my presentation, I showed results from the following three papers.
- On the streaming model augmented with a sorting primitive
- Trading off space for passes in graph streaming problems,
- Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems
The three papers were developed in sequence. In the first paper, the authors proposed using multiple passes with the ability to write onto an intermediate stream and also sort on that stream (as some difficult problems such as graph problems, the data stream model is too weak). Thus this improves the power of the “basic” data stream model. Define a 
class to be the problems that can be solved in polylog passes and polylog (inner memory) space. Then they showed that graph connectivity, max spanning tree and many other problems are in this class. However there do exists problems that are not in the polylog class. In particular, they showed an example that need at least 
passes, and 
space with 
where 
is the input length.
In the second paper, the authors consider the case when we can write to intermediate streams but cannot sort them. This new model is called the 
-stream. They use ideas from parallel algorithms that solve the transitive closure problem to attack the connected component problems and single source shortest paths problem. Later they extended the idea to more general cases in the third paper. They found the following relationship between parallel algorithm and 
-stream. Every processor memory 
time PRAM algorithm can be simulated on the 
-stream with 
passes with space 
. In the next step, they claimed that though the -stream model can be used to simulate PRAM, it is still more powerful that PRAM in that in the -stream model every memory cell in the entire stream can be accessed while in PRAM only a constant number of cells can be accessed. Thus the strategy is to change a PRAM algorithm to a RPRAM algorithm and then to the -stream. In this way, the authors solve many problems such as Maximum independent set and biconnected components.
