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

23rd IEEE International Conference on Parallel and Distributed Systems (ICPADS)

作者： Wang, Lipeng Jia, Xiaoying Luo, Qiong Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781538621295

The betweenness centrality measure has been widely adopted in various graph analytics applications, such as community detection and brain network analysis. Due to the high intensity of BC computation and rapid data growth, there have been a number of studies on parallel BC computation, either on CPUs or GPUs. However, there has not been a comprehensive comparative study on the BC algorithm on different processors. In this paper, we revisit shared-memory parallel BC computation on four kinds of processors, including multi-core CPUs, manycore GPUs, and two generations of Intel MIC processors. We find that, with suitable parallelization strategies and data-oriented optimizations, commodity multi-core CPUs are the fastest, followed by the second generation MIC. These two processors are faster than the state-of-the-art GPU implementations across all kinds of graphs. In comparison, the GPU outperforms the first generation MIC only on small-diameter graphs and is the slowest on the other kinds of graphs.

关键词： Betweenness centrality GPU Intel Xeon Phi Many-core processors Parallel graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A High-Performance Connected Components Implementation for GPUs 18

A High-Performance Connected Components Implementation for G...

引用

27th ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC)

作者： Jaiganesh, Jayadharini Burtscher, Martin Texas State Univ Dept Comp Sci San Marcos TX 78666 USA

ISBN: (纸本)9781450357852

Computing connected components is an important graph algorithm that is used, for example, in medicine, image processing, and biochemistry. This paper presents a fast connected-components implementation for GPUs called ECL-CC. It builds upon the best features of prior algorithms and augments them with GPU-specific optimizations. For example, it incorporates a parallelism-friendly version of pointer jumping to speed up union-find operations and uses several compute kernels to exploit the multiple levels of hardware parallelism. The resulting CUDA code is asynchronous and lock free, employs load balancing, visits each edge exactly once, and only processes edges in one direction. It is 1.8 times faster on average than the fastest prior GPU implementation running on a Titan X and faster on most of the eighteen real-world and synthetic graphs we tested.

关键词： connected components graph algorithm union-find parallelism GPU implementation

来源：评论

学校读者我要写书评

暂无评论

Designing a Heuristic Cross-Architecture Combination for Breadth-First Search 43

Designing a Heuristic Cross-Architecture Combination for Bre...

引用

43rd Annual International Conference on Parallel Processing (ICPP)

作者： You, Yang Bader, David A. Dehnavi, Maryam Mehri Tsinghua Univ Dept Comp Sci & Technol Beijing Peoples R China Georgia Inst Technol Sch Computat Sci & Engn Atlanta GA 30332 USA MIT Comp Sci & Artificial Intelligence Lab Boston MA USA

ISBN: (纸本)9781479956180

Breadth-First Search (BFS) is widely used in real-world applications including computational biology, social networks, and electronic design automation. The most effective BFS approach has been shown to be a combination of top-down and bottom-up approaches. Such hybrid techniques need to identify a switching point which is conventionally found through expensive trial-and-error and exhaustive search routines. We present an adaptive method based on regression analysis that enables dynamic switching at runtime with little overhead. We improve the performance of our method by exploiting popular heterogeneous platforms and efficiently design the approach for a given architecture. An 155x speedup is achieved over the standard top-down approach on GPUs. Our approach is the first to combine top-down and bottom-up across different architectures. Unlike combination on a single architecture, a mistuned switching point may significantly decrease the performance of cross-architecture combination. Our adaptive method can predict the switching point with high accuracy, leading to an 695x speedup compared the worst switching point.

关键词： graph algorithm Data-intensive Cross-architecture Optimization Knights Corner MIC Kepler K20x GPU Combination Regression Analysis

来源：评论

学校读者我要写书评

暂无评论

Applying the Safe-And-Complete Framework to Practical Genome Assembly 24

Applying the Safe-And-Complete Framework to Practical Genome...

引用

24th International Workshop on algorithms in Bioinformatics, WABI 2024

作者： Schmidt, Sebastian Toivonen, Santeri Medvedev, Paul Tomescu, Alexandru I. Department of Computer Science University of Helsinki Finland Department of Computer Science and Engineering The Pennsylvania State University University ParkPA United States Huck Institutes of the Life Sciences The Pennsylvania State University University ParkPA United States Department of Biochemistry and Molecular Biology The Pennsylvania State University University ParkPA United States

ISBN: (纸本)9783959773409

Despite the long history of genome assembly research, there remains a large gap between the theoretical and practical work. There is practical software with little theoretical underpinning of accuracy on one hand and theoretical algorithms which have not been adopted in practice on the other. In this paper we attempt to bridge the gap between theory and practice by showing how the theoretical safe-and-complete framework can be integrated into existing assemblers in order to improve contiguity. The optimal algorithm in this framework, called the omnitig algorithm, has not been used in practice due to its complexity and its lack of robustness to real data. Instead, we pursue a simplified notion of omnitigs (simple omnitigs), giving an efficient algorithm to compute them and demonstrating their safety under certain conditions. We modify two assemblers (wtdbg2 and Flye) by replacing their unitig algorithm with the simple omnitig algorithm. We test our modifications using real HiFi data from the D. melanogaster and the C. elegans genomes. Our modified algorithms lead to a substantial improvement in alignment-based contiguity, with negligible additional computational costs and either no or a small increase in the number of misassemblies. © Sebastian Schmidt, Santeri Toivonen, Paul Medvedev, and Alexandru I. Tomescu

