# Interactive Graph Stream Analytics in Arkouda
## 1 Introduction  
More and more emerging applications, such as social networks, cybersecurity and bioinformatics, have data that often come in the form of real-time graph streams [1]. Over its lifetime, the sheer volume of a stream could be petabytes, or more like network traffic analysis in the IPv6 network, which has \(2^{128}\) nodes. These applications motivate the challenging problem of designing succinct data structures and real-time algorithms to return approximate solutions. Different stream models [2, 3, 4, 5, 6, 7], which allow access to the data in only one pass (or multi-pass in semi-streaming algorithms), are developed to answer different queries using a significantly reduced sublinear space. The accuracy of such models' approximate solutions is often guaranteed by a pair of user specified parameters, \(\epsilon>0\) and \(0<\delta<1\). This means that the \((1+\epsilon)\) approximation ratio can be achieved with a probability of \((1-\delta)\). This literature provides the theoretical foundation to solve the challenging large scale stream data problem. However, ignoring the hidden constants in the theoretical space and time complexity analysis can cause unacceptable performance problems in real-world applications. When different applications, such as from social, economic and natural domains, have to handle real-time large data streams as routine work, the practical performance for real-world applications becomes an even more important and urgent requirement. At the same time, graph streams need exploratory data analysis (EDA) [8, 9, 10]. Instead of checking results, given a hypothesis, with data, EDA is primarily for seeing what the data can tell us beyond the formal modeling or hypotheses testing task. In this way, EDA tries to maximize the value of data. Popular EDA methods and tools, which often run on laptops or common personal computers, cannot hold terabyte or even larger graph datasets, let alone produce highly efficient analysis results. Arkouda [11, 12] is an EDA framework under early development that brings together the productivity of Python withworld-class high-performance computing. If a graph stream algorithm can be integrated into Arkouda, it means that data scientists can take advantage of both laptop computing and cloud/supercomputing to perform interactive data analysis at scale. In this work, we propose a single pass stream model and develop a typical algorithm for interactive graph stream analytics that can meet practical performance requirements with high accuracy. Furthermore, the proposed model and algorithm will be integrated into Arkouda to support the Python community to handle graph streams efficiently. The major contributions of this paper are as follows:  
1. A succinct Double-Index (DI) data structure is designed to build the sketch of a large graph stream. The DI data structure can support an edge based sparse graph partition to achieve load balance and to achieve \(\mathcal{O}(1)\) time complexity in searching the incidence vertices of a given edge or the adjacency list of a given vertex. 2. A single pass regression analysis stream model is developed to support general graph streams analysis. Our model can map a large graph stream into a much smaller user specified working space to build a general graph stream sketch. Our method can improve the query quality by dividing the sketch into multiple partitions. A general regression method is proposed to generate the approximate solution based on the partial query results from different partitions. 3. A typical graph algorithm--triangle counting [13]--is developed to evaluate the efficiency of the proposed stream regression model. Experimental results using two typical distributions--power law and normal distributions--show that our method can achieve a high accuracy with a very low (4%) mean relative error. 4. All the proposed methods have been integrated into an open-source framework, Arkouda, to evaluate their practical end-to-end performance.