检索结果-内蒙古大学图书馆

SOOP: Efficient distributed graph computation Supporting Second-Order Random Walks

Journal of Computer Science & Technology 2021年第5期36卷 985-1001页

作者： Songjie Niu Dongyan Zhou State Key Laboratory of Computer Architecture Institute of Computing TechnologyChinese Academy of Sciences Beijing 100190China University of Chinese Academy of Sciences Beijing 100049China Bytedance Technology Beijing 100086China

The second-order random walk has recently been shown to effectively improve the accuracy in graph analysis *** work mainly focuses on centralized second-order random walk(SOW)*** algorithms rely on edge-to-edge transition probabilities to generate next random ***,it is prohibitively costly to store all the probabilities for large-scale graphs,and restricting the number of probabilities to consider can negatively impact the accuracy of graph analysis *** this paper,we propose and study an alternative approach,SOOP(second-order random walks with on-demand probability computation),that avoids the space overhead by computing the edge-to-edge transition probabilities on demand during the random ***,the same probabilities may be computed multiple times when the same edge appears multiple times in SOW,incurring extra cost for redundant computation and *** propose two optimization techniques that reduce the complexity of computing edge-to-edge transition probabilities to generate next random steps,and reduce the cost of communicating out-neighbors for the probability computation,*** experiments on real-world and synthetic graphs show that SOOP achieves orders of magnitude better performance than baseline precompute solutions,and it can efficiently computes SOW algorithms on billion-scale graphs.

关键词： second-order random walk(SOW) Node2Vec second-order PageRank distributed graph computation SOOP(second-order random walks with on-demand probability computation)

来源：评论

学校读者我要写书评

暂无评论

TransGPerf:Exploiting Transfer Learning for Modeling distributed graph computation Performance

引用

Journal of Computer Science & Technology 2021年第4期36卷 778-791页

作者： Songjie Niu Shimin Chen State Key Laboratory of Computer Architecture Institute of Computing TechnologyChinese Academy of Sciences Beijing 100190China University of Chinese Academy of Sciences Beijing 100049China

It is challenging to model the performance of distributed graph *** formulation cannot easily capture the diversified factors and complex interactions in the *** learning methods require a large number of training samples to generate an accurate prediction ***,it is time-consuming to run the required graph computation tests to obtain the training *** this paper,we propose TransGPerf,a transfer learning based solution that can exploit prior knowledge from a source scenario and utilize a manageable amount of training data for modeling the performance of a target graph computation *** results show that our proposed method is capable of generating accurate models for a wide range of graph computation tasks on Powergraph and *** outperforms transfer learning methods proposed for other applications in the literature.

关键词： performance modeling distributed graph computation deep learning transfer learning

来源：评论

学校读者我要写书评

暂无评论

DisNet: A Framework for distributed graph computation

DisNet: A Framework for Distributed Graph Computation

引用

International Conference on Advances in Social Networks Analysis and Mining (ASONAM)

作者： Lichtenwalter, Ryan Chawla, Nitesh V. Univ Notre Dame Dept Comp Sci Notre Dame IN 46556 USA

ISBN: (纸本)9780769543758

With the rise of network science as an exciting interdisciplinary research topic, efficient graph algorithms are in high demand. Problematically, many such algorithms measuring important properties of networks have asymptotic lower bounds that are quadratic, cubic, or higher in the number of vertices. For analysis of social networks, transportation networks, communication networks, and a host of others, computation is intractable. In these networks computation in serial fashion requires years or even decades. Fortunately, these same computational problems are often naturally parallel. We present here the design and implementation of a master-worker framework for easily computing such results in these circumstances. The user needs only to supply two small fragments of code describing the fundamental kernel of the computation. The framework automatically divides and distributes the workload and manages completion using an arbitrary number of heterogeneous computational resources. In practice, we have used thousands of machines and observed commensurate speedups. Writing only 31 lines of standard C++ code, we computed betweenness centrality on a network of 4.7M nodes in 25 hours.

关键词： Algorithm design and analysis Approximation algorithms C++ language Data structures DisNet Instruction sets Libraries Parallel processing Writing asymptotic lower bounds betweenness centrality communication network analysis distributed computing distributed graph computation graph algorithm graph algorithms graph theory heterogeneous computational resources map-reduce master-worker framework network science network theory (graphs) parallel algorithms parallel processing social network analysis standard C++ code transportation network analysis

来源：评论

学校读者我要写书评

暂无评论

Analysis and Evaluation of the GAS Model for distributed graph computation 37

Analysis and Evaluation of the GAS Model for Distributed Gra...

引用

37th IEEE International Conference on distributed Computing Systems (ICDCS)

作者： Wang, Jinyan Zhang, Chengfei Natl Univ Def Technol Changsha Hunan Peoples R China

ISBN: (纸本)9781538632932

