In the graph semi-streaming model [1]}, [2]} (sometimes just called the graph streaming model), an algorithm is presented with a stream \(S\)  of updates (each an edge insertion or deletion) where the length of the stream is \(N\) .
Stream \(S\)  defines an input graph \(\mathcal {G}= (\mathcal {V},\mathcal {E})\)  with \(V= |\mathcal {V}|\)  and \(E= |\mathcal {E}|\) . The challenge in this model is to compute (perhaps approximately) some property of \(\mathcal {G}\)  given a single pass over \(S\)  and at most \(O(V\mathrm {polylog}(V))\)  words of memory.
Each update has the form \(((u,v), \Delta )\)  where \(u,v \in \mathcal {E}, u \ne v\)  and \(\Delta \in \lbrace -1,1\rbrace \)  where 1 indicates an edge insertion and \(-1\)  indicates an edge deletion. Let \(s_i\)  denote the \(i\) th element of \(S\) , and let \(S_i\)  denote the first \(i\)  elements of \(S\) .
Let \(\mathcal {E}_i\)  be the edge set defined by \(S_i\) , i.e., those edges which have been inserted and not subsequently deleted by step \(i\) . The stream may only insert edge \(e\)  at time \(i\)  if \(e \notin \mathcal {E}_{i-1}\) , and may only delete edge \(e\)  at time \(i\)  if \(e \in \mathcal {E}_{i-1}\) .
