Gossip-based partitioning and replication for Online Social Networks
2014 (English)In: ASONAM 2014 - Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2014, 33-42 p.Conference paper (Refereed)
Online Social Networks (OSNs) have been gaining tremendous growth and popularity in the last decade, as they have been attracting billions of users from all over the world. Such networks generate petabytes of data from the social interactions among their users and create many management and scalability challenges. OSN users share common interests and exhibit strong community structures, which create complex dependability patterns within OSN data, thus, make it difficult to partition and distribute in a data center environment. Existing solutions, such as, distributed databases, key-value stores and auto scaling services use random partitioning to distribute the data across a cluster, which breaks existing dependencies of the OSN data and may generate huge inter-server traffic. Therefore, there is a need for intelligent data allocation strategy that can reduce the network cost for various OSN operations. In this paper, we present a gossip-based partitioning and replication scheme that efficiently splits OSN data and distributes the data across a cluster. We achieve fault tolerance and data locality, for one-hop neighbors, through replication. Our main contribution is a social graph placement strategy that divides the social graph into predefined size partitions and periodically updates the partitions to place socially connected users together. To evaluate our algorithm, we compare it with random partitioning and a state-of-the-art solution SPAR. Results show that our algorithm generates up to four times less replication overhead compared to random partitioning and half the replication overhead compared to SPAR.
Place, publisher, year, edition, pages
2014. 33-42 p.
online social networks, partitioning, replication, scalability, Complex networks, Distributed database systems, Fault tolerance, Social sciences, Community structures, Distributed database, On-line social networks, Online social networks (OSNs), Placement strategy, Social interactions, Social networking (online)
Communication Systems Information Systems, Social aspects
IdentifiersURN: urn:nbn:se:kth:diva-167541DOI: 10.1109/ASONAM.2014.6921557ScopusID: 2-s2.0-84911028340ISBN: 9781479958771OAI: oai:DiVA.org:kth-167541DiVA: diva2:818898
2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014, 17 August 2014 through 20 August 2014
QC 201506092015-06-092015-05-222015-06-09Bibliographically approved