Really Big Data​ Analytics on Graphs with Trillions of Edge

Chargement de la carte…

Date(s) - 21/03/2016

Université Pierre et Marie Curie

Categories No Categories

le Prof. Willy Zwaenepoel, de l’École Polytechnique Fédérale de Lausanne (EPFL) donnera dans le cadre du Colloquium d’informatique de l’UPMC Sorbonne-Universités l’exposé suivant : “Really Big Data​ Analytics on Graphs with Trillions of Edges”.

Cet exposé aura lieu le Mardi 22 mars 2016 à 18h dans l’ Amphi 25 de l’Université Pierre et Marie Curie, campus Jussieu, 4, place Jussieu
Paris Vème (métro Jussieu). Pour s’y rendre:

Un cocktail est prévu à 17h15 en prélude à la conférence, devant l’amphi.


Big graphs occur naturally in many applications, most obviously in social networks, but also in many other areas such as biology and forensics. Current approaches to processing large graphs use either supercomputers or very large clusters. In both cases the entire graph must reside in memory before it can be processed. We are pursuing an alternative approach, processing graphs from secondary storage. While this comes with a performance penalty, it makes analytics on very large graphs feasible on a small number of commodity machines.


We have developed two systems, one for a single machine and one for a cluster of machines. X-Stream, the single machine solution, aims to make all secondary storage access sequential. It uses two techniques to achieve this goal, edge-centric processing and streaming partitions. Chaos, the cluster solution, starts from the observation that there is little benefit to locality when accessing data from secondary storage over a high-speed network. As a result, Chaos spreads graph data uniformly randomly over storage devices, and uses randomized access to achieve I/O balance. Chaos furthermore uses work stealing to achieve computational load balance. By using these techniques, it avoids the need for expensive partitioning during pre-processing, while still achieving good scaling behavior. With Chaos we have been able to process an 8-trillion-edge graph on 32 machines, a new milestone for graph size on a small cluster. I will describe both systems and their performance on a number of benchmarks and in comparison to state-of-the-art alternatives.

This is joint work with Laurent Bindschaedler (EPFL), Jasmina Malicevic (EPFL) and Amitabha Roy (Intel Labs).


zwaenepoelWilly Zwaenepoel received his BS/MS from the University of Gent, Belgium, and his PhD from Stanford University. He is currently a Professor of Computer Science at EPFL. Before he has held appointments as Professor of Computer Science and Electrical Engineering at Rice University, and as Dean of the School of Computer and Communication Sciences at EPFL. His interests are in operating systems and distributed systems. He is a Fellow of the ACM and the IEEE, he has received the IEEE Kanai Award and several best paper awards, and is a member of the Belgian and European Academies. He has also been involved in a number of startups, including BugBuster (acquired by AppDynamics), iMimic (acquired by Ironport/Cisco), Midokura and Nutanix.