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

17th European Conference on Computer Systems (EuroSys)

作者： Baranawal, Animesh Simmhan, Yogesh Indian Inst Sci Bengaluru India

ISBN: (纸本)9781450391627

Temporal graphs assign lifespans to their vertices, edges and attributes. Large temporal graphs are common for finding the shortest paths in transit networks and contact tracing for COVID-19. graph programming abstractions like Interval-centric Computing Model (ICM) extend Google's Pregel model to intuitively compose and execute time-dependent graph algorithms in a distributed environment. However, the benefits of easier algorithmic design in ICM are offset by performance bottlenecks in its TimeWarp shuffle and messaging phases. Here, we design several optimizations to ICM to reduce these overheads. We propose local optimizations within a vertex execution by unrolling messages before TimeWarp (LU), and deferring messaging till all local computations complete (DS). We also temporally partition the interval graph into windows (WICM) to flatten the execution load. We offer a proof of equivalence between ICM and these techniques. Our detailed empirical evaluation for six real-world graphs with up to 133 M vertices, 5.5 B edges and 365 time-points, for six temporal traversal algorithms executing on a commodity cluster with 8 nodes, shows that LU, DS and WICM together significantly reduce the average algorithm runtime by approximate to 61% (approximate to 15 mins) over ICM, and reduce message communication by approximate to 38%(approximate to 3.2 B) on average.

关键词： temporal graphs distributed graph processing

来源：评论

学校读者我要写书评

暂无评论

NEPG: Partitioning Large-Scale Power-Law graphs 21st

NEPG: Partitioning Large-Scale Power-Law Graphs

引用

21st International Conference on Algorithms and Architectures for Parallel processing (ICA3PP)

作者： Si, Jiaqi Gan, Xinbiao Bai, Hao Dong, Dezun Pang, Zhengbin Natl Univ Def Technol Coll Comp Changsha Peoples R China

ISBN: (纸本)9783030953911;9783030953904

We propose Neighbor Expansion on power-law graph(NEPG), a distributed graph partitioning method based on a specific power-law graph that offers both good scalability and high partitioning quality. NEPG is based on a heuristic method, Neighbor Expansion, which constructs the different partitions and greedily expands from vertices selected randomly. NEPG improves the partitioning quality by selecting the vertices according to the properties of the power-law graph. We put forward theoretical proof that NEPG can reach the higher upper bound in partitioning quality. The empirical evaluation demonstrates that compared with the state-of-the-art distributed graph partitioning algorithms, NEPG significantly improved partitioning quality while reducing the graph construction time. The performance evaluation demonstrates that the time efficiency of the proposed method outperforms the existing algorithms.

关键词： graph partitioning distributed graph processing Power-law graph Heuristic algorithm Experimental evaluation

来源：评论

学校读者我要写书评

暂无评论

VSIM: distributed local structural vertex similarity calculation on big graphs

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2021年 158卷 29-46页

作者： Wang, Zhaokang Wang, Shen Li, Junhong Yuan, Chunfeng Gu, Rong Huang, Yihua Nanjing Univ State Key Lab Novel Software Technol Nanjing Peoples R China

In many graph analytical applications, the local structural vertex similarity calculation is an essential prerequisite for advanced graph mining. The similarity calculation finds out all the similar vertex pairs whose local structural similarity scores (like the number of common neighbors, and the Jaccard index of adjacency sets) are above a given threshold. The real-world applications use a wide range of similarity thresholds. However, the existing distributed methods for the problem only optimize for either high thresholds (> 0.7) or low thresholds (< 0.1). To overcome the drawback, we propose a new distributed vertex similarity calculation framework VSIM that is efficient under a broad range of thresholds. VSIM processes static undirected graphs with local structural similarity scores that measure the similarity between vertices based on the first-order topology information. VSIM generates a similarity calculation task for every vertex in the graph and conducts all the tasks in parallel on a distributed computing platform along with a distributed key-value store. Each task finds vertices similar to a given center vertex with two task execution modes. The two modes optimize for high and low thresholds, respectively. Each task picks the suitable mode adaptively according to cost estimation models. We also propose an efficient implementation for VSIM on Apache Spark, with three optimization techniques to reduce communication costs and balance workloads on power-law graphs. The experimental evaluation shows that VSIM outperforms the state-of-the-art distributed methods by up to 67x speedup. VSIM can achieve near-linear node scalability in low-threshold and small cache scenarios. (C) 2021 Elsevier Inc. All rights reserved.

