# Interactive Graph Stream Analytics in Arkouda
## 5 Single Pass Regression Analysis Stream Model
### Edge-Vertex Iterator Based Triangle Counting Algorithm  
We can directly employ existing exact graph algorithms in our sketch because the sketch is also expressed as a graph. Here, we will use a typical graph analysis algorithm--triangle counting--to show how we can develop optimized exact algorithms based on our \(DI\) data structure. To improve the performance of a distributed triangle counting algorithm, two important problems are maintaining load balancing and avoiding remote access or communication as much as possible. In Chapel, the locale type refers to a unit of the machine resources on which the program is running. Locales have the capability to store variables and to run Chapel tasks. In practice, for a standard distributed memory architecture, a single multicore/SMP node is typically considered a locale. Shared memory architectures are typically considered a single locale. In this work, we will develop a multiple-locale exact triangle counting algorithm for distributed memory clusters. For power law graphs, a small number of vertices may have a high degree. So, if we divide the data based on number of vertices, it is easy to cause an unbalanced load. Our method divides the data based on the number of edges. At the same time, our data structure will keep the edges connected with the same vertex together. So, the edge partition method will result in good load balancing and data access locality. However, if each locale directly employs the existing edge iterator [13] on its edges, the reverse edges of the undirected graphs are often not in the same locale. This will cause a new load balancing problem. So, we will first generate the vertices based on the edges distributed to different locales. Then, each locale will employ the vertex iterator to calculate the number of triangles. The combined edge-vertex iterator method is the major innovation for our triangle counting method on distributed systems. When we employ the high level parallel language Chapel to design the parallel exact triangle counting algorithm, there are two additional advantages: (1) Our \(DI\) data structure can work together with the _coforall_ or _forall_ parallel construct of Chapel to exploit the parallelism; (2) We can take advantage of the high level module _Set_ provided by Chapel to implement the parallel set operation easily and efficiently. At a high level, our proposed algorithm takes advantage of the multi-locale feature of Chapel to handle very large graphs in distributed memory. The distributed data are processed at their locales or their local memory. Furthermore, each shared memory compute node can also process their own data in parallel. The following steps are needed to implement the multi-locale exact triangle counting algorithm: (1) The \(DI\) graph data should be distributed evenly onto the distributed memory to balance the load; (2) Each distributed node only counts the triangle including the vertices assigned to the current node; (3) All the triangles calculated by different nodes should be summed together to obtain the exact number of triangles. Our multi-locale exact triangle counting algorithm is described in Algorithm 1. For a given graph sketch partition \(G_{sk}=\langle E_{sk},V_{sk}\rangle\), we will use an array \(subTriSum\) to keep each locale's result (line 2). Here in line 3, we use _coforall_ instead of _forall_ to allow each _loc_ in _Locales_ to execute the following code in parallel so we can fully exploit the distributed computing resources. The code between line 3 and line 17 will be executed in parallel on each locale. Each locale will use a local variable \(triCount\) to store the number of triangles (line 5). Line 6 and line 7 are important for implementing load balancing. Assume edges from \(e_{start}\) to \(e_{end}\) are assigned to the current locale, we can obtain the corresponding vertex ID \(StartVer=SRC[e_{start}]\) and \(EndVer=SRC[e_{end}]\) as the vertices interval that the current locale will handle.