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

DHLP 1&2: Giraph based distributed label propagation algorithms on heterogeneous drug-related networks

EXPERT SYSTEMS WITH APPLICATIONS 2020年 159卷

作者： Maleki, Erfan Farhangi Ghadiri, Nasser Shahreza, Maryam Lotfi Maleki, Zeinab Isfahan Univ Technol Dept Elect & Comp Engn Esfahan *** Iran Univ Delaware Dept Comp & Informat Sci Newark DE 19711 USA Univ Shahreza Dept Comp Engn Shahreza *** Iran

Background and objective: Heterogeneous complex networks are large graphs consisting of different types of nodes and edges. The knowledge extraction from these networks is complicated. Moreover, the scale of these networks is steadily increasing. Thus, scalable methods are required. Methods: In this paper, two distributed label propagation algorithms for heterogeneous networks, namely DHLP-1 and DHLP-2 have been introduced. Biological networks are one type of the heterogeneous complex networks. As a case study, we have measured the efficiency of our proposed DHLP-1 and DHLP-2 algorithms on a biological network consisting of drugs, diseases, and targets. The subject we have studied in this network is drug repositioning but our algorithms can be used as general methods for heterogeneous networks other than the biological network. Results: We compared the proposed algorithms with similar non-distributed versions of them namely MINProp and Heter-LP. The experiments revealed the good performance of the algorithms in terms of running time and accuracy. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： distributed graph processing Heterogeneous label propagation Complex networks Semi-supervised learning Drug repositioning Apache Giraph

来源：评论

学校读者我要写书评

暂无评论

Adaptive Partition Migration for Irregular graph Algorithms on Elastic Resources 12

Adaptive Partition Migration for Irregular Graph Algorithms ...

引用

12th IEEE International Conference on Cloud Computing (IEEE CLOUD) held as Part of IEEE World Congress on Services (IEEE SERVICES)

作者： Dindokar, Ravikant Simmhan, Yogesh Indian Inst Sci Dept Computat & Data Sci Bangalore 560012 Karnataka India

ISBN: (纸本)9781728127057

Component-centric graph programming models allow distributed graph algorithms to be composed, and executed in an iterative manner on commodity clusters and Clouds. graphs are partitioned and statically placed on a fixed number of machines before execution. However, many graph algorithms have an irregular execution behavior across partitions in different iterations, which causes resource under-utilization. We propose two strategies, First Fit Decreasing with Migration Planning (FFDMP) and MinMax, for adaptive partition placement onto an elastic number of Cloud resources for such irregular algorithms. For each iteration, our strategies decide the number of hosts and the placement of partitions on them to balance the compute load, and enact this by migrating partitions between hosts at iteration boundaries. Unlike others, our strategies actively consider the time and cost penalties for moving partitions between hosts, and reduce the overall cost of execution while mitigating any increase in makespan. We implement these strategies on our GoFFish subgraph-centric graph processing platform, and evaluate them for performing Breadth First Search (BFS) on large real-world graphs with 10(7) - 10(9) edges. Our results show that the proposed strategies reduce the median resource cost by 13 - 38% when compared to a static placement, increase the median makespan by 1 - 33%, which is strictly bound by a given time budget, and also out-perform existing baseline scheduling algorithms from literature.

关键词： Adaptive scaling distributed graph processing Elastic scheduling Non stationary graph algorithms Partition migration

来源：评论

学校读者我要写书评

暂无评论

graphOpt: a Framework for Automatic Parameters Tuning of graph processing Frameworks

GraphOpt: a Framework for Automatic Parameters Tuning of Gra...

引用

IEEE International Conference on Big Data (Big Data)

作者： Twaty, Muaz Ghrab, Amine Skhiri, Sabri EURA NOVA Dept Res & Dev Mont St Guibert Belgium

ISBN: (纸本)9781728108582

Finding the optimal configuration of a black-box system is a difficult problem that requires a lot of time and human labor. Big data processing frameworks are among the increasingly popular systems whose tuning is a complex and time consuming. The challenge of automatically finding the optimal parameters of big data frameworks attracted a lot of research in recent years. Some of the studies focused on optimizing specific frameworks such as distributed stream processing [1] [2], or finding the best cloud configurations [3], while others proposed general services for optimizing any black-box system [4]. In this paper, we introduce a new use case in the domain of automatic parameter tuning: optimizing the parameters of distributed graph processing frameworks. This task is notably difficult given the particular challenges of distributed graph processing that include the graph partitioning and the iterative nature of graphs algorithms. To address this challenge, we designed and implemented graphOpt: an efficient and scalable black-box optimization framework that automatically tunes distributed graph processing frameworks. graphOpt implements slate-of-the-art optimization algorithms and introduces a new hill-climbing-based search algorithm. These algorithms are used to optimize the performance of two major graph processing frameworks: Giraph and graphX. Extensive experiments were run on graphOpt using multiple graph benchmarks to evaluate its performance and show that it provides up to 47.8% improvement compared to random search and an average improvement of up to 5.7%.

