You Peng
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
You Peng has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Wenjie Zhang
University of New South Wales
3 shared publications - Lu Qin
University of Technology Sydney, Sydney, Australia
2 shared publications - Xuemin Lin
The Chinese University of Hong Kong
2 shared publications - Ying Zhang
University of Technology Sydney
2 shared publications - Jingren Zhou
Alibaba Group, Seattle, USA
1 shared publication - Shiyu Yang
Normal University East China
1 shared publication
Latest Publications
- 28 August 2021
- Published by Springer Nature in The VLDB Journal
- Vol. 31 (1) , 101-127
Answering reachability and K-reach queries on large graphs with label constraints
- 28 August 2021
- Published by Springer Nature in The VLDB Journal
- Vol. 31 (1) , 101-127
Answering reachability and K-reach queries on large graphs with label constraints
- 8 May 2021
- Published by Springer Nature in The VLDB Journal
- Vol. 30 (5) , 799-823
Efficient Hop-constrained s-t Simple Path Enumeration
- 8 May 2021
- Published by Springer Nature in The VLDB Journal
- Vol. 30 (5) , 799-823
Efficient Hop-constrained s-t Simple Path Enumeration
- Open Access
PEFP: Efficient k-hop Constrained s-t Simple Path Enumeration on FPGA
Graph plays a vital role in representing entities and their relationships in a variety of fields, such as e-commerce networks, social networks and biological networks. Given two vertices s and t, one of the fundamental problems in graph databases is to investigate the relationships between s and t. A well-studied problem in such area is k-hop constrained s-t simple path enumeration. Nevertheless, all existing algorithms targeting this problem follow the DFS-based paradigm, which cannot scale up well. Moreover, using hardware devices like FPGA to accelerate graph computation has become popular. Motivated by this, in this paper, we propose the first FPGA-based algorithm PEFP to solve the problem of k-hop constrained s-t simple path enumeration efficiently. On the host side, we propose a preprocessing algorithm Pre-BFS to reduce the graph size and search space. On the FPGA side in PEFP, we propose a novel DFS-based batching technique to save on-chip memory efficiently. In addition, we also propose caching techniques to cache necessary data in BRAM, which overcome the latency bottleneck brought by the read/write operations from/to FPGA DRAM. Finally, we propose a data separation technique to enable dataflow optimization for the path verification module; hence the sub-stages in that module can be executed in parallel. Comprehensive experiments show that PEFP outperforms the state-of-the-art algorithm JOIN by more than 1 order of magnitude by average, and up to 2 orders of magnitude in terms of preprocessing time, query processing time and total time, respectively.
Open AccessPEFP: Efficient k-hop Constrained s-t Simple Path Enumeration on FPGA
Graph plays a vital role in representing entities and their relationships in a variety of fields, such as e-commerce networks, social networks and biological networks. Given two vertices s and t, one of the fundamental problems in graph databases is to investigate the relationships between s and t. A well-studied problem in such area is k-hop constrained s-t simple path enumeration. Nevertheless, all existing algorithms targeting this problem follow the DFS-based paradigm, which cannot scale up well. Moreover, using hardware devices like FPGA to accelerate graph computation has become popular. Motivated by this, in this paper, we propose the first FPGA-based algorithm PEFP to solve the problem of k-hop constrained s-t simple path enumeration efficiently. On the host side, we propose a preprocessing algorithm Pre-BFS to reduce the graph size and search space. On the FPGA side in PEFP, we propose a novel DFS-based batching technique to save on-chip memory efficiently. In addition, we also propose caching techniques to cache necessary data in BRAM, which overcome the latency bottleneck brought by the read/write operations from/to FPGA DRAM. Finally, we propose a data separation technique to enable dataflow optimization for the path verification module; hence the sub-stages in that module can be executed in parallel. Comprehensive experiments show that PEFP outperforms the state-of-the-art algorithm JOIN by more than 1 order of magnitude by average, and up to 2 orders of magnitude in terms of preprocessing time, query processing time and total time, respectively.