A GPU-based detection method for multi-partition strongly connected graphs

A technology of strongly connected graphs and detection methods, applied in other database retrieval, processor architecture/configuration, other database indexes, etc., to achieve the effect of improving algorithm efficiency and reducing the number of detections

Active Publication Date: 2021-03-09
INST OF INFORMATION ENG CHINESE ACAD OF SCI
View PDF7 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

In addition, the process of center point selection and weakly connected region detection in the traditional FB algorithm has room for speed-up

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
  • A GPU-based detection method for multi-partition strongly connected graphs
  • A GPU-based detection method for multi-partition strongly connected graphs
  • A GPU-based detection method for multi-partition strongly connected graphs

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0045] In order to make the above-mentioned features and advantages of the present invention more comprehensible, the present invention will be further described in detail below through specific embodiments and in conjunction with the accompanying drawings.

[0046] This embodiment proposes a GPU-based multi-partition strongly connected graph detection method. The method covers the selection scheme of the center point, the selection scheme of the sub-center point, and the simultaneous traversal of the center point and the sub-centre point to increase the number of partitions generated by each detection. The number of schemes and the central point directly select the scheme after the weakly connected area. like figure 1 As shown, the implementation process of this method can be roughly divided into two stages, the first stage detects large-scale strongly connected graphs, and the second stage detects medium-sized strongly connected graphs. Weakly connected region detection is ...

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

The invention provides a multi-partition strong connected graph detection method based on GPU. The method comprises the following steps of loading graph data and unifying storage formats; performing a first pruning operation on the graph data based on a GPU, and detecting 1-SCC; selecting a central point on the part except the 1-SCC, performing traversing forwards and backwards in parallel from the central point, and updating the state to obtain the SCC and a plurality of partitions; performing a second pruning operation on the undetected graph data based on the GPU, and detecting 2-SCC; detecting a weakly connected region on the undetected graph data, selecting a central point on each weakly connected region, and performing forward traversal from the central point; randomly selecting the last stored vertex as an auxiliary center point from the areas which are not traversed forwards in the weak connected areas, starting backward traversing from the center point and the auxiliary center point, performing first pruning operation, and updating the state again to obtain SCC and partitions. All SCCs are obtained through the steps.

Description

technical field [0001] The invention belongs to the field of graph calculation on a heterogeneous system, and in particular relates to a method for detecting a multi-partition strongly connected graph on a heterogeneous system configured with a GPU device. Background technique [0002] With the vigorous development of technologies such as big data and the Internet of Things, more and more data can be obtained, and there are intricate connections between these data. Graph computing can simplify research on these complex information, and strongly connected graph (Strongly Connected Components, SCC) detection is an important basic algorithm in graph computing. In the early research on strongly connected graph detection, there are many classic and well-effective strongly connected graph detection schemes, most of which are serial algorithms. However, as the scale of graph data continues to increase, the detection time of the serial algorithm will show a linear upward trend. Wi...

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
Patent Type & Authority Patents(China)
IPC IPC(8): G06T1/20G06F16/901
CPCG06T1/20G06F16/9024
Inventor 侯骏腾王树鹏吴广君王振宇张建宇
Owner INST OF INFORMATION ENG CHINESE ACAD OF SCI
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

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

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap