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

Adaptive update handling for graph HTAP

DISTRIBUTED AND PARALLEL dataBASES 2023年第3期41卷 331-357页

作者： Jibril, Muhammad Attahir Baumstark, Alexander Sattler, Kai-Uwe TU Ilmenau Ilmenau Germany

Hybrid transactional/analytical processing (HTAP) workloads on graph data can significantly benefit from GPU accelerators. However, to exploit the full potential of GPU processing, dedicated graph representations are necessary, which mostly make in-place updates difficult. In this paper, we discuss an adaptive update handling approach in a graph database system for HTAP workloads. We discuss and evaluate strategies for propagating transactional updates from an update-friendly table storage to a GPU-optimized sparse matrix format for analytics.

关键词： graph data management HTAP GPU accelerator Delta store Cost model CSR

来源：评论

学校读者我要写书评

暂无评论

Distributed graph Neural Network Training: A Survey

引用

ACM COMPUTING SURVEYS 2024年第8期56卷 1-39页

作者： Shao, Yingxia Li, Hongzheng Gu, Xizhi Yin, Hongbo Li, Yawen Miao, Xupeng Zhang, Wentao Cui, Bin Chen, Lei Beijing Univ Posts & Telecommun 10 Xitucheng Rd Haidian Dist Beijing 100876 Peoples R China Carnegie Mellon Univ 5000 Forbes Ave Pittsburgh PA 15213 USA HEC Montreal Mila Quebec AI Inst 6666 St Urbain St Montreal PQ H2S 3H1 Canada Peking Univ 5 Yiheyuan Rd Beijing 100871 Peoples R China Hong Kong Univ Sci & Technol Guangzhou 1 Du Xue Rd Guangzhou 511442 Peoples R China

graph neural networks (GNNs) are a type of deep learning models that are trained on graphs and have been successfully applied in various domains. Despite the effectiveness of GNNs, it is still challenging for GNNs to efficiently scale to large graphs. As a remedy, distributed computing becomes a promising solution of training large-scale GNNs, since it is able to provide abundant computing resources. However, the dependency of graph structure increases the difficulty of achieving high-efficiency distributed GNN training, which suffers from the massive communication and workload imbalance. In recent years, many efforts have been made on distributed GNN training, and an array of training algorithms and systems have been proposed. Yet, there is a lack of systematic review of the optimization techniques for the distributed execution of GNN training. In this survey, we analyze three major challenges in distributed GNN training: massive feature communication, the loss of model accuracy, and workload imbalance. Then, we introduce a new taxonomy for the optimization techniques in distributed GNN training that address the above challenges. The new taxonomy classifies existing techniques into four categories: GNN data partition, GNN batch generation, GNN execution model, and GNN communication protocol. We carefully discuss the techniques in each category. In the conclusion, we summarize existing distributed GNN systems for multi-graphics processing units (GPUs), GPU-clusters and central processing unit (CPU)-clusters, respectively, and present a discussion about the future direction of distributed GNN training.

关键词： Surveys and overviews distributed GNN training graph data management communication optimization distributed GNN systems

来源：评论

学校读者我要写书评

暂无评论

One Edge at a Time: A Novel Approach Towards Efficient Transitive Reduction Computation on DAGs

引用

IEEE ACCESS 2020年 8卷 38010-38022页

作者： Tang, Xian Zhou, Junfeng Qiu, Yaxian Liu, Xiang Shi, Yunyu Zhao, Jingwen Shanghai Univ Engn Sci Sch Elect & Elect Engn Shanghai 201620 Peoples R China Donghua Univ Sch Comp Sci & Technol Shanghai 201620 Peoples R China

Given a directed acyclic graph (DAG) G, G's transitive reduction (TR) Gtr is the unique DAG satisfying that Gtr has the minimum number of edges and has the same transitive closure (TC) as G. TR computation has been extensively studied during the past decades and was used in many applications, where the main problem is how to compute TR efficiently for large graphs. However, existing approaches have either large space complexity or higher time complexity, which makes them cannot compute TR efficiently on large dense graphs. We propose a novel approach for TR computation, which takes every single edge as the basic processing unit, and utilizes existing reachability algorithms to test whether it is redundant or not. In this way, we avoid the costly graph traversal operation of existing approaches. We identify the performance bottleneck and propose a set of heuristics to sort edges, such that to reduce the average processing cost of each edge. We show by experimental results that our approach works much better than all the existing approaches, and can be faster than the state-of-the-art approach by more than two orders of magnitude on large dense graphs.

关键词： graph data management directed acyclic graph transitive reduction

来源：评论

学校读者我要写书评

暂无评论

Making graphs compact by lossless contraction

引用

VLDB JOURNAL 2023年第1期32卷 49-73页

