Change search
ReferencesLink to record
Permanent link

Direct link
Gossip-based Partitioning and Replication Middleware for Online Social Networks
KTH, School of Information and Communication Technology (ICT).
2013 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The nature of Online Social Networks (OSNs) has created many scalability challenges for OSN providers in the last decade. The main challenge comes with a huge amount of data that is generated by OSNs and requires large data centers to handle the workload. The existence of strong community structure in social networks creates complex dependability patterns within the OSN data and makes it dicult to deploy over multiple servers without breaking the relation structure. Such systems may require communication among multiple servers and can generate high inter-server trac. With no intelligent data allocation strategy, vital operations of OSNs like query processing and data management inevitably result in high and costly inter-server trac. Existing solutions, i.e., distributed databases, key-value stores and auto scaling, may be inecient and unable to scale for OSNs.

In our work, we present a distributed partitioning and replication middleware that eciently partitions an OSN graph and distributes it across the cluster in order to achieve high availability and scalability for OSNs. Our algorithm splits the social graph into equal sized partitions and periodically updates the partitions to achieve optimal placement of users. Additionally, our algorithm achieves fault tolerance and data locality at a low cost of redundancy through replication. We compared our algorithm with a de-facto random partitioning, state-of-the-art solution SPAR and a distributed graph partitioning algorithm called JA-BEJA. In the experiments, we show that our approach generates four times lower replication overhead compared to random partitioning, and generates lower replication overhead by a factor of two compared to SPAR. We also demonstrate that our algorithm is able to tolerate high churn rates and scale for large OSNs.

Place, publisher, year, edition, pages
2013. , 75 p.
TRITA-ICT-EX, 2013:181
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-177867OAI: diva2:874633
Available from: 2015-12-01 Created: 2015-11-27 Last updated: 2015-12-01Bibliographically approved

Open Access in DiVA

No full text

By organisation
School of Information and Communication Technology (ICT)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link