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

Recent Advances in Fully Dynamic graph algorithms - A Quick Reference Guide

ACM Journal of Experimental Algorithmics 2022年第11期27卷 1-45页

作者： Hanauer, Kathrin Henzinger, Monika Schulz, Christian Faculty of Computer Science University of Vienna Währinger Str. 29 Vienna Vienna1090 Austria Heidelberg University Im Neuenheimer Feld 205 Baden-Württemberg Heidelberg69120 Germany

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 of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms. © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM.

关键词： Dynamic algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Fuzzy Decision and graph algorithms Aided Adaptive Protection of Microgrid 1

Fuzzy Decision and Graph Algorithms Aided Adaptive Protectio...

引用

1st International Conference on Power Engineering Computing and CONtrol (PECCON)

作者： Swathika, O. V. Gnana Angalaeswari, S. Krishnan, V. Anantha Jamuna, K. Daya, J. L. Febin VIT Univ Madras 127 Tamil Nadu India

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.

关键词： Microgrid Adaptive Protection graph algorithms Fuzzy

来源：评论

学校读者我要写书评

暂无评论

LAgraph: Linear Algebra, Network Analysis Libraries, and the Study of graph algorithms

LAGraph: Linear Algebra, Network Analysis Libraries, and the...

引用

35th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Szarnyas, Gabor Bader, David A. Davis, Timothy A. Kitchen, James Mattson, Timothy G. McMillan, Scott Welch, Erik CWI Amsterdam Amsterdam Netherlands New Jersey Inst Technol Newark NJ 07102 USA Texas A&M Univ College Stn TX 77843 USA Anaconda Inc Austin TX USA Intel Corp Santa Clara CA 95051 USA Carnegie Mellon Univ Software Engn Inst Pittsburgh PA 15213 USA

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.

关键词： graph Processing graph algorithms graph Analytics Linear Algebra graphBLAS

来源：评论

学校读者我要写书评

暂无评论

An Optimization Approach to Locally-Biased graph algorithms

引用

PROCEEDINGS OF THE IEEE 2017年第2期105卷 256-272页

作者： Fountoulakis, Kimon Gleich, David F. Mahoney, Michael W. Univ Calif Berkeley Int Comp Sci Inst Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

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.

关键词： Clustering graph algorithms local algorithms network flow partitioning semi-supervised learning spectral graph theory

来源：评论

学校读者我要写书评

暂无评论

graph theory and model collection management: conceptual framework and runtime analysis of selected graph algorithms

引用

INFORMATION SYSTEMS AND E-BUSINESS MANAGEMENT 2015年第1期13卷 69-106页

作者： Breuker, Dominic Delfmann, Patrick Dietrich, Hanns-Alexander Steinhorst, Matthias WWU Muenster ERCIS D-48149 Munster Germany

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.

关键词： Business process modeling Model collection management Model analysis graph algorithms

来源：评论

学校读者我要写书评

暂无评论

LAgraph: A Community Effort to Collect graph algorithms Built on Top of the graphBLAS 33

LAGraph: A Community Effort to Collect Graph Algorithms Buil...

引用

33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Mattson, Tim Davis, Timothy A. Kumar, Manoj Buluc, Aydin McMillan, Scott Moreira, Jose Yang, Carl Intel Corp Santa Clara CA 95051 USA Lawrence Berkeley Natl Lab Computat Res Div Berkeley CA USA Texas A&M Univ College Stn TX 77843 USA IBM Corp Armonk NY 10504 USA Carnegie Mellon Univ Software Engn Inst Pittsburgh PA 15213 USA Univ Calif Davis Elect & Comp Engn Dept Davis CA 95616 USA

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 LAgraph graph 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.

关键词： graph algorithms Linear Algebra graphBLAS

来源：评论

学校读者我要写书评

暂无评论

Euler Meets GPU: Practical graph algorithms with Theoretical Guarantees 35

Euler Meets GPU: Practical Graph Algorithms with Theoretical...

引用

35th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Polak, Adam Siwiec, Adrian Stobierski, Michal Jagiellonian Univ Fac Math & Comp Sci Krakow Poland

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.

关键词： graph algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Fine-Grained Task Migration for graph algorithms using Processing in Memory 30

Fine-Grained Task Migration for Graph Algorithms using Proce...

引用

30th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Aguilera, Paula Zhang, Dong Ping Kim, Nam Sung Jayasena, Nuwan Univ Wisconsin Dept Elect & Comp Engn Madison WI 53706 USA AMD Res Sunnyvale CA USA Univ Illinois Dept Elect & Comp Engn Champaign IL USA

ISBN: (纸本)9781509036820

