Graph upscaling method for preserving graph properties
AssigneeDaegu Gyeongbuk Institute of Science and Technology
InventorsMin Soo Kim, Himchan Park
Life of this patent
Estimating the term…
Abstract
A graph upscaling method and apparatus is disclosed. The graph upscaling apparatus may store, in a main memory, original graph data including topological data including a vertex and an edge, determine a parent edge using a hash function and the original graph data, and generate a new edge based on the determined parent edge. The graph upscaling apparatus may store, in a main memory, original graph data including topological data including a vertex and an edge, allocate identities (IDs) of edges to be generated to cores included in a central processing unit (CPU) based on the number of the cores, and generate new edges based on the IDs of the edges using a hash function and the original graph data.
Claims8
A graph upscaling method comprising:
- storing, in a main memory, original graph data including topological data including a vertex and an edge;
- determining a parent edge using a hash function and the original graph data;
- generating a new edge based on the determined parent edge;
- and
- determining a current scale factor based on an identity (ID) of the new edge,
- wherein the determining of the parent edge comprises:
- determining an ID of the parent edge;
- and
- determining a direction of the parent edge
- wherein the determining of the ID of the parent edge comprises:
- determining a hash function value for the ID of the new edge;
- and
- determining the ID of the parent edge based on the hash function value, the current scale factor, and the number of edges in the original graph data,
- wherein the generating of the new edge comprises:
- determining a reference vertex based on a first vertex among two vertices of the parent edge;
- and
- determining the new edge based on the determined reference vertex and a second vertex among the two vertices, and
- wherein an ID of the reference vertex is determined based on an ID of the first vertex among the two vertices of the parent edge, the number of vertices in the original graph data, and a current scale factor.
A graph upscaling apparatus comprising:
- a central processing unit (CPU) including a plurality of cores;
- and
- a controller configured to store, in a main memory, original graph data including topological data including a vertex and an edge and allocate, to the cores, identities (IDs) of edges to be generated based on the number of the cores,
- wherein each of the cores is configured to generate new edges based on a corresponding ID allocated to each of the cores using a hash function and the original graph data,
- wherein the controller configured to generate the new edges until a preset number is satisfied,
- wherein the preset number includes a product of the number of edges in the original graph data and a final scale factor,
- wherein the each of the cores is configured to determine a parent edge using the hash function and the original graph data, and generate new edges based on the determined parent edge,
- wherein the each of the cores is configured to:
- determine a reference vertex based on a first vertex among two vertices of the parent edge;
- and
- determine a new edge based on the determined reference vertex and a second vertex among the two vertices, and
- wherein an ID of the reference vertex is determined based on an ID of the first vertex among the two vertices of the parent edge, the number of vertices in the original graph data, and a current scale factor.
Dependencies are inferred from the claim text.