The Taub Faculty of Computer Science Events and Talks

Balanced Graph Partitioning is a hard problem. Doing it at large scale on graphs of millions of nodes and edges is even harder. Doing it in a distributed way makes the problem even more challenging. And finally, dong it with linear or even sub linear time and space complexity may sound like pushing the limits too far. In this talk I will present our practical approach to this hard problem motivated by the systems we build and describe two algorithms that solve it in two different settings. The first operates on a static graph where nodes arrive one by one in a streaming fashion. The second operates on a dynamic, constantly changing graph with random access to nodes and edges. I will also describe how those algorithms were used in two different large distributed systems that we built: Horton - distributed graph database and Orleans – distributed actor based middleware.

Bio:
Gabriel Kliot obtained his PhD in Computer Science from the Technion in 2009, working on Distributed Systems and Networking. Since then he has been with Microsoft Research realizing his dream of bringing distributed computing to the masses.