Minimizing inter-server communications by exploiting self-similarity in online social networks

Hanhua Chen, Hai Jin, Ning Jin, Tao Gu

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

17 Citations (Scopus)

Abstract

Efficiently operating on relevant data for users in large-scale online social network (OSN) systems is a challenging problem. Storage systems used by popular OSN systems often rely on key-value stores, where randomly partitioning the data of users among servers across the data centers is the defacto standard. Although by using DHTs, the random partition scheme is highly scalable for hosting a large number of users, it leads to costly inter-server communications across data centers due to the complexity of interconnection and interaction between OSN users. In this paper, we explore how to reduce the inter-server communications by retaining the simple and robust nature of OSNs. We propose a data placement solution atop OSN systems to divide users among servers according to the interaction-locality-based structure. Our approach exploits a simple, yet powerful principle of OSN interactions, self-similarity, which reveals that the inter-server communication cost is minimized under such intrinsic structure. Our algorithm avoids a significant amount of inter-server traffic as well as achieves load balance among servers across the data centers. We demonstrate the existence of self-similarity in large-scale Facebook traces including 10 million Facebook users and 24 million interaction events. We conduct comprehensive trace-driven simulations to evaluate this design exploiting the unique feature of self-similarity. Results show that our scheme significantly reduces the traffic and latency of the existing schemes.
Original languageEnglish
Title of host publication2012 20th IEEE International Conference on Network Protocols (ICNP 2012)
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages10
ISBN (Print)9781467324472
DOIs
Publication statusPublished - 2012
Externally publishedYes

Keywords

  • Self-similarity
  • interaction graph
  • inter-server communications
  • data center
  • online social networks

Fingerprint

Dive into the research topics of 'Minimizing inter-server communications by exploiting self-similarity in online social networks'. Together they form a unique fingerprint.

Cite this