Shortest-path calculation on weighted graphs are an essential operation in computer networks. The performance of such algorithms has become a critical challenge in emerging software-defined networks(SDN),since SDN con...Shortest-path calculation on weighted graphs are an essential operation in computer networks. The performance of such algorithms has become a critical challenge in emerging software-defined networks(SDN),since SDN controllers need to centralizedly perform a shortest-path query for every flow,usually on large-scale network. Unfortunately,one of the challenges is that current algorithms will become incalculable as the network size increases. Therefore, inspired by the compression graph in the field of compute visualization,we propose an efficient shortest path algorithm by compressing the original big network graph into a small one, but the important graph properties used to calculate path is reserved. We implement a centralized version of our approach in SDN-enabled network,and the evaluations validate the improvement compared with the well-known algorithms.展开更多
Graphs are an effective approach for data representation and organization,and graph analysis is a promising killer application for AI systems.However,recently emerging extremely large graphs(consisting of trillions of...Graphs are an effective approach for data representation and organization,and graph analysis is a promising killer application for AI systems.However,recently emerging extremely large graphs(consisting of trillions of vertices and edges)exceed the capacity of any small-/medium-scale clusters and thus necessitate the adoption of supercomputers for efficient graph processing.Graph500 is the de facto standard for benchmarking supercomputers’graph processing performance,and connected component(CC)is an important basic algorithm for Graph500’s BFS and SSSP tests.However,current CC algorithms are inefficient on supercomputers and fast CC is expensive and challenging.In this paper,we propose VPC,an efficient method that prunes connected components using vector-based path compression.It includes the following innovations:(i)The data structure of the traversal algorithm is customized with the two-dimensional adjacency vector.(ii)The vector-based path compression is proposed for the union-find algorithm.(iii)Parallel VPC is proposed customized with Tianhe.Experimental results validate that the two-dimensional adjacency vector has better performance than other data structures and the vectorbased path compression is used in the realization of the union-find algorithm.When the scale is 26,the performance of our algorithm is 1.38×,1.69×and 2.57×that of other algorithms.The union-find algorithm is used for connected components,and the performance of the algorithm is 5.14×and 5.01×that of BFS and DFS respectively.展开更多
Correction to:CCF Transactions on High Performance Computing https://doi.org/10.1007/s42514-021-00070-z In this article the following corrections have been made·Removed the last keyword.
Holistic twig query processing techniques based on region encoding have been developed to minimize the intermediate results, namely, those root-to-leaf path matches that are not in the final twig results. These algori...Holistic twig query processing techniques based on region encoding have been developed to minimize the intermediate results, namely, those root-to-leaf path matches that are not in the final twig results. These algorithms have to scan all the streams of tags in query patterns. However, useless path matches cannot be completely avoided. TJFast which is based on the labeling scheme of Extended Dewey has been proposed to avoid useless intermediate results, and it only needs to access the labels of the leaf query nodes. However, it don＇t concern about the characteristics of elements with the same parent, and it has to merge join all the intermediate results which are evaluated during the first phrase. We propose a new labeling scheme to compress the XML elements which have the same characteristic. Based on the compressed path-labeled streams, a new novel holistic twig query algorithm named CPJoin is designed. Finally, implementation results are provided to show that CPJoin has good performance on both real and synthetic data.展开更多
This paper provides a method of producing a minimum cost spanning tree(MCST)using set operations.It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and...This paper provides a method of producing a minimum cost spanning tree(MCST)using set operations.It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm.This algorithm uses the FDG(formula to divide elements into groups)to sort(the FDG sorts a sequence of n elements in expected tir O(n))and uses the method of path compression to find and to unite.Therefore.n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).展开更多
基金supported by the National Natural Science Foundation of China(No.61521003)
文摘Shortest-path calculation on weighted graphs are an essential operation in computer networks. The performance of such algorithms has become a critical challenge in emerging software-defined networks(SDN),since SDN controllers need to centralizedly perform a shortest-path query for every flow,usually on large-scale network. Unfortunately,one of the challenges is that current algorithms will become incalculable as the network size increases. Therefore, inspired by the compression graph in the field of compute visualization,we propose an efficient shortest path algorithm by compressing the original big network graph into a small one, but the important graph properties used to calculate path is reserved. We implement a centralized version of our approach in SDN-enabled network,and the evaluations validate the improvement compared with the well-known algorithms.
基金supported by the National Numerical Wind Tunnel Project(NNW2019ZT6-B21)the National Key Research and Development Program of China(2018YFB0204301)+1 种基金the Hunan Natural Science Foundation of China(2020JJ4669)the Foundation of Parallel and Distributed Processing Laboratory(6142110190206).
文摘Graphs are an effective approach for data representation and organization,and graph analysis is a promising killer application for AI systems.However,recently emerging extremely large graphs(consisting of trillions of vertices and edges)exceed the capacity of any small-/medium-scale clusters and thus necessitate the adoption of supercomputers for efficient graph processing.Graph500 is the de facto standard for benchmarking supercomputers’graph processing performance,and connected component(CC)is an important basic algorithm for Graph500’s BFS and SSSP tests.However,current CC algorithms are inefficient on supercomputers and fast CC is expensive and challenging.In this paper,we propose VPC,an efficient method that prunes connected components using vector-based path compression.It includes the following innovations:(i)The data structure of the traversal algorithm is customized with the two-dimensional adjacency vector.(ii)The vector-based path compression is proposed for the union-find algorithm.(iii)Parallel VPC is proposed customized with Tianhe.Experimental results validate that the two-dimensional adjacency vector has better performance than other data structures and the vectorbased path compression is used in the realization of the union-find algorithm.When the scale is 26,the performance of our algorithm is 1.38×,1.69×and 2.57×that of other algorithms.The union-find algorithm is used for connected components,and the performance of the algorithm is 5.14×and 5.01×that of BFS and DFS respectively.
文摘Correction to:CCF Transactions on High Performance Computing https://doi.org/10.1007/s42514-021-00070-z In this article the following corrections have been made·Removed the last keyword.
基金Supported by the National Natural Science Foundation of China (60573089)the Teaching and Research Award Program for Out-standing Young Teachers in Post-Secondary Institutions by the Ministry of Education, China (706016)
文摘Holistic twig query processing techniques based on region encoding have been developed to minimize the intermediate results, namely, those root-to-leaf path matches that are not in the final twig results. These algorithms have to scan all the streams of tags in query patterns. However, useless path matches cannot be completely avoided. TJFast which is based on the labeling scheme of Extended Dewey has been proposed to avoid useless intermediate results, and it only needs to access the labels of the leaf query nodes. However, it don＇t concern about the characteristics of elements with the same parent, and it has to merge join all the intermediate results which are evaluated during the first phrase. We propose a new labeling scheme to compress the XML elements which have the same characteristic. Based on the compressed path-labeled streams, a new novel holistic twig query algorithm named CPJoin is designed. Finally, implementation results are provided to show that CPJoin has good performance on both real and synthetic data.
文摘This paper provides a method of producing a minimum cost spanning tree(MCST)using set operations.It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm.This algorithm uses the FDG(formula to divide elements into groups)to sort(the FDG sorts a sequence of n elements in expected tir O(n))and uses the method of path compression to find and to unite.Therefore.n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).
