Sans: Streaming Anonymized Network Sensing

Large-scale network sensing is an important task with applications in various domains. Recently, researchers have proposed a network sensing algorithm based on GraphBLAS, which divides the input data into multiple disjoint blocks and constructs a graph for each block containing hypersparse network sensing data. However, this block-based approach may miss some anomalies between two consecutive blocks. In this paper, we aim to address this issue by developing a streaming anonymized network sensing systems, Sans. Specifically, Sans combines the advantages of directly maintaining edges in the hashtable and maintaining the vertices as well as the adjacent edges in the hashtable of list to develop a dynamic, efficient, and compressed data structure for hypersparse network sensing data. Furthermore, we develop an incremental calibration algorithm based on gradient descent by leveraging the previous analysis parameters. We also propose a parallel version of the algorithm, which supports shared-memory lock-based and distributed-memory lock-free designs. We conduct extensive experiments to evaluate the performance of the proposed streaming network sensing algorithm. The results demonstrate that Sans outperforms the static CSR (GraphBLAS) approach by one million times.