关键词： distributed graph processing graph data engineering Task-parallel algorithm Vertex similarity calculation Local structural similarity score

来源：评论

学校读者我要写书评

暂无评论

SQL-G: Efficient graph Analytics by SQL

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2021年第5期33卷 2237-2251页

作者： Zhao, Kangfei Su, Jiao Yu, Jeffrey Xu Zhang, Hao Chinese Univ Hong Kong Sha Tin Hong Kong Peoples R China

Querying graphs and conducting graph analytics become important in data processing since many real applications are dealing with massive graphs, such as online social networks, Semantic Web, knowledge graphs, etc. Over the years, many distributed graph processing systems have been developed to support graph analytics using various programming models, and many graph querying languages have been proposed. A natural question that arises is how to integrate graph data and traditional non-graph data in a distributed system for users to conduct analytics. There are two issues. One issue is related to expressiveness on how to specify graph analytics as well as data analytics by a querying language. The other issue is related to efficiency on how to process analytics in a distributed system. For the first issue, SQL is a best candidate, since SQL is a well-accepted language for data processing. We concentrate on SQL for graph analytics. Our early work shows that graph analytics can be supported by SQL in a way from "semiring + while" to "relational algebra + while" via the enhanced recursive SQL queries. In this article, we focus on the second issue on how to process such enhanced recursive SQL queries based on the GAS (Gather-Apply-Scatter) model under which efficient graph processing systems can be developed. To demonstrate the efficiency, we implemented a system by tightly coupling Spark SQL and graphX on Spark which is one of the most popular in-memory data-flow processing platforms. First, we enhance Spark SQL by adding the capability of supporting the enhanced recursive SQL queries for graph analytics. In this regard, graph analytics can be processed using a distributed SQL engine alone. Second, we further propose new transformation rules to optimize/translate the operations for recursive SQL queries to the operations by graphX. In this regard, graph analytics by SQL can be processed in a similar way as done by a distributed graph processing system using the APIs prov

关键词： Structured Query Language Sparks Algebra Engines Programming distributed databases Data processing graph analytics distributed graph processing SQL recursive query spark

来源：评论

学校读者我要写书评

暂无评论

HUGE: An Efficient and Scalable Subgraph Enumeration System 21

HUGE: An Efficient and Scalable Subgraph Enumeration System

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Yang, Zhengyi Lai, Longbin Lin, Xuemin Hao, Kongzhang Zhang, Wenjie Univ New South Wales Sydney NSW Australia Alibaba Grp Hangzhou Peoples R China

ISBN: (纸本)9781450383431

Subgraph enumeration is a fundamental problem in graph analytics, which aims to find all instances of a given query graph on a large data graph. In this paper, we propose a system called HUGE to efficiently process subgraph enumeration at scale in the distributed context. HUGE features 1) an optimiser to compute an advanced execution plan without the constraints of existing works;2) a hybrid communication layer that supports both pushing and pulling communication;3) a novel two-stage execution mode with a lock-free and zero-copy cache design;4) a BFS/DFS-adaptive scheduler to bound memory consumption;and 5) two-layer intra- and inter-machine load balancing. HUGE is generic such that all existing distributed subgraph enumeration algorithms can be plugged in to enjoy automatic speed up and bounded-memory execution.

关键词： subgraph enumeration distributed graph processing join processing cache dynamic scheduling load balancing

来源：评论

学校读者我要写书评

暂无评论

TriPoll: Computing Surveys of Triangles in Massive -Scale Temporal graphs with Metadata 21

TriPoll: Computing Surveys of Triangles in Massive -Scale Te...

引用

International Conference for High Performance Computing, Networking, Storage and Analysis (SC21)

作者： Steil, Trevor Reza, Tahsin Iwabuchi, Keita Priest, Benjamin W. Sanders, Geoffrey Pearce, Roger Lawrence Livermore Natl Lab LLNL Ctr Appl Sci Comp CASC Livermore CA 94550 USA

