Large Scale Network-Centric Distributed Systems

25

Computational Graph Analytics for Massive Streaming Data^*

David Ediger, Jason Riedy, David A. Bader, and Henning Meyerhenke

Contents

25.1 Introduction

25.2 STINGER: A General-Purpose Data Structure for Dynamic Graphs

25.2.1 Related Graph Data Structures

25.2.2 The STINGER Data Structure

25.2.3 Finding Parallelism in Streams and Analytics

25.3 Algorithm for Updating Clustering Coefficients

25.3.1 Generic Algorithm

25.3.2 Approximating Clustering Coefficients Using a Bloom Filter

25.4 Tracking Connected Components in Scale-Free Graphs

25.4.1 Problem Structure

25.4.2 The Algorithm in Detail

25.4.3 Discussion

25.5 Implementation

25.5.1 Multithreaded Platforms

25.5.2 The STINGER Data Structure

25.5.3 Multithreaded Implementation of Algorithm 25.1 (Clustering Coefficients)

25.5.4 Multithreaded Implementation of Algorithm 25.2 (Connected Components)

25.6 Experimental Results

25.6.1 Clustering Coefficient Experiments

25.6.1.1 Scalability of the Initial Computation

25.6.1.2 Number of Individual Updates per Second

25.6.2 Connected Components

25.7 Related Work

25.7.1 Streaming Data

25.7.2 Graph Data Structures

25.7.3 Tracking Connected Components

25.8 Conclusion

Acknowledgments

References

25.1 Introduction

The data deluge from a wide range of application domains, from business and finance to computational biology and computer security, requires development of new analysis tools and algorithms to retrieve the information stored within the data. With the Facebook user base containing ...