Defragmenting Social Networks
MetadataShow full metadata
The scale of Online Social Networks, like Facebook, requires splitting users across many servers; unfortunately, this can spread one user's friends across hundreds of servers, increasing both the latency of retrieving all friends' activity and the cost of operation. We investigate two related graph partitioning problems, Minimum Edge Cut and the more recent problem of Min_Replica. We compare existing solutions and find that hybridizing them can reduce latency and lower operational cost. Specifically, combining an event-driven local repartitioning algorithm and a periodic global repartitioning algorithm can yield significant benefits, similar to placing a file on disk greedily and periodically improving placement by defragmenting.