3 years ago

DRONE: a Distributed Subgraph-Centric Framework for Processing Large Scale Power-law Graphs.

Xiaole Wen, Shuai Zhang, Haihang You

Nowadays, in the big data era, social networks, graph databases, knowledge graphs, electronic commerce etc. demand efficient and scalable capability to process an ever increasing volume of graph-structured data. To meet the challenge, two mainstream distributed programming models, vertex-centric (VC) and subgraph-centric (SC) were proposed. Compared to the VC model, the SC model converges faster with less communication overhead on well-partitioned graphs, and is easy to program due to the "think like a graph" philosophy. The edge-cut method is considered as a natural choice of subgraph-centric model for graph partitioning, and has been adopted by Giraph++, Blogel and GRAPE. However, the edge-cut method causes significant performance bottleneck for processing large scale power-law graphs. Thus, the SC model is less competitive in practice. In this paper, we present an innovative distributed graph computing framework, DRONE (Distributed gRaph cOmputiNg Engine). It combines the subgraph-centric model and the vertex-cut graph partitioning strategy. Experiments show that DRONE outperforms the state-of-art distributed graph computing engines on real-world graphs and synthetic power-law graphs. DRONE is capable of scaling up to process one-trillion-edge synthetic power-law graphs, which is orders of magnitude larger than previously reported by existing SC-based frameworks.

Publisher URL: http://arxiv.org/abs/1812.04380

DOI: arXiv:1812.04380v2

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.