Premium
Workload prediction and balance for distributed reachability processing for large‐scale attribute graphs
Author(s) -
Ho LiYung,
Wu JanJan,
Liu Pangfeng
Publication year - 2017
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4344
Subject(s) - computer science , locality , reachability , workload , distributed computing , partition (number theory) , graph , theoretical computer science , parallel computing , operating system , philosophy , linguistics , mathematics , combinatorics
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%.