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

arXiv 2024年

作者： de Luca, Artur Back Fountoulakis, Kimon David R. Cheriton School of Computer Science University of Waterloo WaterlooON Canada

The execution of graph algorithms using neural networks has recently attracted significant interest due to promising empirical progress. This motivates further understanding of how neural networks can replicate reasoning steps with relational data. In this work, we study the ability of transformer networks to simulate algorithms on graphs from a theoretical perspective. The architecture we use is a looped transformer with extra attention heads that interact with the graph. We prove by construction that this architecture can simulate individual algorithms such as Dijkstra’s shortest path, Breadth- and Depth-First Search, and Kosaraju’s strongly connected components, as well as multiple algorithms simultaneously. The number of parameters in the networks does not increase with the input graph size, which implies that the networks can simulate the above algorithms for any graph. Despite this property, we show a limit to simulation in our solution due to finite precision. Finally, we show a Turing Completeness result with constant width when the extra attention heads are utilized. Copyright © 2024, The Authors. All rights reserved.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Fully Dynamic graph algorithms with Edge Differential Privacy

arXiv

引用

arXiv 2024年

作者： Raskhodnikova, Sofya Steiner, Teresa Anna Boston University BostonMA United States DTU Compute Technical University of Denmark Kongens Lyngby Denmark

We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates, where edges are inserted and deleted over time, and the algorithm is required to update the solution at every time step. Previous work has presented differentially private algorithms for many graph problems that can handle insertions only or deletions only (called partially dynamic algorithms) and obtained some hardness results for the fully dynamic setting. The only algorithms in the latter setting were for the edge count, given by Fichtenberger, Henzinger, and Ost (ESA’21), and for releasing the values of all graph cuts, given by Fichtenberger, Henzinger, and Upadhyay (ICML’23). We provide the first differentially private and fully dynamic graph algorithms for several other fundamental graph statistics (including the triangle count, the number of connected components, the size of the maximum matching, and the degree histogram), analyze their error, and show strong lower bounds on the error for all algorithms in this setting. Previously, only lower bounds for purely differentially private algorithms were known;our lower bounds give an exponential improvement in terms of the dependence on the number of time steps, while applying to algorithms satisfying pure as well as approximate differential privacy. We study two variants of edge differential privacy for fully dynamic graph algorithms: event-level and item-level. Under the former notion, two graph update sequences are considered neighboring if, roughly speaking, they differ in at most one update;under the latter notion, they can differ only in updates pertaining to one edge. Differential privacy requires that for any two neighboring inputs, the output distributions of the algorithm are close. We give upper and lower bounds on the error of both—event-level and item-level—fully dynamic algorithms for several fundamental graph problems. No fully dynamic algorithms that are privat

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A mixed nodal-mesh formulation of the PEEC method based on efficient graph algorithms

A mixed nodal-mesh formulation of the PEEC method based on e...

引用

2008 IEEE International Symposium on Electromagnetic Compatibility, Pages 1-536

作者： Giuseppe Miscione Giulio Antonini Daniele Frigioni Dipartimento di Ingegneria Elettrica e dell'Informazione Universita degli Studi dell'Aquila I-67040 Monteluco di Roio L'Aquila Italy

ISBN: (纸本)9781424416998

In this paper a new mixed nodal-mesh formulation of the PEEC method is proposed. Based on the hypothesis that charges reside only on the surface of conductors and that current density is solenoidal inside them, a novel scheme is developed fully exploiting the physical properties of charges and currents. It comes out that the presented approach allows to reduce the number of unknowns while preserving the accuracy. An elegant and efficient algorithm, based on graph theory, is proposed to automatically search independent loops on three dimensional rectangular grids such as those arising in volumetric PEEC formulation. The method is validated through numerical results that confirm the accuracy of the proposed formulation from DC-to-daylight and its capability to provide memory saving.

关键词： graph algorithms solenoidal CHARGES efficient algorithm graph theory conducting bodies Current density

来源：评论

学校读者我要写书评

暂无评论

graph partitioning algorithms for optimizing software deployment in mobile cloud computing

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2013年第2期29卷 451-459页

作者： Verbelen, Tim Stevens, Tim De Turck, Filip Dhoedt, Bart Ghent Univ IBBT Dept Informat Technol B-9050 Ghent Belgium

As cloud computing is gaining popularity, an important question is how to optimally deploy software applications on the offered infrastructure in the cloud. Especially in the context of mobile computing where software components could be offloaded from the mobile device to the cloud, it is important to optimize the deployment, by minimizing the network usage. Therefore we have designed and evaluated graph partitioning algorithms that allocate software components to machines in the cloud while minimizing the required bandwidth. Contrary to the traditional graph partitioning problem our algorithms are not restricted to balanced partitions and take into account infrastructure heterogenity. To benchmark our algorithms we evaluated their performance and found they produce 10%-40% smaller graph cut sizes than METIS 4.0 for typical mobile computing scenarios. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Distributed systems graph algorithms Deployment optimization Cloud computing Mobile computing

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Resource Allocation in Femtocell Networks using graph algorithms

