Graph data compression method and apparatus
AssigneeKorea Advanced Institute of Science and Technology
InventorsMin-Soo Kim, Seyeon Oh, Donghyoung Han, Inju Na, Sungwoo Park
Life of this patent
Estimating the term…
Abstract
Provided are a graph data compression method and apparatus. A computing device divides graph data including information about a source vertex and a destination vertex of an edge into a plurality of pieces, generates a plurality of compressed data obtained by compressing the plurality of pieces, and stores the plurality of compressed data as a file. The computing device may generate a plurality of pieces having a size equal to or less than a predefined data size by recursively dividing graph data.
Claims13
A graph data compression method by which computing device comprising one or more memories, one or more processors, and one or more input/output devices compress graph data comprising vertices and edges, the graph data compression method comprising:
- dividing graph data comprising information about a source vertex and a destination vertex of each edge into a plurality of pieces;
- generating a plurality of compressed data obtained by compressing the plurality of pieces;
- and
- storing the plurality of compressed data,
- wherein the dividing comprises recursively dividing the graph data to generate a plurality of pieces having a size equal to or less than a predefined data size.
A graph data compression method by which computing device comprising one or more memories, one or more processors, and one or more input/output devices compress graph data comprising vertices and edges, the graph data compression method comprising:
- dividing graph data comprising information about a source vertex and a destination vertex of each edge into a plurality of pieces;
- generating a plurality of compressed data obtained by compressing the plurality of pieces;
- and
- storing the plurality of compressed data,
- wherein the graph data is an adjacency matrix in which source vertices and destination vertices of edges are represented as a matrix,
- wherein the dividing comprises recursively dividing the adjacency matrix until a number of edges included in each piece is equal to or less than a predefined number.
A graph data compression method by which computing device comprising one or more memories, one or more processors, and one or more input/output devices compress graph data comprising vertices and edges, the graph data compression method comprising:
- dividing graph data comprising information about a source vertex and a destination vertex of each edge into a plurality of pieces;
- generating a plurality of compressed data obtained by compressing the plurality of pieces;
- and
- storing the plurality of compressed data,
- wherein the storing comprises mapping and storing the plurality of compressed data with index information of each piece.
A graph data compression method by which computing device comprising one or more memories, one or more processors, and one or more input/output devices compress graph data comprising vertices and edges, the graph data compression method comprising:
- dividing graph data comprising information about a source vertex and a destination vertex of each edge into a plurality of pieces;
- generating a plurality of compressed data obtained by compressing the plurality of pieces;
- and
- storing the plurality of compressed data,
- wherein the generating of the plurality of compressed data comprises:
- for each piece,
- converting global identification information indicating vertices of the graph data into local identification information that sequentially increases within the piece;
- and
- generating compressed data representing source vertices and destination vertices of edges by using the local identification information.
A graph data compression method by which computing device comprising one or more memories, one or more processors, and one or more input/output devices compress graph data comprising vertices and edges, the graph data compression method comprising:
- dividing graph data comprising information about a source vertex and a destination vertex of each edge into a plurality of pieces;
- generating a plurality of compressed data obtained by compressing the plurality of pieces;
- and
- storing the plurality of compressed data,
- wherein the generating of the plurality of compressed data comprises:
- dividing a piece comprising source vertices and destination vertices of edges into two or more groups;
- and
- for each group, generating compressed data comprising first information indicating a difference between identification information of each source vertex from an immediately previous source vertex, second information indicating a number of edges for each source vertex, third information indicating groups to which destination vertices of edges for each source vertex belongs, and fourth information indicating destination vertices of edges for each source vertex.
A computing device comprising:
- memories into which graph data is loaded;
- and
- processors configured to generate and store compressed data for the graph data stored in the memories by using a graph compression storage method,
- wherein the graph data compression storage method comprises:
- dividing graph data comprising information about source vertices and destination vertices of edges into a plurality of pieces;
- generating a plurality of compressed data obtained by compressing the plurality of pieces;
- and
- storing the plurality of compressed data,
- wherein the dividing comprises recursively dividing the graph data to generate a plurality of pieces having a size equal to or less than a predefined data size.
Dependencies are inferred from the claim text.