# Interactive Graph Stream Analytics in Arkouda
## 5 Single Pass Regression Analysis Stream Model
### Building the Sketch as a Multi-Partition Graph  
#### 5.1.1 Sliding Window Stream  
We first describe our method when the stream comes from a sliding window, which means that only the last \(M\) edges falling into the given time window will be considered.  
We define the shrinking factor \(SF\) (a positive integer) to constrain the space allocation of a stream sketch. This means that the size of the edges and vertices of the graph sketch will be \(\frac{1}{SF}\) of the original graph. The existing research on sketch building [7] shows that multiple pairwise independent hash function [4] methods can often generate better estimation results because they can reduce the probability of hash collisions. In our solution, we sample at different parts of the given sliding window instead of the complete stream and then map the sampled edges into multiple (here three) independent partitions to completely avoid collisions. We name the three partitions Head, Mid, and Tail partitions or sub-sketches, respectively. Each partition will be assigned with \(\frac{1}{3 SF}\) space of the original graph.  
Since we divide the sketch into three independent partitions, we select a very simple hash function. For a given sliding window, we let the total number of edges and vertices in this window be \(M\) and \(N\). Then, the size of each partition will have \(Partition_{M}=\frac{M}{3 SF}\) edges and \(Partition_{N}=\frac{N}{3 SF}\) vertices. For any edge \(e=\langle i,j\rangle\) from the original graph, we will map the edge ID \(e\) to \(mod(e,Partition_{M})\). At the same time, its two vertices \(i\) and \(j\) will be mapped to \(mod(i,Partition_{N})\) and \(mod(j,Partition_{N})\). If \(e<\frac{M}{3}\), then we will map \(e=\langle i,j\rangle\) to the Head partition. If \(e\geq\frac{2M}{3}\), we will map \(e=\langle i,j\rangle\) to the Tail partition. Otherwise, we will map \(e=\langle i,j\rangle\) to the Mid partition.  
Figure 4 is an example that shows how we map, completely, 3,000,000 edges in a given sliding window into a sketch with three partitions. The edges from 1,000,000 to 1999,999 are mapped to the Head partition p0 that has 1000 edges. The edges from 2,000,000 to 2,999,999 are mapped to the Mid partition p1 and the edges from 3,000,000 to 3,999,999 are mapped to the Tail partition p2. Each partition is expressed as a graph.  
Figure 4: Mapping a graph stream into a multi-partition sketch.  
After the three smaller partitions are built, we sort the edges and create the \(DI\) data structure to store the partition graphs.  
We map different parts of a stream into corresponding sub-sketches and this is very different from the existing sketch building methods. They map the same stream into different sketches with independent pairwise hash functions so each sketch is an independent summarization of the stream. However, in our method, one sub-sketch can only stand for a part of the stream and we use different sub-sketches to capture the different local features in a stream. Our regression model (see Section 5.3) will be responsible for generating the final approximate solution.  
More partitions will help to capture more local features of a stream. However, we aim for a regression model that is as simple as possible. Too many partitions will make our regression model have more variables and become complicated. We select three as the default number of partitions because this can achieve sufficient accuracy based on our experimental results. Of course, for some special cases, we may choose more partitions but use the same proposed framework.