Compared with distributed graph computation, traditionally single node computation is unfitted in processing large scale graph data. The GAS (Gather, Apply and Scatter) Model is a universal vertex-cut graph computation programming model based on edge-centric programs to support graph algorithms, which process distributed graph computation after graph partition. In this paper, we introduce that three minor-steps of GAS. We then analyze more complete process of GAS considering intra-node computation and inter node communication of distributed graph computation. Based on our analysis, we evaluate the performance in different nodes of graph analysis algorithm applying GAS model. The evaluation shows that the bottleneck is computation performance or communication bandwidth depending on number of nodes, which is an inspiration of optimizing the GAS model.

关键词： distributed graph computation vertex-cut GAS model computation performance inter-node communication

来源：评论

学校读者我要写书评

暂无评论

Enhancing the Scalability and Performance of Iterative graph Algorithms on Apache Storm

Enhancing the Scalability and Performance of Iterative Graph...

引用

IEEE International Conference on Big Data (Big Data)

作者： Jayasekara, Sachini Karunasekera, Shanika Harwood, Aaron Univ Melbourne Dept Comp & Informat Syst Melbourne Vic Australia

ISBN: (纸本)9781538650356

Real-time processing of large-scale, time-varying graphs is becoming essential in bigdata streaming applications that require high-throughput and low-latency. Streaming applications typically perform graph computations on periodic snapshots of the graph, using windowing. For large-scale graphs, that contains millions of edges, distributed parallel processing is essential to meet the throughput and latency needs of streaming applications. Apache Storm, a widely used stream processing system, provides a topology-based processing architecture which supports distribution and pipelining to meet the latency and throughput needs;a typical Storm topology contains a fixed number of stages, each stage with a single operator supporting a single computation step, which can be parallelized through horizontal scaling (bolt instances). One of the limitations of such a topology, is the fixed number of stages, which makes it not suitable for graph algorithms that require iterative computations, such as the PageRank algorithm, because the number of iterations, hence the number of stages in the topology, is unknown a-priori. In this paper we explore how iterative graph algorithms can be executed efficiently in a distributed manner for scalability (with the graph distributed across a set of Storm bolts), using a single stage of a Storm topology, using Storm's cyclic communication (S-CC) mechanism. We show that S-CC approach outperforms alternative approaches that can be used for parallel-iterative computations in Storm, such as off-loading to a third-party graph processing system such as Giraph or using a distributed memory architecture, both in terms of scalability and performance.

关键词： Dynamic graphs distributed graph computation real-time analytics stream processing

来源：评论

学校读者我要写书评

暂无评论

Benefits of Stabilization versus Rollback in Self-Stabilizing graph-Based Applications on Eventually Consistent Key-Value Stores 39

Benefits of Stabilization versus Rollback in Self-Stabilizin...

引用

39th International Symposium on Reliable distributed Systems (SRDS)

作者： Duong Nguyen Kulkarni, Sandeep S. Michigan State Univ Dept Comp Sci & Engn E Lansing MI 48824 USA

ISBN: (纸本)9781728176260

In this paper, we evaluate and compare the performance of two approaches, namely self-stabilization and rollback, to handling consistency violating faults (cvf) that occur when a self-stabilizing distributed graph-based program is executed on an eventually consistent key-value store. Consistency violating faults are caused by reading wrong values due to weaker level of consistency provided by the key-value store. One way to deal with these faults is to utilize rollback whereas another way is to rely on the property of self-stabilization that is expected to provide recovery from arbitrary states. We evaluate both these approaches in different case studies -planar graph coloring, arbitrary graph coloring, and maximal matching- as well as for different problem dimensions such as input data characteristics, workload partition, and network latency. We also consider the effect of executing non-stabilizing algorithm with rollback with a similar stabilizing algorithm that does not utilize rollback.

关键词： distributed graph computation Eventual consistency Fault tolerance Key-value store Passive node model Rollback Self-stabilization

来源：评论

学校读者我要写书评

暂无评论

Research on communication mechanism optimization based on distributed graph computing environment 4

Research on communication mechanism optimization based on di...

引用

4th International Conference on Big Data Economy and Information Management, BDEIM 2023

作者： Lin, Jianchao Cao, Chunna Ren, Chunhui State Grid Laboratory of Grid Advanced Computing and Applications State Grid Smart Grid Research Institute Co. Ltd Beijing China

ISBN: (纸本)9798400716669

In recent years, with the rapid development of the Internet of Things, the Internet, and social networks, the storage of data in the network is growing at an explosive rate and is becoming more and more closely related to the real natural world. Driven by large-scale data mining and machine learning applications, distributed graph computing models that use graph data structures to describe data and relationships between data have been increasingly widely used. Therefore, this paper studies the optimization of communication mechanisms based on a distributed graph computing environment. Firstly, a BSP model based on a pure message-passing communication mechanism of a distributed graph computing system is established. Secondly, the optimization model is evaluated from two aspects: data communication and convergence condition judgment. Finally, large-scale data sets are used to test and evaluate performance optimization. The results show that this method can greatly improve the efficiency of graph parallel computing. © 2023 ACM.

关键词： BSP model distributed graph computation distributed system graph processing Parallel computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：