Back to results
US 11,106,735 B2Granted
Directed graph compression
AssigneeInternational Business Machines Corporation
InventorsGuohua Li, Qi Liang, Qi Ye, Tian Tian, Weixiong Rao
Life of this patent
Estimating the term…
Abstract
In one embodiment of the present disclosure, an original graph including nodes is obtained. The nodes of the original graph are reordered to generate a reordered graph. Non-zero elements in an adjacency matrix for the reordered graph are clustered as compared with an adjacency matrix for the original graph. The adjacency matrix for the reordered graph is encoded with integers. The integers correspond to non-empty blocks in the adjacency matrix for the reordered graph.
Claims20
A computer-implemented method comprising:
- reordering, by one or more processors, a plurality of nodes of a graph, wherein a plurality of non-zero elements in a reordered adjacency matrix are clustered;
- and
- encoding, by one or more processors, the reordered adjacency matrix with a plurality of integers, wherein the encoding comprises:
- creating, by one or more processors, (i) a directory and (ii) a set of integers, wherein:
- a non-empty block in the reordered adjacency matrix includes at least two rows;
- the directory includes an associated row identification that identifies row location of the first non-empty block;
- and
- the set of numbers comprises:
- (i) a first integer that is a left-most column identification of the non-empty block and (ii) a second integer that is a representation of a binary number present in the non-empty block, wherein the binary number includes each integer of the at least two rows of the non-empty block.
6 more elements
A system comprising:
- one or more processors;
- a memory couples to at least one of the processors;
- a set of computer program instructions stored in the memory and executed by at least one of the processors in order to perform actions of:
- reordering a plurality of nodes of a graph, wherein a plurality of non-zero elements in a reordered adjacency matrix are clustered;
- and
- encoding the reordered adjacency matrix with a plurality of integers, wherein the encoding comprises:
- creating (i) a directory and (ii) a set of integers, wherein:
- a non-empty block in the reordered adjacency matrix includes at least two rows;
- the directory includes an associated row identification that identifies row location of the first non-empty block;
- and
- the set of numbers comprises:
- (i) a first integer that is a left-most column identification of the non-empty block and (ii) a second integer that is a representation of a binary number present in the non-empty block, wherein the binary number includes each integer of the at least two rows of the non-empty block.
9 more elements
A computer program product comprising:
- one or more computer readable storage media and program instructions stored on the one or more computer readable storage media, the program instructions comprising program instructions to:
- reorder a plurality of nodes of a graph, wherein a plurality of non-zero elements in a reordered adjacency matrix are clustered;
- and
- encode the reordered adjacency matrix with a plurality of integers, wherein the program instructions to encode comprise:
- program instructions to create (i) a directory and (ii) a set of integers, wherein:
- a non-empty block in the reordered adjacency matrix includes at least two rows;
- the directory includes an associated row identification that identifies row location of the first non-empty block;
- and
- the set of numbers comprises:
- (i) a first integer that is a left-most column identification of the non-empty block and (ii) a second integer that is a representation of a binary number present in the non-empty block, wherein the binary number includes each integer of the at least two rows of the non-empty block.
7 more elements
Dependencies are inferred from the claim text.