Workload prediction and balance for distributed reachability processing for large‐scale attribute graphs. (10th October 2017)

• Record Type: Journal Article
• Authors: Ho, Li‐Yung; Wu, Jan‐Jan; Liu, Pangfeng
• Is Part Of: Concurrency and computation. Volume 30:Number 6(2018)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2017-10-10
• Subjects: attribute graph -- bulk synchronization -- distributed reachability -- graph algorithm -- workload balance -- workload prediction; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4344
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: Reachability query with label constraint in an attribute graph is one of the most fundamental and important operations in semantic network analysis. However, ever‐growing graph size has resulted in intractable reachability problems on single machines. This work aims to devise efficient solutions for the reachability with label constraint problem in an attribute graph in a distributed environment. We focus on two issues in distributed processing— data locality and workload balancing —since data locality reduces communication overhead and workload balancing improves the efficiency of cluster use. We propose three novel techniques to address the two issues: (1) a partition replication method that improves data locality while conserving community property, (2) a workload‐prediction method that accurately predicts machine workloads for a given quer, and (3) a workload balancing method that uses these predictions to shift partial workloads among machines to produce a balanced workload. Experimental results suggest that these techniques significantly improve performance and reduce total execution time by 40%.