به نام خدا

Title: Sharding Social Networks

Authors: Quang Duong, Sharad Goel, Jake Hofman, Sergei Vassilvitskii

Abstract: Online social networking platforms regularly support hun-dreds of millions of users, who in aggregate generate sub-stantially more data than can be stored on any single phys-ical server. As such, user data are distributed, or sharded,across many machines. A key requirement in this setting israpid retrieval not only of a given user_s information, butalso of all data associated with his or her social contacts,suggesting that one should consider the topology of the so-cial network in selecting a sharding policy. In this paperwe formalize the problem of efficiently sharding large so-cial network databases, and evaluate several sharding strate-gies, both analytically and empirically. We find that randomsharding-the de facto standard-results in provably poorperformance even when frequently accessed nodes are repli-cated to many shards. By contrast, we demonstrate that onecan substantially reduce querying costs by identifying andassigning tightly knit communities to shards. In particular,our theoretical analysis motivates a novel, scalable shardingalgorithm that outperforms both random and location-basedsharding schemes.   

Publish Year: 2013

Published by: ACM-WSDM

موضوع: شبکه های اجتماعی (Social Netwroks)

لینک مشاهده صفحه اول مقاله

لینک دانلود مقاله

ایران سای – مرجع علمی فنی مهندسی

حامی دانش بومی ایرانیان