# Interactive Graph Stream Analytics in Arkouda
## 4 Succinct Data Structure
### Time and Space Complexity Analysis  
For a given array \(A\), we use \(A[i..j]\) to express the elements in \(A\) from \(A[i]\) to \(A[j]\). \(A[i..j]\) is also called an array section of \(A\). So, for a given vertex with index \(i\), it will have \(NEI[i]\) neighbors and their vertex IDs are from \(DST[STR[i]]\) to \(DST[STR[i]+NEI[i]-1]\). This can be expressed as an array section \(DST[STR[i]\_STR[i]+NEI[i]-1]\) (here we assume the out degree of \(i\) is not 0). For given vertex \(i\), the adjacency list of vertex \(i\) can be easily expressed as \(\langle i,x\rangle\), where \(x\) in \(DST[STR[i]\_STR[i]+NEI[i]-1]\). Based on the \(NEI\) and \(STR\) vertex index arrays, we can find the neighbor vertices or the adjacency list in \(\mathcal{O}(1)\) time complexity. For given edge \(e=\langle i,j\rangle\), it will be easy for us to find its incident vertices \(i\) in array \(SRC[e]\) and \(j\) in array \(DST[e]\) and also in \(\mathcal{O}(1)\) time complexity. Regarding the storage space, if the graph has \(M\) edges and \(N\) vertices, we will need \(2M\) memory to store all the edges. Compared with the dense matrix data structure, which needs \(N^{2}\) memory to store all the edges, this is much smaller. To improve the adjacency list search performance, we use \(2N\) memory to store the \(NEI\) and \(STR\) arrays.  
Figure 2 shows \(M\) sorted edges represented by the \(SRC\) and \(DST\) arrays. Any one of the \(N\) vertices \(n_{k}\) can find its neighbors using \(NEI\) and \(STR\) arrays with \(\mathcal{O}(1)\) time complexity. For example, given edge \(\langle i,j\rangle\), if vertex \(j\)'s starting index in \(SRC\) is 1000, it has three adjacency edges, then such edges can be found starting from index position 1000 in arrays \(SRC\) and \(DST\) using \(NEI\) and \(STR\) arrays directly. This figure shows how the \(NEI\) and \(STR\) arrays can help us locate neighbors and adjacency lists quickly.  
For an undirected graph, an edge \(\langle i,j\rangle\) means that we can also arrive at \(i\) from \(j\). We may use the data structures \(SRC,DST,STR,NEI\) to search the neighbors of \(j\) in SRC. However, this search cannot be performed in \(\mathcal{O}(1)\) time complexity. To improve the search performance, we introduce another four arrays, called reversed arrays, \(SRCr,DSTr,STRr,NEIr\). For any edge \(\langle i,j\rangle\) that has its \(i\) vertex in \(SRC\) and \(j\) vertex in \(DST\), we will have the corresponding reverse edge \(\langle j,i\rangle\) in \(SRCr\) and \(DSTr\), where \(SRCr\) has exactly the same elements as in \(DST\), and \(DSTr\) has exactly the same elements as in \(SRC\). \(SRCr\) and \(DSTr\) are also sorted, and \(NEIr\) and \(STRr\) are the array of the number of neighbors and the array of the starting neighbor index just like the directed graph. So, for a given vertex \(i\) of an undirected graph, the neighbors of vertex \(i\) will include the elements in \(DST[STR[i]\_STR[i]+NEI[i]-1]\) and the elements in \(DST[STR[i]\_STR[i]+NEI[i]-1]\). The adjacency list of the vertex \(i\) should be \(\langle i,x\rangle\), where \(x\) in \(DST[STR[i]\_STR[i]+NEI[i]-1]\) or \(\langle i,x\rangle\), where \(x\) in \(DSTr[STRr[i]\_STRr[i]+NEI[i]-1]\).  
Given a directed graph with \(M\) edges and \(N\) vertices, our data structure will need \(2(M+N)\) integer (64 bits) storage or \(\frac{M+N}{4}\) bytes. For an undirected graph, we will need twice the storage of a directed graph. For weighted vertices and weighted edges, additional \(N\), \(M\) integer storage will be needed, respectively.