关键词： distributed graph processing Parameters Tuning Black-box Optimization

来源：评论

学校读者我要写书评

暂无评论

MultiLyra: Scalable distributed Evaluation of Batches of Iterative graph Queries

MultiLyra: Scalable Distributed Evaluation of Batches of Ite...

引用

IEEE International Conference on Big Data (Big Data)

作者： Mazloumi, Abbas Jiang, Xiaolin Gupta, Rajiv Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA

ISBN: (纸本)9781728108582

graph analytics is being increasingly used for analyzing large scale networks representing entities and relationships in many domains. Various distributed graph processing frameworks have been developed to deliver scalable performance for evaluation of individual iterative graph queries. In practice though, we may need to evaluate many queries. In this paper we develop MultiLyra, a distributed framework that efficiently evaluates a batch of graph queries. To deliver high performance, this system is designed to amortize the communication and synchronization costs of distributed query evaluation across multiple queries. Our experiments with MultiLyra for four iterative algorithms on a cluster of four 32-core machines show the following. Basic hatching technique for amortizing communication and synchronization costs yield maximum speedups ranging from 3.08x to 5.55x across different batch sizes, algorithms and input graphs. After employing optimizations that improve scalability of expensive phases and perform reuse across the distributed computation, the improved maximum speedups range from 7.35x to 11.86x. MultiLyra also delivers superior scalahilty than the Quegel batch processing system.

关键词： distributed graph processing Query Batching Reuse Redundancy Elimination

来源：评论

学校读者我要写书评

暂无评论

Scale Up or Scale Out for graph processing?

引用

IEEE INTERNET COMPUTING 2018年第3期22卷 72-78页

作者： Lin, Jimmy Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON Canada

This column explores a simple question: scale up or scale out for graph processing? Should we simply throw "beefier" individual multi-core, large-memory machines at graph processing tasks and focus on developing more efficient multi-threaded algorithms, or are investments in distributed graph processing frameworks and accompanying algorithms worthwhile? For rhetorical convenience, I adopt customary definitions, referring to the former as scale up and the latter as scale out. Under what circumstances should we prefer one approach over the other?

关键词： graph Theory Mathematics Computing Multiprocessing Systems Multi Threading Large Memory Machines graph processing Tasks distributed graph processing Multithreaded Algorithms Multicore graphical User Interfaces Big Data Random Access Memory Memory Management Internet graph processing Big Data

来源：评论

学校读者我要写书评

暂无评论

UniWalk: Unidirectional Random Walk Based Scalable SimRank Computation over Large graph

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2018年第5期30卷 992-1006页

作者： Song, Junshuai Luo, Xiongcai Gao, Jun Zhou, Chang Wei, Hu Yu, Jeffery Xu Peking Univ Minist Educ Key Lab High Confidence Software Technol Beijing 100080 Peoples R China Peking Univ Sch EECS Beijing 100080 Peoples R China Alibaba Grp Hangzhou 311121 Zhejiang Peoples R China Chinese Univ Hong Kong Dept Syst Engn Sha Tin Hong Kong Peoples R China

SimRank is an important measure of vertex-pair similarity according to the structure of graphs. Although progress has been achieved, existing methods still face challenges to handle large graphs. Besides huge index construction and maintenance cost, existing methods may require considerable search space and time overheads in the online SimRank query. In this paper, we design a Monte Carlo based method, UniWalk, to enable the fast top-k SimRank computation over large undirected graphs. UniWalk directly locates the top-k similar vertices for any single source vertex u via R sampling paths originating from u, which avoids selecting candidate vertex set C and the following OojCjRthorn bidirectional sampling paths. We also devise a path enumeration strategy to improve the SimRank precision by using path probabilities instead of path frequencies when sampling, a space-efficient method to reduce intermediate results, and a path-sharing strategy to lower the redundant path sampling cost for multiple source vertices. Furthermore, we extend UniWalk to existing distributed graph processing frameworks to improve its scalability. We conduct extensive experiments to illustrate that UniWalk has high scalability, and outperforms the state-of-the-art methods by orders of magnitude.

关键词： SimRank Monte Carlo random walk distributed graph processing

来源：评论

学校读者我要写书评

暂无评论

graph: Traffic-Aware graph processing

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2018年第6期29卷 1289-1302页

作者： Mayer, Christian Tariq, Muhammad Adnan Mayer, Ruben Rothermel, Kurt Univ Stuttgart Inst Parallel & Distributed Syst D-70174 Stuttgart Germany FAST Natl Univ Comp Sci & Emerging Sci Dept Comp Sci Islamabad Pakistan

distributed graph processing systems such as Pregel, Powergraph, or graphX gained popularity due to their superior performance of data analytics on graph-structured data. These systems employ partitioning algorithms to parallelize graph analytics while minimizing inter-partition communication. Recent partitioning algorithms, however, unrealistically assume a uniform and constant amount of data exchanged between graph vertices (i.e., uniform vertex traffic) and homogeneous network costs between workers hosting the graph partitions. This leads to suboptimal partitioning decisions and inefficient graph processing. To this end, we developed graph, the first graph processing system using vertex-cut graph partitioning that considers both, diverse vertex traffic and heterogeneous network costs. The main idea is to avoid frequent communication over expensive network links using an adaptive edge migration strategy. Our evaluations show an improvement of 10 percent in graph processing latency and 60 percent in communication costs compared to state-of-the-art partitioning approaches.

