Patent ID: 11875426
Assignee: SHANGHAI JIAO TONG UNIVERSITY
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 7:
8. The graph sampling and random walk acceleration method based on GPU according to claim 1, wherein said generating and sampling an alias table in real-time specifically includes:
step 1: the working group of each GPU kernel function requests a task from the corresponding task queue and obtains a vertex to be sampled;
step 2: each working group checks the GPU's memory; if there is an alias table for the vertices to be sampled, go directly to the next step, otherwise, multiple GPU threads will coordinate to construct an alias table for the vertices to be sampled at the same time;
step 3: each working group uses min(|WG|, k) threads for sampling, where: min represents the minimum value, |WG| represents the number of threads in the working group, and k represents the size of each point sampled at the current depth; and
step 4: each working group stores the constructed alias table in the memory of the GPU for future use.