Fast statistical relationship discovery in massive monitoring data

Today´s network systems are extensively instrumented for collecting a wealth of monitoring data. Statistical techniques like regression analysis can be applied to uncover rich relationships (e.g., correlation, causality, independence) between the measurement data which are further utilized for systems management tasks including fault diagnosis, configuration management, performance analysis, etc. However, one problem during this information mining process comes from the heavy computation overhead in statistical relationship discovery. In this paper, we propose a fast indexing technique to alleviate this problem by helping guide the discovery process in an optimal order. We model the optimal discovery process as the classic vertex cover problem in graph theory which is NP-complete. We use the heuristic of greedy vertex selection based on vertex degree and propose two simple algorithms for generating an estimated ranking (indexing) on the vertices (i.e., measurement points) based on the edges (the existing statistical relationships) incident to them. The two algorithms are based on random sampling and we analyze their output accuracy as a function of the sampling trials. On data traces from an operational 3G mobile network, our indexing technique performed close to the optimal solution (e.g., no more than 10% discovery time) and significantly better than random discovery (e.g., 70% less discovery time) on finding a specified percentage (e.g., 90%) of the existing relationships.