Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Graph sampling and random walk acceleration method and system based on graphics processor

A graphics processor, random walk technology, applied in the field of data processing, can solve problems such as high complexity, reducing overall running time, and long overall running time

Active Publication Date: 2021-06-08
SHANGHAI JIAO TONG UNIV
View PDF7 Cites 1 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0004] Aiming at the disadvantages of existing biased graph sampling, high complexity of random walk system, low accelerator execution efficiency, long overall running time, etc., the present invention proposes a graph sampling and random walk acceleration method and system based on a graphics processor , can execute alias methods efficiently and in parallel, and can significantly improve the performance of graph data processing on the same hardware platform, including improving sampling throughput and reducing overall runtime

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Graph sampling and random walk acceleration method and system based on graphics processor
  • Graph sampling and random walk acceleration method and system based on graphics processor
  • Graph sampling and random walk acceleration method and system based on graphics processor

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0021] Such as figure 2 As shown, this embodiment relates to a graph sampling and random walk acceleration method based on a graphics processor. The CPU reads the graph data from the storage medium and converts it into a CSR format and then outputs it to the GPU. The GPU works according to the set Mode: Real-time generation of alias table and sampling; or offline judgment whether there is a pre-generated alias table and sampling, wherein: the initial stage graph structure data is stored in the memory of the graphics processor, and the vertices to be processed are stored in the global task In the queue; in the iterative execution stage, the thread groups in the kernel function independently process the tasks in the global task queue until the global task queue is empty.

[0022] The offline judgment refers to: when there is no pre-generated alias table, the alias table is first generated for the whole image before sampling, otherwise, the existing alias table is used for sampl...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

According to the graph sampling and random walk acceleration method and system based on the graphics processor, graph data are read from a storage medium through a CPU, converted into a CSR format and then output to the GPU, and the GPU generates an alias table in real time according to a set working mode and samples the alias table, or off-line judges whether a pre-generated alias table exists or not and sampling. According to the method, the alias method can be executed efficiently and concurrently, and the performance of graph data processing can be remarkably improved on the same hardware platform, including improvement of the sampling throughput and reduction of the overall running time.

Description

technical field [0001] The present invention relates to a technology in the field of data processing, in particular to a graphic processor-based graph sampling and random walk acceleration method and system for artificial intelligence applications. Background technique [0002] Graph sampling and random walk pass certain criteria to select subgraphs of the original graph data. Graph sampling and random walk are commonly used processing techniques for graph data, which can significantly reduce the overhead of processing large graphs while maintaining high accuracy and other indicators in artificial intelligence applications. However, graph sampling and random walk themselves are computationally The process also consumes a lot of time, and its acceleration is conducive to the improvement of overall performance. [0003] Partial graph sampling and random walk refer to the process of randomly selecting the neighbor vertices of a vertex in the graph according to the weight of th...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G06F9/48G06F9/50G06T1/20
CPCG06F9/4881G06F9/505G06T1/20G06F2209/5018
Inventor 李超王鹏宇王靖朱浩瑾过敏意
Owner SHANGHAI JIAO TONG UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com