We study the problem of implementing graph algorithms efficiently on Pregel-like systems, which can be surprisingly challenging. Standard graph algorithms in this setting can incur unnecessary inefficiencies such as s...
详细信息
We study the problem of implementing graph algorithms efficiently on Pregel-like systems, which can be surprisingly challenging. Standard graph algorithms in this setting can incur unnecessary inefficiencies such as slow convergence or high communication or computation cost, typically due to structural properties of the input graphs such as large diameters or skew in component sizes. We describe several optimization techniques to address these inefficiencies. Our most general technique is based on the idea of performing some serial computation on a tiny fraction of the input graph, complementing Pregel's vertex-centric parallelism. We base our study on thorough implementations of several fundamental graph algorithms, some of which have, to the best of our knowledge, not been implemented on Pregel-like systems before. The algorithms and optimizations we describe are fully implemented in our open-source Pregel implementation. We present detailed experiments showing that our optimization techniques improve runtime significantly on a variety of very large graph datasets.
作者：
Jansson, JesperKyoto Univ
Inst Chem Res Bioinformat Ctr Lab Math Bioinformat Uji Kyoto 6110011 Japan
This special issue of algorithms is devoted to the design and analysis of algorithms for solving combinatorial problems of a theoretical or practical nature involving graphs, with a focus on computational complexity.
This special issue of algorithms is devoted to the design and analysis of algorithms for solving combinatorial problems of a theoretical or practical nature involving graphs, with a focus on computational complexity.
This book contains Volumes 4 and 5 of the Journal of graph algorithms and Applications (JGAA). The first book of this series, graph algorithms and Applications 1, published in March 2002, contains Volumes 1-3 of *** i...
详细信息
ISBN:
(数字)9789812794741
ISBN:
(纸本)9789812388551
This book contains Volumes 4 and 5 of the Journal of graph algorithms and Applications (JGAA). The first book of this series, graph algorithms and Applications 1, published in March 2002, contains Volumes 1-3 of *** is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit design. The journal is supported by distinguished advisory and editorial boards, has high scientific standards, and takes advantage of current electronic document technology. The electronic version of JGAA is available on the Web at ***/.graph algorithms and Applications 2 presents contributions from prominent authors and includes selected papers from the Dagstuhl Seminar on graph algorithms and Applications and the Symposium on graph Drawing in 1998. All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few o...
详细信息
Consumer power demand is an ever increasing component in distribution networks. A solution to meet this bridge between conventional source availability and load demands is using microgrids. The microgrid is an assortm...
详细信息
Consumer power demand is an ever increasing component in distribution networks. A solution to meet this bridge between conventional source availability and load demands is using microgrids. The microgrid is an assortment of loads and distributed generators (DGs). The dynamicity of microgrids is a key challenge for protection engineers. The purpose of this paper is to develop a central protection system (CPS) for a microgrid with fuzzy based monitoring and graph algorithms based protection control features. Hence the CPS provides suitable overcurrent relay coordination to the microgrid which may cause minimum portion of the network disconnection. (C) 2017 The Authors. Published by Elsevier Ltd.
graph algorithms can be expressed in terms of linear algebra. graphBLAS is a library of low-level building blocks for such algorithms that targets algorithm developers. LAgraph builds on top of the graphBLAS to target...
详细信息
ISBN:
(纸本)9781665435772
graph algorithms can be expressed in terms of linear algebra. graphBLAS is a library of low-level building blocks for such algorithms that targets algorithm developers. LAgraph builds on top of the graphBLAS to target users of graph algorithms with high-level algorithms common in network analysis. In this paper, we describe the first release of the LAgraph library, the design decisions behind the library, and performance using the GAP benchmark suite. LAgraph, however, is much more than a library. It is also a project to document and analyze the full range of algorithms enabled by the graphBLAS. To that end, we have developed a compact and intuitive notation for describing these algorithms. In this paper, we present that notation with examples from the GAP benchmark suite.
Locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of locality constraint and calling ...
详细信息
Locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of locality constraint and calling a traditional graph algorithm;but more interesting are locally-biased graph algorithms that compute answers by running a procedure that does not even look at most of the input graph. This corresponds more closely to what practitioners from various data science domains do, but it does not correspond well with the way that algorithmic and statistical theory is typically formulated. Recent work from several research communities has focused on developing locally-biased graph algorithms that come with strong complementary algorithmic and statistical theory and that are useful in practice in downstream data science applications. We provide a review and overview of this work, highlighting commonalities between seemingly different approaches, and highlighting promising directions for future work.
Analysing conceptual models is a frequent task of business process management (BPM), for instance to support comparison or integration of business processes, to check business processes for compliance or weaknesses, o...
详细信息
Analysing conceptual models is a frequent task of business process management (BPM), for instance to support comparison or integration of business processes, to check business processes for compliance or weaknesses, or to tailor conceptual models for different audiences. As recently, many companies have started to maintain large model collections and analysing such collections manually may be laborious, practitioners have articulated a demand for automatic model analysis support. Hence, BPM scholars have proposed a plethora of different model analysis techniques. As virtually any conceptual model can be interpreted as a mathematical graph and model analysis techniques often include some kind of graph problem, in this paper, we introduce a graph algorithm based model analysis framework that can be accessed by specialized model analysis techniques. To prove that basic graph algorithms are feasible to support such a framework, we conduct a performance analysis of selected graph algorithms.
In 2013, we released a position paper to launch a community effort to define a common set of building blocks for constructing graph algorithms in the language of linear algebra. This led to the graphBLAS. We released ...
详细信息
ISBN:
(纸本)9781538655559
In 2013, we released a position paper to launch a community effort to define a common set of building blocks for constructing graph algorithms in the language of linear algebra. This led to the graphBLAS. We released a specification for the C programming language binding to the graphBLAS in 2017. Since that release, multiple libraries that conform to the graphBLAS C specification have been produced. In this position paper, we launch the next phase of this ongoing community effort: a project to assemble a set of high level graph algorithms built on top of the graphBLAS. While many of these algorithms are well-known with high quality implementations available, they have not been assembled in one place and integrated with the graphBLAS. We call this project the LAgraphgraph algorithms project and with this position paper, we put out a call for collaborators to join us. While the initial goal is to just assemble these algorithms into a single framework, the long term goal is a library of production-worthy code, with the LAgraph library serving as an open source repository of verified graph algorithms that use the graphBLAS.
The Euler tour technique is a classical tool for designing parallel graph algorithms, originally proposed for the PRAM model. We ask whether it can be adapted to run efficiently on GPU. We focus on two established app...
详细信息
ISBN:
(纸本)9781665440660
The Euler tour technique is a classical tool for designing parallel graph algorithms, originally proposed for the PRAM model. We ask whether it can be adapted to run efficiently on GPU. We focus on two established applications of the technique: (1) the problem of finding lowest common ancestors (LCA) of pairs of nodes in trees, and (2) the problem of finding bridgis in undirected graphs. In our experiments, we compare theoretically optimal algorithms using the Euler tour technique against simpler heuristics supposed to perform particularly well on typical instances. We show that the Euler tour-based algorithms not only fulfill their theoretical promises and outperform practical heuristics on hard instances, but also perform on par with them on easy instances.
暂无评论