  Partitioning an input graph over a set of workers is a complex operation.
Objectives are twofold: split the work evenly, so that every worker gets an
equal share, and minimize edge cut to achieve a good work locality (i.e.
workers can work independently). Partitioning a graph accessible from memory is
a notorious NP-complete problem. Motivated by the regain of interest for the
stream processing paradigm (where nodes and edges arrive as a flow to the
datacenter), we propose in this paper a stream-enabled graph partitioning
system that constantly seeks an optimum between those two objectives. We first
expose the hardness of partitioning using classic and static methods; we then
exhibit the cut versus load balancing tradeoff, from an application point of
view. With this tradeoff in mind, our approach translates the online
partitioning problem into a standard optimization problem. A greedy algorithm
handles the stream of incoming graph updates while optimizations are triggered
on demand to improve upon the greedy decisions. Using simulations, we show that
this approach is very efficient, turning a basic optimization strategy such as
hill climbing into an online partitioning solution that compares favorably to
literature's recent stream partitioning solutions.