Hierarchical Resource Allocation in Femtocell Networks using...

引用

IEEE International Conference on Communications

作者： Sanam Sadr Raviraj Adve University of Toronto Dept. of Elec. and Comp. Eng.

ISBN: (纸本)9781457720529

This paper presents a hierarchical approach to resource allocation in open-access femtocell networks. The major challenge in femtocell networks is interference management which in our system, based on the Long Term Evolution (LTE) standard, translates to which user should be allocated which physical resource block (or fraction thereof) from which femtocell access point (FAP). The globally optimal solution requires integer programming and is mathematically intractable. We propose a hierarchical three-stage solution: first, the load of each FAP is estimated considering the number of users connected to the FAP, their average channel gain and required data rates. Second, based on each FAP's load, the physical resource blocks (PRBs) are allocated to FAPs in a manner that minimizes the interference by coloring the modified interference graph. Finally, the resource allocation is performed at each FAP considering users' instantaneous channel gain. The two major advantages of this suboptimal approach are the significantly reduced computation complexity and the fact that the proposed algorithm only uses information that is already likely to be available at the nodes executing the relevant optimization step. The performance of the proposed solution is evaluated in networks based on the LTE standard.

关键词： Femtocell networks Resource utilization graph algorithms management of resources Long Term Evolution Hierarchical Consumers Local thermodynamic equilibrium Data transfer rates Integer Programming

来源：评论

学校读者我要写书评

暂无评论

Modified MapReduce Framework for Enhancing Performance of graph Based algorithms by Fast Convergence in Distributed Environment 3

Modified MapReduce Framework for Enhancing Performance of Gr...

引用

3rd International Conference on Advances in Computing, Communications and Informatics (ICACCI)

作者： Singhal, Hitesh Guddeti, Ram Mohana Reddy Natl Inst Technol Kamataka Dept Informat Technol Mangalore India

ISBN: (纸本)9781479930807

The amount of data which is produced is huge in current world and more importantly it is increasing exponentially. Traditional data storage and processing techniques are ineffective in handling such huge data [10]. Many real life applications require iterative computations in general and in particular used in most of machine learning and data mining algorithms over large datasets, such as web link structures and social network graphs. MapReduce is a software framework for easily writing applications which process large amount of data (multi-terabyte) in parallel on large clusters (thousands of nodes) of commodity hardware. However, because of batch oriented processing of MapReduce we are unable to utilize the benefits of MapReduce in iterative computations. Our proposed work is mainly focused on optimizing three factors resulting in performance improvement of iterative algorithms in MapReduce environment. In this paper, we address the key issues based on execution of tasks, the unnecessary creation of new task in each iteration and excessive shuffling of data in each iteration. Our preliminary experiments have shown promising results over the basic MapReduce framework. The comparative study with existing solutions based on MapReduce framework like HaLoop, has also shown better performance w.r.t algorithm run time and amount of data traffic over Hadoop Cluster.

关键词： MapReduce graph algorithms Iterative Computations

来源：评论

学校读者我要写书评

暂无评论

Exploring the Design Space of Static and Incremental graph Connectivity algorithms on GPUs 20

Exploring the Design Space of Static and Incremental Graph C...

引用

ACM International Conference on Parallel Architectures and Compilation Techniques (PACT)

作者： Hong, Changwan Dhulipala, Laxman Shun, Julian MIT CSAIL Cambridge MA 02139 USA CMU Pittsburgh PA USA

ISBN: (纸本)9781450380751

Connected components and spanning forest are fundamental graph algorithms due to their use in many important applications, such as graph clustering and image segmentation. GPUs are an ideal platform for graph algorithms due to their high peak performance and memory bandwidth. While there exist several GPU connectivity algorithms in the literature, many design choices have not yet been explored. In this paper, we explore various design choices in GPU connectivity algorithms, including sampling, linking, and tree compression, for both the static as well as the incremental setting. Our various design choices lead to over 300 new GPU implementations of connectivity, many of which outperform state-of-the-art. We present an experimental evaluation, and show that we achieve an average speedup of 2.47x speedup over existing static algorithms. In the incremental setting, we achieve a throughput of up to 48.23 billion edges per second. Compared to state-of-the-art CPU implementations on a 72-core machine, we achieve a speedup of 8.26-14.51x for static connectivity and 1.85-13.36x for incremental connectivity using a Tesla V100 GPU.

关键词： Connected components graph algorithms GPU algorithms Spanning forest

来源：评论

学校读者我要写书评

暂无评论

vLock: Lock Virtualization Mechanism for Exploiting Fine-grained Parallelism in graph Traversal algorithms

vLock: Lock Virtualization Mechanism for Exploiting Fine-gra...

引用