关键词： distributed graph processing partitioning vertex-cut heterogeneous traffic geo-distributed adaptive workload architecture network streaming partitioning communication

来源：评论

学校读者我要写书评

暂无评论

ADWISE: Adaptive Window-based Streaming Edge Partitioning for High-Speed graph processing 38

ADWISE: Adaptive Window-based Streaming Edge Partitioning fo...

引用

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

作者： Mayer, Christian Mayer, Ruben Tariq, Muhammad Adnan Geppert, Heiko Laich, Larissa Rieger, Lukas Rothermel, Kurt Univ Stuttgart Inst Parallel & Distributed Syst Stuttgart Germany

ISBN: (纸本)9781538668719

In recent years, the graph partitioning problem gained importance as a mandatory preprocessing step for distributed graph processing on very large graphs. Existing graph partitioning algorithms minimize partitioning latency by assigning individual graph edges to partitions in a streaming manner at the cost of reduced partitioning quality. However, we argue that the mere minimization of partitioning latency is not the optimal design choice in terms of minimizing total graph analysis latency, i.e., the sum of partitioning and processing latency. Instead, for complex and long-running graph processing algorithms that run on very large graphs, it is beneficial to invest more time into graph partitioning to reach a higher partitioning quality - which drastically reduces graph processing latency. In this paper, we propose ADWISE, a novel window-based streaming partitioning algorithm that increases the partitioning quality by always choosing the best edge from a set of edges for assignment to a partition. In doing so, ADWISE controls the partitioning latency by adapting the window size dynamically at run-time. Our evaluations show that ADWISE can reach the sweet spot between graph partitioning latency and graph processing latency, reducing the total latency of partitioning plus processing by up to 23 47 percent compared to the state-of-the-art.

关键词： graph partitioning vertex-cut edge partitioning adaptive window streaming distributed graph processing

来源：评论

学校读者我要写书评

暂无评论

Scalable Breadth-First Search on a GPU Cluster 32

Scalable Breadth-First Search on a GPU Cluster

引用

32nd IEEE International Parallel and distributed processing Symposium (IPDPS)

作者： Pan, Yuechao Pearce, Roger Owens, John D. Univ Calif Davis Davis CA 95616 USA Lawrence Livermore Natl Lab Livermore CA USA

ISBN: (纸本)9781538643686

On a GPU cluster, the ratio of high computing power to communication bandwidth makes scaling breadth-first search (BFS) on a scale-free graph extremely challenging. By separating high and low out-degree vertices, we present an implementation with scalable computation and a model for scalable communication for BFS and direction-optimized BFS. Our communication model uses global reduction for high-degree vertices, and point-to-point transmission for low-degree vertices. Leveraging the characteristics of degree separation, we reduce the graph size to one third of the conventional edge list representation. With several other optimizations, we observe linear weak scaling as we increase the number of GPUs, and achieve 259.8 GTEPS on a scale-33 graph500 RMAT graph with 124 GPUs on the latest CORAL early access system.

关键词： multi GPU distributed graph processing BFS

来源：评论

学校读者我要写书评

暂无评论

Fast and Scalable distributed Loopy Belief Propagation on Real-World graphs 18

Fast and Scalable Distributed Loopy Belief Propagation on Re...

引用

11th ACM International Conference on Web Search and Data Mining

作者： Jo, Saehan Yoo, Jaemin Kang, U. Seoul Natl Univ Seoul South Korea

ISBN: (纸本)9781450355810

Given graphs with millions or billions of vertices and edges, how can we efficiently make inferences based on partial knowledge? Loopy Belief Propagation (LBP) is a graph inference algorithm widely used in various applications including social network analysis, malware detection, recommendation, and image restoration. The algorithm calculates approximate marginal probabilities of vertices in a graph within a linear running time proportional to the number of edges. However, when it comes to real-world graphs with millions or billions of vertices and edges, this cost overwhelms the computing power of a single machine. Moreover, this kind of large-scale graphs does not fit into the memory of a single machine. Although several distributed LBP methods have been proposed, previous works do not consider the properties of real-world graphs, especially the effect of power-law degree distribution on LBP. Therefore, our work focuses on developing a fast and scalable LBP for such large real-world graphs on distributed environment. In this paper, we propose DLBP, a distributed Loopy Belief Propagation algorithm which efficiently computes LBP in a distributed manner across multiple machines. By setting the correct convergence criterion and carefully scheduling the computations, DLBP provides up to 10.7x speed up compared to standard distributed LBP. We show that DLBP demonstrates near-linear scalability with respect to the number of machines as well as the number of edges.

关键词： real-world graphs distributed graph processing loopy belief propagation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：