ISBN: (纸本)9781450384421

Understanding the higher-order interactions within network data is a key objective of network science. Surveys of metadata triangles (or patterned 3 -cycles in metadata-enriched graphs) are often of interest in this pursuit. In this work, we develop Tr i Poll, a prototype distributed HPC system capable of surveying triangles in massive graphs containing metadata on their edges and vertices. We contrast our approach with much of the prior effort on triangle analysis, which often focuses on simple triangle counting, usually in simple graphs with no metadata. We assess the scalability of Tr iPoll when surveying triangles involving metadata on real and synthetic graphs with up to hundreds of billions of edges. We utilize communication-reducing optimizations to demonstrate a triangle counting task on a 224 billion edge web graph in approximately half of the time of competing approaches, while additionally supporting metadata-aware capabilities.

关键词： distributed graph processing asynchronous communication

来源：评论

学校读者我要写书评

暂无评论

Hybrid Edge Partitioner: Partitioning Large Power-Law graphs under Memory Constraints 21

Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs...

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Mayer, Ruben Jacobsen, Hans-Arno Tech Univ Munich Munich Germany Univ Toronto Toronto ON Canada

ISBN: (纸本)9781450383431

distributed systems that manage and process graph-structured data internally solve a graph partitioning problem to minimize their communication overhead and query run-time. Besides computational complexity-optimal graph partitioning is NP-hard-another important consideration is the memory overhead. Real-world graphs often have an immense size, such that loading the complete graph into memory for partitioning is not economical or feasible. Currently, the common approach to reduce memory overhead is to rely on streaming partitioning algorithms. While the latest streaming algorithms lead to reasonable partitioning quality on some graphs, they are still not completely competitive to in-memory partitioners. In this paper, we propose a new system, Hybrid Edge Partitioner (HEP), that can partition graphs that fit partly into memory while yielding a high partitioning quality. HEP can flexibly adapt its memory overhead by separating the edge set of the graph into two sub-sets. One sub-set is partitioned by NE++, a novel, efficient in-memory algorithm, while the other sub-set is partitioned by a streaming approach. Our evaluations on large real-world graphs show that in many cases, HEP outperforms both in-memory partitioning and streaming partitioning at the same time. Hence, HEP is an attractive alternative to existing solutions that cannot fine-tune their memory overheads. Finally, we show that using HEP, we achieve a significant speedup of distributed graph processing jobs on Spark/graphX compared to state-of-the-art partitioning algorithms.

关键词： graph partitioning distributed graph processing

来源：评论

学校读者我要写书评

暂无评论

Practical and high-quality partitioning algorithm for large-scale and time-evolving graphs

引用

KNOWLEDGE-BASED SYSTEMS 2021年 227卷 107211-107211页

作者： Luo, Xiangyu Luo, Yingxiao Xin, Gang Gui, Xiaolin Wang, Jia Guo, Cheng Xian Univ Sci & Technol Inst Syst Secur & Control Sch Comp Sci & Technol Xian Peoples R China Xi An Jiao Tong Univ Sch Elect & Informat Engn Xian Peoples R China AVIC Comp Tech Res Inst Xian Peoples R China Xian Inst Appl Opt Xian Peoples R China

With the appearance of widespread large-scale graph data, distributed graph processing grows in popularity. In order to store and analyze a large-scale graph in a distributed manner, the graph should be properly partitioned in advance. Although the partitioning of static graphs has been sufficiently investigated, the emerging graphs nowadays are typically dynamic or time-evolving. State-of-the-art partitioning algorithms for such large-scale and time-evolving graphs either are impractical because of the complexity caused by the global optimization or sacrifice partitioning quality due to a huge number of cross partition edges. This paper investigates the problem and proposes a new practical and high-quality graph partitioning algorithm. First, graph updates accumulated in a time interval are expressed as a delta graph. Second, vertices in the delta graph are classified into several subsets based on a non-overlapping community detection method. Third, vertices in the same subset are assigned to a properly chosen partition as a whole. The chosen partition is lightly loaded as well as closely related with vertices in the subset. Experimental results show that compared with the widely used hash-based and heuristic-based partitioning algorithms, our proposed algorithm gains significant decrease in terms of the number of cross partition edges while maintaining a similar level of load balance. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Time-evolving graph graph partitioning distributed graph processing Cross partition edge Load balance