11th IEEE/ACM International Symposium on Code Generation and Optimization (CGO)

作者： Yan, Jie Tan, Guangming Zhang, Xiuxia Yao, Erlin Sun, Ninghui Chinese Acad Sci Inst Comp Technol State Key Lab Comp Architecture Beijing 100864 Peoples R China

ISBN: (纸本)9781467355254;9781467355247

For graph traversal applications, fine synchronization is required to exploit massive fine parallelism. However, in the conventional solution using fine-grained locks, locks themselves suffer huge memory cost as well as poor locality for inherent irregular access to vertices. In this paper, we propose a novel fine lock solution-vLock. The key idea is lock virtualization that maps the huge logical lock space to a much smaller physical lock space that can reside in cache during the program life cycle. Lock virtualization effectively reduces lock incurred overheads of both memory cost and cache misses. It also achieves high usability in legacy graph programs, as from users's view vLock is the same as lock methods in Pthreads. We implement vLock as a Pthreads-like library and evaluate its performance in four classical graph algorithms (BFS,SSSP,CC,PageRank). Experiments on a SMP system with two Intel Westemere six-core processors show that, compared to conventional fine locks, vLock significantly reduces locks' cache misses and has competitive performance. Particularly, PageRank with vLock has about 20% performance improvement.

关键词： graph algorithms Fine Synchronization vLock

来源：评论

学校读者我要写书评

暂无评论

The Comparison of Large-Scale graph Processing algorithms Implementation Methods for Intel KNL and NVIDIA GPU 3rd

The Comparison of Large-Scale Graph Processing Algorithms Im...

引用

3rd Russian Supercomputing Days (RuSCDays)

作者： Afanasyev, Ilya Voevodin, Vladimir Lomonosov Moscow State Univ Moscow Russia

ISBN: (纸本)9783319712543;9783319712550

The paper describes implementation approaches to large-graph processing on two modern high-performance computational platforms: NVIDIA GPU and Intel KNL. The described approach is based on a deep a priori analysis of algorithm properties that helps to choose implementation method correctly. To demonstrate the proposed approach, shortest paths and strongly connected components computation problems have been solved for sparse graphs. The results include detailed description of the whole algorithm's development cycle: from algorithm information structure research and selection of efficient implementation methods, suitable for the particular platforms, to specific optimizations for each of the architectures. Based on the joint analysis of algorithm properties and architecture features, a performance tuning, including graph storage format optimizations, efficient usage of the memory hierarchy and vectorization is performed. The developed implementations demonstrate high performance and good scalability of the proposed solutions. In addition, a lot of attention was paid to profiling implemented algorithms with NVIDIA Visual Profiler and Intel (R) VTune (TM) Amplifier utilities. This allows current paper to present a fair comparison, demonstrating advantages and disadvantages of each platform for large-scale graph processing.

关键词： graph algorithms GPU KNL CUDA Vectorization SSSP SCC Large-scale graph processing

来源：评论

学校读者我要写书评

暂无评论

Applications of graph Segmentation algorithms For Quantitative Genomic Analyses

Applications of Graph Segmentation Algorithms For Quantitati...

引用

作者： Gunady, Mohamed University of Maryland

学位级别：博士

There is a growing interest in utilizing graph formulations and graph-based algorithms in different subproblems of genomic analysis. Since graphs provide a natural and efficient representation of sequences of data where some structural relationships are observed within the data, we study some graph applications in quantitative analysis of typical RNA-seq and Whole Genome Sequencing pipelines. Analysis of differential alternative splicing from RNA-seq data is complicated by the fact that many RNA-seq reads map to multiple transcripts, besides, the annotated transcripts are often a small subset of the possible transcripts of a gene. This work describes Yanagi, a tool for segmenting transcriptomes to create a library of maximal L-disjoint segments from a complete transcriptome annotation. That segment library preserves transcriptome substrings and structural relationships between transcripts while eliminating unnecessary sequence duplications. First, we formalize the concept of transcriptome segmentation and propose an efficient algorithm for generating segment libraries. The resulting segment sequences can be used with pseudo-alignment tools to quantify gene expression and alternative splicing at the segment level and provide gene-level visualization of the segments for more interpretability. The notion of transcript segmentation as introduced here and implemented in Yanagi opens the door for the application of lightweight, ultra-fast pseudo-alignment algorithms in a wide variety of RNA-seq analyses. Furthermore, we show how transcriptome quantification can be performed from segment-level statistics. We present an EM algorithm that uses segment counts as features to estimate transcripts relative abundances in a way that maximizes the likelihood of the observed sequenced data. Then we tackle the problem of quantification in an incomplete annotation setting. We propose an assembly-free correction procedure that reduces bias in the estimated abundances of the annotate

关键词： Bioinformatics Computer science Alternative Splicing graph algorithms Population Reference graph RNA-seq scRNA-seq Transcriptome Quantification

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：