Taming graph dynamics at scale
Félix Cuadrado, Queen Mary, University of London
Large-scale graph processing systems are predominantly based on partitioning and distributing the graph across computing nodes. This approach provides substantial scalability, while making network communications a performance bottleneck. The majority of graph processing systems are designed for processing static snapshots, but real-world graphs can be highly dynamic, with vertices and edges being added and removed. Supporting dynamic graphs brings additional challenges, with system performance degrading as the structure of the graph keeps changing. This talk presents a BSP (Bulk Synchronous Parallel) dynamic graph processing system that updates the graph and adapts partitioning while performing computations. The system uses a highly scalable adaptive partitioning strategy based on iterative vertex migrations. The talk shows through real-world scenarios how adapting graph partitioning reduces execution time by over 50% when compared to commonly used hash partitioning. To conclude the talk, I argue that existing graph computation models are inherently limited for tracking graph changes over time (as they only consider snapshots), and discuss the challenges for enabling a different type of system where both temporal and structural elements of a graph can be evaluated.
About the speaker
Dr Félix Cuadrado is a Lecturer (Assistant Professor) in the School of Electronic Engineering and Computer Science, QMUL, from 2011. He obtained his PhD in 2009 from UPM (Universidad Politecnica de Madrid), for which he received a prize for the best PhD thesis in 2010 by the Spanish Association of Telecommunications Engineering. His research interests include large-scale distributed systems, dynamic graph processing, cloud computing, and network support for distributed applications.
Date & Time
Thursday, May 14, 2015 - 14:00