关键词： Assembly evaluation Genome assembly graph algorithm HiFi sequencing data Omnitigs Safe-and-complete framework

来源：评论

学校读者我要写书评

暂无评论

A practical approach to generating route sketches 2

A practical approach to generating route sketches

引用

2nd ACM SIGSPATIAL International Workshop on MapInteraction, MapInteract 2014

作者： Luxen, Dennis Niklaus, Patrick Mapbox Inc. 1714 14th St NW Rear Entrance WashingtonDC20009 United States Karlsruhe Institute of Technology Am Fasanengarten 5 Karlsruhe76128 Germany

ISBN: (纸本)9781450331418

Online mapping and navigation services are a corner stone of the World Wide Web. While automatically generated car directions have gone from static data to user-specific customizations, automatically generated route guidance has stayed very much the same. And as such, it doesn't necessarily reflect the complexity of turns and may also be hard to use while traveling. We report on a practical and efficient technique for computing and presenting generalizations of routes, so-called sketches that compress a route and its guidance into an easy to comprehend and usable form by non-uniformly scaling and generalizing certain parts of the route. Our work draws from a sound theoretical foundation, is easy to implement, and gives very good results in practice.

关键词： algorithm engineering graph algorithm Route sketches

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for Large Scale Network Problems

Efficient Algorithms for Large Scale Network Problems

引用

作者： Huang, Dawei University of Michigan

学位级别：博士

In recent years, the growing scale of data has renewed our understanding of what is an efficient algorithm and poses many essential challenges for the algorithm designers. This thesis aims to improve our understanding of many algorithmic problems in this context. These include problems in communication complexity, matching theory, and approximate query processing for database systems. We first study the fundamental and well-known question of {SetIntersection} in communication complexity. We give a result that incorporates the error probability as an independent parameter into the classical trade-off between round complexity and communication complexity. We show that any $r$-round protocol that errs with error probability $2^{-E}$ requires $Omega(Ek^{1/r})$ bits of communication. We also give several almost matching upper bounds. In matching theory, we first study several generalizations of the ordinary matching problem, namely the $f$-matching and $f$-edge cover problem. We also consider the problem of computing a minimum weight perfect matching in a metric space with moderate expansion. We give almost linear time approximation algorithms for all these problems. Finally, we study the sample-based join problem in approximate query processing. We present a result that improves our understanding of the effectiveness and limitations in using sampling to approximate join queries and provides a guideline for practitioners in building AQP systems from a theory perspective.

关键词： graph algorithm communication complexity approximate query processing Computer Science Engineering

来源：评论

学校读者我要写书评

暂无评论

Priority queues with update and finding minimum spanning trees

引用

Information Processing Letters 1975年第3期4卷 53-57页

作者： Johnson, Donald B. Computer Science Department The Pennsylvania State University University Park PA 16802 United States

来源：评论

学校读者我要写书评

暂无评论

An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid

An algorithm for 1-bend embeddings of plane graphs in the tw...

引用

Brazilian Symposium on graphs, algorithms and Combinatorics

作者： Morgana, A de Mello, CP Sontacchi, G Univ Rome 1 Dipartimento Matemat I-000185 Rome Italy Univ Estadual Campinas Inst Computacao BR-3081970 Campinas SP Brazil

In this paper we characterize the class of plane graphs that can be embedded on the two-dimensional grid with at most one bend on each edge. In addition, we provide an algorithm that either detects a forbidden configu... 详细信息

关键词： planar embedding grid bend graph algorithm VLSI design

来源：评论

学校读者我要写书评

暂无评论

A dynamic programming algorithm for the maximum induced matching problem in permutation graphs 18

A dynamic programming algorithm for the maximum induced matc...

引用

9th International Symposium on Information and Communication Technology (SoICT)

作者： Viet-Dung Nguyen Ba-Thai Pham Viet-Hung Tran Phan-Thuan Do Korea Adv Inst Sci & Technol Daejeon South Korea Hanoi Univ Sci & Technol Hanoi Vietnam

ISBN: (纸本)9781450365390

For a finite undirected graph G = (V, E) and a positive integer k >= 1, an edge set M subset of E is a distance-k matching if the pairwise distance of edges in M is at least k in G. The special case k = 2 has been studied under the name maximum induced matching (MIM for short), i.e., a maximum matching which forms an induced subgraph in G. MIM arises in many applications, such as artificial intelligence, game theory, computer networks, VLSI design and marriage problems. In this paper, we design an O(n(2)) solution for finding MIM in permutation graphs based on a dynamic programming method on edges with the aid of the sweep line technique. Our result is better than the best known algorithm.

关键词： maximum induced matching permutation graph graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Fraternal Augmentations of graphs, Coloration and Minors

引用

Electronic Notes in Discrete Mathematics 2007年 28卷 223-230页

作者： Nešetřil, Jaroslav Ossona de Mendez, Patrice Department of Applied Mathematics Institute of Theoretical Computer Science Charles University Praha Czech Republic Centre d'Analyse Mathématiques Sociales - CNRS UMR 8557 Paris France

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇_r (G). We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings, a linear time algorithm to check subgraph isomorphism for a fixed pattern and homomorphism dualities. © 2007 Elsevier B.V. All rights reserved.

关键词： Bounded expansion Coloring graph algorithm Homomorphism Ramsey number Restricted duality Subgraph Isomorphism Transitive fraternal augmentation Tree-depth

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：