Change search
ReferencesLink to record
Permanent link

Direct link
Gossip-based partitioning and replication for Online Social Networks
KTH, School of Electrical Engineering (EES), Communication Networks.ORCID iD: 0000-0001-5872-7809
KTH, School of Electrical Engineering (EES), Communication 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)
Abstract [en]

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.
Keyword [en]
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)
National Category
Communication Systems Information Systems, Social aspects
URN: urn:nbn:se:kth:diva-167541DOI: 10.1109/ASONAM.2014.6921557ScopusID: 2-s2.0-84911028340ISBN: 9781479958771OAI: 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 20150609

Available from: 2015-06-09 Created: 2015-05-22 Last updated: 2015-06-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Nasir, M. Anis U.Girdzijauskas, Sarunas
By organisation
Communication Networks
Communication SystemsInformation Systems, Social aspects

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

Altmetric score

Total: 8 hits
ReferencesLink to record
Permanent link

Direct link