Query：
学者姓名：程永利
Refining：
Year
Type
Indexed by
Source
Complex
Former Name
Co-
Language
Clean All
Abstract ：
In recent years, a number of out-of-core graph processing systems have been proposed to process graphs with billions of edges on just one commodity computer, due to their high cost efficiency. To obtain a better performance, these systems adopt a full I/O model that scans all edges during the computation to avoid the inefficiency of random I/Os. Although this model ensures good I/O access locality, it leads to a large number of useless edges to be loaded when running graph algorithms that only access a small portion of edges in each iteration. An intuitive method to solve this I/O inefficiency problem is the on-demand I/O model that only accesses the active edges. However, this method only works well for the graph algorithms with very few active edges, since the I/O cost will grow rapidly as the number of active edges increases due to the increasing amount of random I/Os. In this article, we present HUS-Graph, an efficient out-of-core graph processing system to address the above I/O issues and achieve a good balance between I/O traffic and I/O access locality. HUS-Graph adopts a hybrid update strategy including two update models, Row-oriented Push (ROP) and Column-oriented Pull (COP). It supports switching between ROP and COP adaptively, for the graph algorithms that have different computation and I/O features. For traversal-based algorithms, HUS-Graph also provides an immediate propagation-based vertex update scheme to accelerate the vertex state propagation and convergence speed. Furthermore, HUS-Graph adopts a locality-optimized dual-block representation to organize graph data and an I/O-based performance prediction method to enable the system to dynamically select the optimal update model between ROP and COP. To save the disk space and further reduce I/O traffic, HUS-Graph implements a space-efficient storage format by combining several graph compression methods. Extensive experimental results show that HUS-Graph outperforms two existing out-of-core systems GraphChi and GridGraph by 1.2x-52.8x.
Keyword ：
Graph processing Graph processing hybrid update strategy hybrid update strategy I/O I/O out-of-core out-of-core
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Xu, Xianghao , Wang, Fang , Jiang, Hong et al. A Hybrid Update Strategy for I/O-Efficient Out-of-Core Graph Processing [J]. | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS , 2020 , 31 (8) : 1767-1782 . |
| MLA | Xu, Xianghao et al. "A Hybrid Update Strategy for I/O-Efficient Out-of-Core Graph Processing" . | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 31 . 8 (2020) : 1767-1782 . |
| APA | Xu, Xianghao , Wang, Fang , Jiang, Hong , Chen, Yongli , Feng, Dan , Zhang, Yongxuan . A Hybrid Update Strategy for I/O-Efficient Out-of-Core Graph Processing . | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS , 2020 , 31 (8) , 1767-1782 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Nowadays, high-bandwidth networks are more easily accessible than ever before. However, existing distributed graph-processing frameworks, such as GPS, fail to efficiently utilize the additional bandwidth capacity in these networks for higher performance, due to their inefficient computation and communication models, leading to very long waiting times experienced by users for the graph-computing results. The root cause lies in the fact that the computation and communication models of these frameworks generate, send and receive messages so slowly that only a small fraction of the available network bandwidth is utilized. In this paper, we propose a high-performance distributed graph-processing framework, called BlitzG, to address this problem. This framework fully exploits the available network bandwidth capacity for fast graph processing. Our approach aims at significant reduction in (i) the computation workload of each vertex for fast message generation by using a new slimmed-down vertex-centric computation model and (ii) the average message overhead for fast message delivery by designing a light-weight message-centric communication model. Evaluation on a 40Gbps Ethernet, driven by real-world graph datasets, shows that BlitzG outperforms GPS by up to 27x with an average of 20.7x.
Keyword ：
communication model communication model computation model computation model Graph computation Graph computation high-bandwidth networks high-bandwidth networks high performance high performance
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Cheng, Yongli , Jiang, Hong , Wang, Fang et al. Using High-Bandwidth Networks Efficiently for Fast Graph Computation [J]. | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS , 2019 , 30 (5) : 1170-1183 . |
| MLA | Cheng, Yongli et al. "Using High-Bandwidth Networks Efficiently for Fast Graph Computation" . | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 30 . 5 (2019) : 1170-1183 . |
| APA | Cheng, Yongli , Jiang, Hong , Wang, Fang , Hua, Yu , Feng, Dan , Guo, Wenzhong et al. Using High-Bandwidth Networks Efficiently for Fast Graph Computation . | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS , 2019 , 30 (5) , 1170-1183 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Big data applications increasingly rely on the analysis of large graphs. In recent years, a number of out-of-core graph processing systems have been proposed to process graphs with billions of edges on just one commodity computer, by efficiently using the secondary storage (e.g., hard disk, SSD). On the other hand, the vertex-centric computing model is extensively used in graph processing thanks to its good applicability and expressiveness. Unfortunately, when implementing vertex-centric model for out-of-core graph processing, the large number of random memory accesses required to construct subgraphs lead to a serious performance bottleneck that substantially weakens cache access locality and thus leads to very long waiting time experienced by users for the computing results. In this paper, we propose an efficient out-of-core graph processing system, LOSC, to substantially reduce the overhead of subgraph construction without sacrificing the underlying vertex-centric computing model. LOSC proposes a locality-optimized subgraph construction scheme that significantly improves the in-memory data access locality of the subgraph construction phase. Furthermore, LOSC adopts a compact edge storage format and a lightweight replication of vertices to reduce I/O traffic and improve computation efficiency. Extensive evaluation results show that LOSC is respectively 6.9x and 3.5x faster than GraphChi and GridGraph, two state-of-the-art out-of-core systems. © 2019 Association for Computing Machinery.
Keyword ：
Cache memory Cache memory Graph theory Graph theory Hard disk storage Hard disk storage Quality of service Quality of service Random access storage Random access storage
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Xu, Xianghao , Wang, Fang , Jiang, Hong et al. LOSC: Efficient out-of-core graph processing with locality-optimized subgraph construction [C] . 2019 . |
| MLA | Xu, Xianghao et al. "LOSC: Efficient out-of-core graph processing with locality-optimized subgraph construction" . (2019) . |
| APA | Xu, Xianghao , Wang, Fang , Jiang, Hong , Cheng, Yongli , Hua, Yu , Feng, Dan et al. LOSC: Efficient out-of-core graph processing with locality-optimized subgraph construction . (2019) . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Existing distributed graph-processing frameworks, e.g., Pregel, GPS and Giraph, handle large-scale graphs in the memory of clusters built of commodity compute nodes for better scalability and performance. While capable of scaling out according to the size of graphs up to thousands of compute nodes, for graphs beyond a certain size, these frameworks would usually require investments of machines that are either beyond the financial capability of or unprofitable for most small and medium-sized organizations, making the deployment of their large-scale graph-computing jobs difficult if not impossible. At the other end of the spectrum of graph-processing frameworks research, the single-node disk-based graph-computing frameworks, such as GraphChi and XStream, handle large-scale graphs on just one commodity computer, leading to high efficiency in the use of hardware but at the cost of low user performance and limited scalability. Motivated by this dichotomy, in this paper we propose a pipeline-based task scheduling strategy with high cost-effectiveness. We use this scheduling strategy to design and implement a distributed disk-based graph-processing framework, called DD-Graph, that can process very large graphs with trillions of edges on a small cluster while achieving the high performance of existing distributed in-memory graph-processing frameworks. The evaluation of DD-Graph prototype, driven by very large graph datasets, shows that it saves 73% of GPS' hardware costs while running 1.34x faster than GPS. (C) 2018 Elsevier B.V. All rights reserved.
Keyword ：
Cost-effectiveness Cost-effectiveness Graph computation Graph computation Very large graphs Very large graphs
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Cheng, Yongli , Wang, Fang , Jiang, Hong et al. A highly cost-effective task scheduling strategy for very large graph computation [J]. | FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE , 2018 , 89 : 698-712 . |
| MLA | Cheng, Yongli et al. "A highly cost-effective task scheduling strategy for very large graph computation" . | FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 89 (2018) : 698-712 . |
| APA | Cheng, Yongli , Wang, Fang , Jiang, Hong , Hua, Yu , Feng, Dan , Wu, Yunxiang et al. A highly cost-effective task scheduling strategy for very large graph computation . | FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE , 2018 , 89 , 698-712 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
The bulk synchronous parallel (BSP) model is very user friendly for coding and debugging parallel graph algorithms. However, existing BSP-based distributed graph-processing frameworks, such as Pregel, GPS and Giraph, routinely suffer from high communication costs. These high communication costs mainly stem from the fine-grained message-passing communication model. In order to address this problem, we propose a new computation model with low communication costs, called LCC-BSP. We use this model to design and implement a high-performance distributed graph-processing framework called LCC-Graph. This framework eliminates high communication costs in existing distributed graph-processing frameworks. Moreover, LCC-Graph also balances the computation workloads among all compute nodes by optimizing graph partitioning, significantly reducing the computation time for each superstep. Evaluation of LCC-Graph on a 32-node cluster, driven by real-world graph datasets, shows that it significantly outperforms existing distributed graph-processing frameworks in terms of run-time, particularly when the system is supported by a high-bandwidth network. For example, LCC-Graph achieves an order of magnitude performance improvement over GPS and GraphLab.
Keyword ：
communication decrease communication decrease computation balance computation balance graph computation graph computation
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Cheng, Yongli , Wang, Fang , Jiang, Hong et al. A communication-reduced and computation-balanced framework for fast graph computation [J]. | FRONTIERS OF COMPUTER SCIENCE , 2018 , 12 (5) : 887-907 . |
| MLA | Cheng, Yongli et al. "A communication-reduced and computation-balanced framework for fast graph computation" . | FRONTIERS OF COMPUTER SCIENCE 12 . 5 (2018) : 887-907 . |
| APA | Cheng, Yongli , Wang, Fang , Jiang, Hong , Hua, Yu , Feng, Dan , Zhang, Lingling et al. A communication-reduced and computation-balanced framework for fast graph computation . | FRONTIERS OF COMPUTER SCIENCE , 2018 , 12 (5) , 887-907 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
In recent years, a number of out-of-core graph processing systems have been proposed to process graphs with billions of edges on just one commodity computer, due to their high cost efficiency. To obtain the better performance, these systems adopt a full I/O model that accesses all edges during the computation to avoid the ineffectiveness of random I/Os. Although this model ensures good I/O access locality, it loads a large number of useless edges when running graph algorithms that only require a small portion of edges in each iteration. A natural method to solve this problem is the on-demand I/O model that only accesses the active edges. However, this method only works well for the graph algorithms with very few active edges, since the I/O cost will grow rapidly as the number of active edges increases due to larger amount of random I/Os. In this paper, we present HUS-Graph, an efficient out-of-core graph processing system to address the above I/O issues and achieve a good balance between I/O amount and I/O access locality. HUS-Graph first adopts a hybrid update strategy including two update models, Row-oriented Push (ROP) and Column-oriented Pull (COP). It can adaptively select the optimal update model for the graph algorithms that have different computation and I/O features, based on an I/O-based performance prediction method. Furthermore, HUS-Graph proposes a dual-block representation to organize graph data, which ensures good access locality. Extensive experimental results show that HUS-Graph outperforms existing out-of-core systems by 1.4x-23.1x. © 2018 Association for Computing Machinery.
Keyword ：
Computer applications Computer applications Computer programming Computer programming Iterative methods Iterative methods
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Xu, Xianghao , Cheng, Yongli , Wang, Fang et al. HUS-graph: I/O-efficient out-of-core graph processing with hybrid update strategy [C] . 2018 . |
| MLA | Xu, Xianghao et al. "HUS-graph: I/O-efficient out-of-core graph processing with hybrid update strategy" . (2018) . |
| APA | Xu, Xianghao , Cheng, Yongli , Wang, Fang , Feng, Dan , Jiang, Hong , Zhang, Yongxuan . HUS-graph: I/O-efficient out-of-core graph processing with hybrid update strategy . (2018) . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
With the rapid growth of application migration, the anonymity in data center networks becomes important in breaking attack chains and guaranteeing user privacy. However, existing anonymity systems are designed for the Internet environment, which suffer from high computational and network resource consumption and deliver low performance, thus failing to be directly deployed in data centers. In order to address this problem, this paper proposes an efficient and easily deployed anonymity scheme for software defined networking-based data centers, called mimic channel (MIC). The main idea behind MIC is to conceal the communication participants by modifying the source/destination addresses, such as media access control (MAC) and Internet protocol (IP) address at switch nodes, so as to achieve anonymity. Compared with the traditional overlay-based approaches, our in-network scheme has shorter transmission paths and less intermediate operations, thus achieving higher performance with less overhead. We also propose a collision avoidance mechanism to ensure the correctness of routing, and three mechanisms to enhance the traffic-analysis resistance. To enhance the practicality, we further propose solutions to enable MIC co-existing with some MIC-incompatible systems, such as packet analysis systems, intrusion detection systems, and firewall systems. Our security analysis demonstrates that MIC ensures unlinkability and improves traffic-analysis resistance. Our experiments show that MIC has extremely low overhead compared with the base-line transmission control protocol (TCP) (or secure sockets layer (SSL)), e.g., less than 1% overhead in terms of throughput. Experiments on MIC-based distributed file system show the applicability and efficiency of MIC.
Keyword ：
Anonymity Anonymity data center data center distributed file system distributed file system in-network anonymous communication in-network anonymous communication software-defined networking software-defined networking
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zhu, Tingwei , Feng, Dan , Wang, Fang et al. Efficient Anonymous Communication in SDN-Based Data Center Networks [J]. | IEEE-ACM TRANSACTIONS ON NETWORKING , 2017 , 25 (6) : 3767-3780 . |
| MLA | Zhu, Tingwei et al. "Efficient Anonymous Communication in SDN-Based Data Center Networks" . | IEEE-ACM TRANSACTIONS ON NETWORKING 25 . 6 (2017) : 3767-3780 . |
| APA | Zhu, Tingwei , Feng, Dan , Wang, Fang , Hua, Yu , Shi, Qingyu , Liu, Jiahao et al. Efficient Anonymous Communication in SDN-Based Data Center Networks . | IEEE-ACM TRANSACTIONS ON NETWORKING , 2017 , 25 (6) , 3767-3780 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Export
| Results： |
Selected to |
| Format： |
