English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Graph plays a vital role in representing entities and their relationships ina variety of fields, such as e-commerce networks, social networks andbiological networks. Given two vertices s and t, one of the fundamentalproblems in graph databases is to investigate the relationships between s andt. A well-studied problem in such area is k-hop constrained s-t simple pathenumeration. Nevertheless, all existing algorithms targeting this problemfollow the DFS-based paradigm, which cannot scale up well. Moreover, usinghardware devices like FPGA to accelerate graph computation has become popular.Motivated by this, in this paper, we propose the first FPGA-based algorithmPEFP to solve the problem of k-hop constrained s-t simple path enumerationefficiently. On the host side, we propose a preprocessing algorithm Pre-BFS toreduce the graph size and search space. On the FPGA side in PEFP, we propose anovel DFS-based batching technique to save on-chip memory efficiently. Inaddition, we also propose caching techniques to cache necessary data in BRAM,which overcome the latency bottleneck brought by the read/write operationsfrom/to FPGA DRAM. Finally, we propose a data separation technique to enabledataflow optimization for the path verification module; hence the sub-stages inthat module can be executed in parallel. Comprehensive experiments show thatPEFP outperforms the state-of-the-art algorithm JOIN by more than 1 order ofmagnitude by average, and up to 2 orders of magnitude in terms of preprocessingtime, query processing time and total time, respectively.

PEFP: Efficient k-hop Constrained s-t Simple Path Enumeration on FPGA