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

Lightweight efficient graph vertex rearrangement method

A graph vertex, lightweight technology, applied in the field of graph computing, can solve the problem of low efficiency of graph vertex rearrangement, and achieve the effect of improving efficiency

Pending Publication Date: 2021-02-19
SHENZHEN UNIV
View PDF3 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0009] The present invention provides a lightweight and high-efficiency graph vertex rearrangement method in order to overcome the defect of low graph vertex rearrangement efficiency described in the prior art

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
  • Lightweight efficient graph vertex rearrangement method
  • Lightweight efficient graph vertex rearrangement method
  • Lightweight efficient graph vertex rearrangement method

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0052] This embodiment provides a lightweight and efficient graph vertex rearrangement method, such as figure 1 As shown, the method includes the following steps:

[0053] S1: Load the graph that needs to be rearranged by ID, and perform preprocessing to determine the seed point.

[0054] S1.1: Load the graph G=(V, E) that needs ID rearrangement, V represents the vertex set of the graph, E represents the edge set of the graph, and |V| and |E| represent the number of vertices and the number of edges respectively. The entire image information is stored in the form of Compressed Sparse Row (CSR). Set the flag bit is_trivial of the vertex according to the in-degree of the vertex, if the in-degree is greater than the given threshold λ, set is_trivial=true, otherwise set is_trivial=false.

[0055] S1.2: In order to reproduce the rearrangement results, this method sets the ID rearrangement from the vertex with the smallest original ID, and selects the seed point seed, wherein the v...

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 relates to a lightweight efficient graph vertex rearrangement method, which comprises the following steps of S1, loading a graph needing to be subjected to ID rearrangement, performing preprocessing, and determining seed points; S2, selecting a seed point, and generating a super vertex through the seed point; and S3, allocating new IDs to the vertexes of the graph needing ID rearrangement according to the hyper-vertexes, thereby realizing graph vertex rearrangement. The common neighbors of the combined vertexes have similar IDs through a method of combining the low-in-degree vertexes and then distributing the IDs. As the invention always depends on the vertex information directly connected with the current vertex during ID rearrangement, belongs to local information, and pursues to quickly complete the rearrangement operation while realizing local optimization, the rearrangement operation of the method is also efficient, and the graph vertex rearrangement efficiency can be effectively improved.

Description

technical field [0001] The invention relates to the field of graph computing, and more specifically, to a lightweight and efficient graph vertex rearrangement method. Background technique [0002] Since graphs can well represent various relationships in reality, and various graph algorithms can be used to mine potential facts in the graph structure, graph computing has many applications. However, the calculation of large-scale graphs requires a very large amount of data. In order to complete graph computing more efficiently, scholars try to optimize it from multiple aspects, including the improvement of the graph computing environment, the optimization of the algorithm level, and the preprocessing of graph data. aspect. Among them, the preprocessing of the graph data does not involve the specific graph algorithm before the execution of the graph algorithm, and does not need to modify the original algorithm. Therefore, after a certain graph has been preprocessed once, a sing...

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 Applications(China)
IPC IPC(8): G06F16/901G06F17/16
CPCG06F16/9024G06F17/16
Inventor 刘志丹黄保福伍楷舜
Owner SHENZHEN 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