作者： Fan, Wenfei Li, Yuanhao Liu, Muyang Lu, Can Univ Edinburgh Edinburgh Midlothian Scotland Shenzhen Inst Comp Sci Shenzhen Peoples R China Beihang Univ BDBC Beijing Peoples R China

This paper proposes a scheme to reduce big graphs to small graphs. It contracts obsolete parts and regular structures into supernodes. The supernodes carry a synopsis S-Q for each query class Q in use, to abstract key features of the contracted parts for answering queries of Q. Moreover, for various types of graphs, we identify regular structures to contract. The contraction scheme provides a compact graph representation and prioritizes up-to-date data. Better still, it is generic and lossless. We show that the same contracted graph is able to support multiple query classes at the same time, no matter whether their queries are label based or not, local or non-local. Moreover, existing algorithms for these queries can be readily adapted to compute exact answers by using the synopses when possible and decontracting the supernodes only when necessary. As a proof of concept, we show how to adapt existing algorithms for subgraph isomorphism, triangle counting, shortest distance, connected component and clique decision to contracted graphs. We also provide a bounded incremental contraction algorithm in response to updates, such that its cost is determined by the size of areas affected by the updates alone, not by the entire graphs. We experimentally verify that on average, the contraction scheme reduces graphs by 71.9% and improves the evaluation of these queries by 1.69, 1.44, 1.47, 2.24 and 1.37 times, respectively.

关键词： graph data management graph contraction graph algorithms Incremental computation

来源：评论

学校读者我要写书评

暂无评论

Keyword Search on RDF graphs - A Query graph Assembly Approach 17

Keyword Search on RDF Graphs - A Query Graph Assembly Approa...

引用

ACM Conference on Information and Knowledge management (CIKM)

作者： Han, Shuo Zou, Lei Yu, Jeffery Xu Zhao, Dongyan Peking Univ Beijing Peoples R China Chinese Univ Hong Kong Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781450349185

Keyword search provides ordinary users an easy-to-use interface for querying RDF data. Given the input keywords, in this paper, we study how to assemble a query graph that is to represent user's query intention accurately and efficiently. Based on the input keywords, we first obtain the elementary query graph building blocks, such as entity/class vertices and predicate edges. Then, we formally define the query graph assembly (QGA) problem. Unfortunately, we prove theoretically that QGA is a NP-complete problem. In order to solve that, we design some heuristic lower bounds and propose a bipartite graph matching-based best-first search algorithm. The algorithm's time complexity is O(k(2l).l(3l)), where 1 is the number of the keywords and k is a tunable parameter, i.e., the maximum number of candidate entity/class vertices and predicate edges allowed to match each keyword. Although QGA is intractable, both 1 and k are small in practice. Furthermore, the algorithm's time complexity does not depend on the RDF graph size, which guarantees the good scalability of our system in large RDF graphs. Experiments on DBpedia and Freebase confirm the superiority of our system on both effectiveness and efficiency.

关键词： keyword search RDF graph data management

来源：评论

学校读者我要写书评

暂无评论

Incremental graph Computations: Doable and Undoable 17

Incremental Graph Computations: Doable and Undoable

引用

ACM International Conference on management of data

作者： Fan, Wenfei Hu, Chunming Tian, Chao Univ Edinburgh Edinburgh Midlothian Scotland Beihang Univ Beijing Peoples R China

ISBN: (纸本)9781450341974

The incremental problem for a class Q of graph queries aims to compute, given a query Q is an element of Q, graph G, output Q(G) and updates Delta G to G as input, changes Delta O to Q(G) such that Q(G circle plus Delta G) = Q(G)circle plus Delta O. It is called bounded if its cost can be expressed as a polynomial function in the sizes of Q, Delta G and Delta O. It is to reduce computations on possibly big G to small Delta G and Delta O. No matter how desirable, however, our first results are negative: for common graph queries such as graph traversal, connectivity, keyword search and pattern matching, their incremental problems are unbounded. In light of the negative results, we propose two characterizations for the effectiveness of incremental computation: (a) localizable, if its cost is decided by small neighbors of nodes in Delta G instead of the entire G;and (b) bounded relative to a batch algorithm T, if the cost is determined by the sizes of Delta G and changes to the affected area that is necessarily checked by T. We show that the incremental computations above are either localizable or relatively bounded, by providing corresponding incremental algorithms. That is, we can either reduce the incremental computations on big graphs to small data, or incrementalize batch algorithms by minimizing unnecessary recomputation. Using real-life graphs, we experimentally verify the effectiveness of our algorithms.

关键词： incremental computation graph data management query optimization

来源：评论

学校读者我要写书评

暂无评论

Making graphs Compact by Lossless Contraction 21

Making Graphs Compact by Lossless Contraction

