Much of the data being produced in large scale by modern applications represents connected entities and their relationships, that can be modeled as large graphs. In order to extract valuable information from these lar...
详细信息
Much of the data being produced in large scale by modern applications represents connected entities and their relationships, that can be modeled as large graphs. In order to extract valuable information from these large datasets, several parallel and distributed graph processing engines have been proposed. These systems are designed to run in large clusters, where resources must by allocated efficiently. Aiming to handle this problem, this paper presents a performance prediction model for GPS, a popular Pregel-based graphprocessing framework. By leveraging a micro-partitioning technique, our system can use various partitioning algorithms that greatly reduce the execution time, comparing with the simple hash partitioning that is commonly used in graphprocessing systems. Experimental results show that the prediction model has accuracy close to 90%, allowing it to be used in schedulers or to estimate the cost of running graphprocessing tasks.
Big data applications based on graphs need to be scalable enough for handling immense growth in size of graphs, efficiently. Scalable graphprocessing typically handles the high workload by increasing the number of co...
详细信息
Big data applications based on graphs need to be scalable enough for handling immense growth in size of graphs, efficiently. Scalable graphprocessing typically handles the high workload by increasing the number of computing nodes. However, this increases the chances of single or multiple node (multi-node) failures. Failures may occur during normal job execution, as well as during recovery. Most of the systems for failure detection either follow checkpoint-based recovery which has high computation cost, or follows replication that has high memory overhead. In this work, we have proposed an unsupervised learning-based failure-recovery scheme for graphprocessing systems that detects different kinds of failures and allows node recovery within a shorter amount of time. It has been able to provide enhanced performance as compared to traditional failure-recovery models with respect to simultaneous recovery from single and multi-node failures, memory overload and computational latency. Evaluating its performance on four benchmark datasets has reinforced its strength and makes the proposed model completely fit in with the status quo.
Extreme scale graph analytics is imperative for several real-world Big Data applications with the underlying graph structure containing millions or billions of vertices and edges. Since such huge graphs cannot fit int...
详细信息
ISBN:
(数字)9781665488020
ISBN:
(纸本)9781665488020
Extreme scale graph analytics is imperative for several real-world Big Data applications with the underlying graph structure containing millions or billions of vertices and edges. Since such huge graphs cannot fit into the memory of a single computer, distributedprocessing of the graph is required. Several frameworks have been developed for performing graphprocessing on distributed systems. The frameworks focus primarily on choosing the right computation model and the partitioning scheme under the assumption that such design choices will automatically reduce the communication overheads. For any computational model and partitioning scheme, communication schemes - the data to be communicated and the virtual interconnection network among the nodes - have significant impact on the performance. To analyze this impact, in this work, we identify widely used communication schemes and estimate their performance. Analyzing the trade-offs between the number of compute nodes and communication costs of various schemes on a distributed platform by brute force experimentation can be prohibitively expensive. Thus, our performance estimation models provide an economic way to perform the analyses given the partitions and the communication scheme as input. We validate our model on a local HPC cluster as well as the cloud hosted NSF Chameleon cluster. Using our estimates as well as the actual measurements, we compare the communication schemes and provide conditions under which one scheme should be preferred over the others.
Big data applications like social networks, biological networks, etc. are often realized on graphs. graphprocessing, if done on a single node, increases time complexity. Partitioning of graphs has been proved to be u...
详细信息
ISBN:
(纸本)9783031105395;9783031105388
Big data applications like social networks, biological networks, etc. are often realized on graphs. graphprocessing, if done on a single node, increases time complexity. Partitioning of graphs has been proved to be useful towards handle this well-known issue. There are several partitioning algorithms that are used to partition a graph. Each partition is assigned to a node within a cluster. However, the storage capacity of a node is limited. Therefore, an effective data distribution mechanism is required. This work aims to propose a novel strategy that would define an efficient distribution of graphs into nodes using genetic algorithms. The proposed data distribution strategy, when applied on two benchmark data set, shows improved data availability without increasing the number of replicas. It has also observed that the execution time will almost became half after applying the proposed method.
With the increase in graph dataset size and algorithm complexity, distributed graph processing runs with severe reliability problems caused by high uncertainty. A range of fault tolerance specific to distributedgraph...
详细信息
ISBN:
(纸本)9781665426039
With the increase in graph dataset size and algorithm complexity, distributed graph processing runs with severe reliability problems caused by high uncertainty. A range of fault tolerance specific to distributed graph processing has been proposed. Unfortunately, current work does not consider the complexity of actual failure but only verifies the effectiveness of fault tolerance by simply killing processes or crashing compute nodes. We investigate the impact of failures on the effectiveness of three widely-used fault-tolerance mechanisms in distributed graph processing, such as checkpoint-based fault tolerance, logging-based fault tolerance, and replication-based fault tolerance, by performing fault injection based on extensive research about actual faults. Based on the above analysis, we find that failure offsets cause fault tolerance's average recovery coverage factor to drop by 0.37% to 26.77%, and small checkpoint intervals and the confined recovery bring weak robustness of failure recovery.
graphprocessing is one of the most important and ubiquitous classes of analytical workloads. To process large graph datasets with diverse algorithms, tens of distributed graph processing frameworks emerged. Their use...
详细信息
ISBN:
(数字)9781728166773
ISBN:
(纸本)9781728166773
graphprocessing is one of the most important and ubiquitous classes of analytical workloads. To process large graph datasets with diverse algorithms, tens of distributed graph processing frameworks emerged. Their users are increasingly expecting high performance for diversifying workloads. Meeting this expectation depends on understanding the performance of each framework. However, performance analysis and characterization of a distributed graph processing framework is challenging. Contributing factors are the irregular nature of graph computation across datasets and algorithms, the semantic gap between workload-level and system-level monitoring, and the lack of lightweight mechanisms for collecting fine-grained performance data. Addressing the challenge, in this work we present Grade10, an experimental framework for fine-grained performance characterization of distributed graph processing workloads. Grade10 captures the graph workload execution as a performance graph from logs and application traces, and builds a fine-grained, unified workload-level and system-level view of performance. Grade10 samples sparsely for lightweight monitoring and addresses the problem of accuracy through a novel approach for resource attribution. Last, it can identify automatically resource bottlenecks and common classes of performance issues. Our real-world experimental evaluation with Giraph and Powergraph, two state-of-the-art distributed graph processing systems, shows that Grade10 can reveal large differences in the nature and severity of bottlenecks across systems and workloads. We also show that Grade10 can be used in debugging processes, by exemplifying how we find with it a synchronization bug in Powergraph that slows down affected phases by 1.10 - 2.50x. Grade10 is an open-source project available at https://***/atlarge-research/grade10.
A multitude of contemporary applications heavily involve graph data whose size appears to be ever-increasing. This trend shows no signs of subsiding and has caused the emergence of a number of distributedgraph proces...
详细信息
A multitude of contemporary applications heavily involve graph data whose size appears to be ever-increasing. This trend shows no signs of subsiding and has caused the emergence of a number of distributed graph processing systems including Pregel, Apache Giraph, and graphX. However, the unprecedented scale now reached by real-world graphs hardens the task of graphprocessing due to excessive memory demands even for distributed environments. By and large, such contemporary graphprocessing systems employ ineffective in-memory representations of adjacency lists. Therefore, memory usage patterns emerge as a primary concern in distributed graph processing. We seek to address this challenge by exploiting empirically-observed properties demonstrated by graphs generated by human activity. In this paper, we propose 1) three compressed adjacency list representations that can be applied to any distributed graph processing system, 2) a variable-byte encoded representation of out-edge weights for space-efficient support of weighted graphs, and 3) a tree-based compact out-edge representation that allows for efficient mutations on the graph elements. We experiment with publicly-available graphs whose size reaches two-billion edges and report our findings in terms of both space-efficiency and execution time. Our suggested compact representations do reduce respective memory requirements for accommodating the graph elements up-to 5 times if compared with state-of-the-art methods. At the same time, our memory-optimized methods retain the efficiency of uncompressed structures and enable the execution of algorithms for large scale graphs in settings where contemporary alternative structures fail due to memory errors.
Efficient processing of large-scale graphs in distributed environments has been an increasingly popular topic of research in recent years. Inter-connected data that can be modeled as graphs appear in application domai...
详细信息
Efficient processing of large-scale graphs in distributed environments has been an increasingly popular topic of research in recent years. Inter-connected data that can be modeled as graphs appear in application domains such as machine learning, recommendation, web search, and social network analysis. Writing distributedgraph applications is inherently hard and requires programming models that can cover a diverse set of problems, including iterative refinement algorithms, graph transformations, graph aggregations, pattern matching, ego-network analysis, and graph traversals. Several high-level programming abstractions have been proposed and adopted by distributed graph processing systems and big data platforms. Even though significant work has been done to experimentally compare distributed graph processing frameworks, no qualitative study and comparison of graph programming abstractions has been conducted yet. In this survey, we review and analyze the most prevalent high-level programming models for distributed graph processing, in terms of their semantics and applicability. We review 34 distributed graph processing systems with respect to the graphprocessing models they implement and we survey applications that appear in recent distributedgraph systems papers. Finally, we discuss trends and open research questions in the area of distributed graph processing.
The accelerated growth of datasets observed in modern applications also applies to datasets modeled as graphs. To handle this problem, several large scale distributed graph processing models have been proposed, such a...
详细信息
ISBN:
(纸本)9781538672327
The accelerated growth of datasets observed in modern applications also applies to datasets modeled as graphs. To handle this problem, several large scale distributed graph processing models have been proposed, such as Pregel. These systems are designed to run in large clusters, where the resources must be allocated efficiently. In this paper we present a prediction model and a scheduler for Pregel-based distributed graph processing jobs. The jobs are treated as moldable tasks by the scheduler that, based on the predictions, allocates the best number of workers to each job in order to minimize makespan. Experimental results show that the prediction model has accuracy close to 90%, allowing the scheduler to work within the theoretical approximation limits of the optimal makespan.
graphprocessing has been widely used to capture complex data dependency and uncover relationship insights. Due to the ever-growing graph scale and algorithm complexity, distributed graph processing has become more an...
详细信息
ISBN:
(纸本)9781509066117
graphprocessing has been widely used to capture complex data dependency and uncover relationship insights. Due to the ever-growing graph scale and algorithm complexity, distributed graph processing has become more and more popular. In this paper, we investigate how to balance performance and cost for large scale graphprocessing on configurable virtual machines (VMs). We analyze the system architecture and implementation details of a Pregel-like distributed graph processing framework and develop a system-aware model to predict the execution time. Consequently, cost effective execution scenarios are recommended by selecting a certain number of VMs with specified capability subject to the predefined resource price and user preference. Experiments using synthetic and real world graphs have verified that system-aware model can achieve much higher prediction accuracy than popular machine-learning models which treat graphprocessing framework as a black box. As a result, the recommended execution scenarios have comparable cost efficiency to the optimal scenarios.
暂无评论