graphs are used in a wide variety of application domains, from social science to machine learning. graph algorithms present large numbers of irregular accesses with little data reuse to amortize the high cost of memory accesses, requiring high memory bandwidth. Processing in memory (PIM) implemented through 3D die-stacking can deliver this high memory bandwidth. In a system with multiple memory modules with PIM, the in-memory compute logic has low latency and high bandwidth access to its local memory, while accesses to remote memory introduce high latency and energy consumption. Ideally, in such a system, computation and data are partitioned among the PIM devices to maximize data locality. But the irregular memory access patterns present in graph applications make it difficult to guarantee that the computation in each PIM device will only access its local data. A large number of remote memory accesses can negate the benefits of using PIM. In this paper, we examine the feasibility and potential of fine-grained work migration to reduce remote data accesses in systems with multiple PIM devices. First, we propose a data-driven implementation of our study algorithms: breadth-first search (BFS), single source shortest path (SSSP) and betweenness centrality (BC) where each PIM has a queue where the vertices that it needs to process are held. New vertices that need to be processed are enqueued at the PIM device co-located with the memory that stores those vertices. Second, we propose hardware support that takes advantage of PIM to implement highly efficient queues that improve the performance of the queuing framework by up to 16.7%. Third, we develop a timing model for the queueing framework to explore the benefits of work migration vs. remote memory accesses. And, finally, our analysis using the above framework shows that naive task migration can lead to performance degradations and identifies trade-offs among data locality, redundant computation, and load balance among PI

关键词： graph algorithms Processing In Memory

来源：评论

学校读者我要写书评

暂无评论

Julienne: A Framework for Parallel graph algorithms usingWork-efficient Bucketing 17

Julienne: A Framework for Parallel Graph Algorithms usingWor...

引用

29th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Dhulipala, Laxman Blelloch, Guy Shun, Julian Carnegie Mellon Univ Pittsburgh PA 15213 USA Univ Calif Berkeley Berkeley CA USA

ISBN: (纸本)9781450345934

Existing graph-processing frameworks let users develop efficient implementations for many graph problems, but none of them support efficiently bucketing vertices, which is needed for bucketing-based graph algorithms such as.-stepping and approximate set-cover. Motivated by the lack of simple, scalable, and efficient implementations of bucketing-based algorithms, we develop the Julienne framework, which extends a recent shared-memory graph processing framework called Ligra with an interface for maintaining a collection of buckets under vertex insertions and bucket deletions. We provide a theoretically efficient parallel implementation of our bucketing interface and study several bucketing-based algorithms that make use of it (either bucketing by remaining degree or by distance) to improve performance: the peeling algorithm for k-core (coreness), Delta-stepping, weighted breadth-first search, and approximate set cover. The implementations are all simple and concise (under 100 lines of code). Using our interface, we develop the first work-efficient parallel algorithm for k-core in the literature with nontrivial parallelism. We experimentally show that our bucketing implementation scales well and achieves high throughput on both synthetic and real-world workloads. Furthermore, the bucketing-based algorithms written in Julienne achieve up to 43x speedup on 72 cores with hyper-threading over well-tuned sequential baselines, significantly outperform existing work-inefficient implementations in Ligra, and either outperform or are competitive with existing special-purpose parallel codes for the same problem. We experimentally study our implementations on the largest publicly available graphs and show that they scale well in practice, processing real-world graphs with billions of edges in seconds, and hundreds of billions of edges in a few minutes. As far as we know, this is the first time that graphs at this scale have been analyzed in the main memory of a single multicore m

关键词： parallel programming graph algorithms experiments shared memory

来源：评论

学校读者我要写书评

暂无评论

External Memory Priority Queues with Decrease-Key and Applications to graph algorithms 27

External Memory Priority Queues with Decrease-Key and Applic...

引用

27th Annual European Symposium on algorithms (ESA)

作者： Iacono, John Jacob, Riko Tsakalidis, Konstantinos Univ Libre Bruxelles Dept Comp Sci Brussels Belgium IT Univ Copenhagen Comp Sci Dept Copenhagen Denmark Univ Liverpool Dept Comp Sci Liverpool Merseyside England

ISBN: (纸本)9783959771245

We present priority queues in the external memory model with block size B and main memory size M that support on N elements, operation Update (a combination of operations Insert and DECREASEKEY) in O (1/B log(M/B) N/B) amortized I/Os and operations EXTRACTMIN and DELETE in O ([M-epsilon/B log(M/B) N/B]log(M/B) N/B) amortized I/Os, for any real epsilon is an element of (0, 1), using O (N/B log(M/B) N/B) blocks. Previous I/O-efficient priority queues either support these operations in O (1/B log(2) N/B)amortized I/Os [Kumar and Schwabe, SPDP '96] or support only operations INSERT, DELETE and EXTRACTMIN in optimal O (1/B log(M/B) N/B) amortized I/Os, however without supporting DECREASEKEY [Fadel et al., TCS '99]. We also present buffered repository trees that support on a multi-set of N elements, operation Insert in O (1/B log(M/B) N/B) I/Os and operation Extract on K extracted elements in O (M-epsilon/B log(M/B) K/B) amortized I/Os, using O(N/B) blocks. Previous results achieve O (1/B log(2) N/B) I/Os and O (log(2) N/B + K/B) I/Os, respectively [Buchsbaum et al., SODA '00]. Our results imply improved O (E/B log(M/B) E/B) I/Os for single-source shortest paths, depth-first search and breadth-first search algorithms on massive directed dense graphs ( V, E) with E = Omega(V1+ epsilon), epsilon > 0 and V = Omega(M), which is equal to the I/O-optimal bound for sorting E values in external memory.

关键词： priority queues external memory graph algorithms shortest paths depth-first search breadth-first search

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：