引用

ACM SIGMOD International Conference on management of data (SIGMOD)

作者： Fan, Wenfei Li, Yuanhao Liu, Muyang Lu, Can Univ Edinburgh Edinburgh Midlothian Scotland Shenzhen Inst Comp Sci Shenzhen Peoples R China Beihang Univ Beijing Peoples R China

ISBN: (纸本)9781450383431

This paper proposes a scheme to reduce big graphs to small graphs. It contracts obsolete parts, stars, cliques and paths into supernodes. The supernodes carry a synopsis S-Q for each query class Q to abstract key features of the contracted parts for answering queries of Q. The contraction scheme provides a compact graph representation and prioritizes up-to-date data. Better still, it is generic and lossless. We show that the same contracted graph is able to support multiple query classes at the same time, no matter whether their queries are label-based or not, local or non-local. Moreover, existing algorithms for these queries can be readily adapted to compute exact answers by using the synopses when possible, and decontracting the supernodes only when necessary. As a proof of concept, we show how to adapt existing algorithms for subgraph isomorphism, triangle counting and shortest distance to contracted graphs. We also provide an incremental contraction algorithm in response to updates. We experimentally verify that on average, the contraction scheme reduces graphs by 71.2%, and improves the evaluation of these queries by 1.53, 1.42 and 2.14 times, respectively.

关键词： graph data management graph contraction graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards Next-Generation graph Processing and management Platform

Towards Next-Generation Graph Processing and Management Plat...

引用

ACM Workshop on High Performance graph Processing (HPGP)

作者： Suzumura, Toyotaro IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Univ Tokyo Barcelona Supercomp Ctr Tokyo 1138654 Japan

ISBN: (纸本)9781450343503

Application which need to process and manage large graph data sets have imposed significant challenges for data science community inrecent times. This talk discusses the key challenges which need to be handled when implementing a next-generation graph processing and management platform. There are severalkey problems which needs to bead dressed in building such large graph processing system. First, optimized techniques needs to be followed for managing extremely large graph data. Second, new programming models and software tools need to be created for efficiently processing large graphs. This talk will discuss the approaches which need to be followed in addressing these two major issues and will highlight our vision in achieving the challenges of next-generation graph processing and management.

关键词： Large graph Processing High Performance Computing graph data management graph Algorithm

来源：评论

学校读者我要写书评

暂无评论

System G data Store: Big, Rich graph data Analytics in the Cloud

System G Data Store: Big, Rich Graph Data Analytics in the C...

引用

1st IEEE International Conference on Cloud Engineering (IC2E)

作者： Canim, Mustafa Chang, Yuan-Chi IBM Thomas J Watson Res Ctr Yorktown Hts NY USA

ISBN: (纸本)9780769549453;9781467364737

Big, rich graph data is increasingly captured through the interactions among people (email, messaging, social media), objects (location/map, server/network, product/catalog) and their relations. graph data analytics, however, poses several intrinsic challenges that are ill fitted to the popular MapReduce programming model. This paper presents System G data Store, a graph data management system that supports rich graph data, accepts online updates, complies with Hadoop, and runs efficiently by minimizing redundant data shuffling. These desirable capabilities are built on top of Apache HBase for scalability, updatability and compatibility. This paper introduces several exemplary target graph queries and global feature algorithms implemented using the newly available HBase Coprocessors. These graph algorithmic coprocessors execute on the server side directly on graph data stored locally and only communicates with remote servers for the dynamic algorithmic state, which is typically a small fraction of the raw data. Performance evaluation on real-world rich graph datasets demonstrated significant improvement over traditional Hadoop implementation, as prior works observed in their no-graph-shuffling solutions. Our work stands out at achieving the same or better performance without introducing incompatibility or scalability limitations.

关键词： graph data management graph analytics HBase Coprocessor

来源：评论

学校读者我要写书评

暂无评论

Adaptive Update Handling for graph HTAP 38

Adaptive Update Handling for Graph HTAP

引用

38th IEEE International Conference on data Engineering (ICDE)

作者： Jibril, Muhammad Attahir Baumstark, Alexander Sattler, Kai-Uwe TU Ilmenau Ilmenau Germany

ISBN: (纸本)9781665481045

Processing hybrid transactional/analytical work-loads on graph data can significantly benefit from GPU accelerators. However, to exploit the full potential of GPU processing, dedicated graph representations are necessary, which make in-place updates difficult. In this paper, we discuss an approach for adaptive handling of updates in a graph database system for HTAP workloads. We discuss and evaluate strategies for propagating updates from an update-friendly table storage to a GPU-optimized sparse matrix format.

关键词： HTAP graph analytics GPU delta adaptive update handling CSR cost model graph data management

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：