来源：评论

学校读者我要写书评

暂无评论

GraBi: Communication-Efficient andWorkload-Balanced Partitioning for Bipartite graphs 20

GraBi: Communication-Efficient andWorkload-Balanced Partitio...

引用

49th International Conference on Parallel processing (ICPP)

作者： Sheng, Feng Cao, Qiang Jiang, Hong Yao, Jie HUST KLISS WNLO Wuhan Hubei Peoples R China Univ Texas Arlington Arlington TX 76019 USA HUST Sch Comp Sci & Tech Wuhan Hubei Peoples R China

ISBN: (纸本)9781450388160

Machine Learning and Data Mining (MLDM) applications, such as recommendation and topic modeling, generally represent their input data in bipartite graphs with two disjoint vertex-subsets connected only by edges between them. Despite the prevalence of bipartite graphs, existing graph partitioning frameworks have rarely sufficiently exploited their unique structures, especially the highly lopsided subset sizes and extremely skewed vertex degrees. As a result of poor partitioning quality, problems, particularly of high communication cost and severe workload imbalance, arise during subsequent computation over these bipartite graphs in distributed environments such as datacenters or HPC systems, significantly hampering the performance of MLDM applications. In this paper, we approach these problems by communication-efficient and workload-balanced partitioning of bipartite graphs, which fully exploits the vertex vectorization in MLDM algorithms and inherent asymmetry in bipartite graphs. To this end, we present GraBi, a two-stage partitioning framework that partitions a bipartite graph first vertically and then horizontally. The first partitioning stage divides each vectored vertex into multiple vertex-chunks such that the bipartite graph is vertically partitioned into multiple layers, to strike an appropriate tradeoff between inter- and intra-vertex communication. In the second partitioning stage, for each layer, the vertex-chunks in the larger vertex-subset are first assigned to nodes, to minimize vertex replicas. To be specific, these vertex-chunks are horizontally decomposed into one or more sub-chunks with an upper-bounded number of edges, and then the sub-chunks are evenly assigned over nodes of a distributed system using a set of hash functions, to achieve workload balance among all computing nodes. GraBi is a lightweight partitioning framework for bipartite graphs, and can be generalizable to most MLDM applications. Our evaluation, driven by real-world bipartite gr

关键词： distributed graph processing graph partitioning bipartite graphs

来源：评论

学校读者我要写书评

暂无评论

BEAD: Batched Evaluation of Iterative graph Queries with Evolving Analytics Demands 8

BEAD: Batched Evaluation of Iterative Graph Queries with Evo...

引用

8th IEEE International Conference on Big Data (Big Data)

作者： Mazloumi, Abbas Xu, Chengshuo Zhao, Zhijia Gupta, Rajiv Univ Calif Riverside Comp Sci & Engn Riverside CA 92521 USA

ISBN: (纸本)9781728162515

Simultaneous evaluating a batch of iterative graph queries on a distributed system enables amortization of high communication and computation costs across multiple queries. As demonstrated by our prior work on MultiLyra [BigData'19], batched graph query processing can deliver significant speedups and scale up to batch sizes of hundreds of queries. In this paper, we greatly expand the applicable scenarios for batching by developing BEAD, a system that supports Batching in the presence of Evolving Analytics Demands. First, BEAD allows the graph data set to evolve (grow) over time, more vertices (e.g., users) and edges (e.g., interactions) are added. In addition, as the graph data set evolves, BEAD also allows the user to add more queries of interests to the query batch to accommodate new user demands. The key to the superior efficiency offered by BEAD lies in a series of incremental evaluation techniques that leverage the results of prior request to "fast-foward" the evaluation of the current request. We performed experiments comparing batching in BEAD with batching in MultiLyra for multiple input graphs and algorithms. Experiments demonstrate that BEAD's batched evaluation of 256 queries, following graph changes that add up to 100K edges to a billion edge Twitter graph and also query changes of up to 32 new queries, outperforms MultiLyra's batched evaluation by factors of up to 26.16 x and 5.66 x respectively.

关键词： distributed graph processing Query Batching Evolving graphs Evolving Query Batch

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：