Lossless compression method for graph traversal

Patent metadata

Field	Value
Publication number	US-10263638-B2
Application number	US-201615168992-A
Country	US
Kind code	B2
Filing date	May 31, 2016
Priority date	May 31, 2016
Publication date	Apr 16, 2019
Grant date	Apr 16, 2019

Abstract

To enable lossless compression, an auxiliary bitmap is used to provide side information about the graph bitmap. Each bit in the auxiliary bitmap represents a word in the graph bitmap. A zero bit in the auxiliary bitmap means that the corresponding word in the graph bitmap is not transmitted. Therefore, it is set to the default value, λ, during decompression. This default value could be either an all-zeros word, or all-ones word depending on the BFS step. A one bit in the auxiliary bitmap means that the corresponding word in the graph bitmap is transmitted.

First claim

What is claimed is:

1. A method of data compression comprising:
constructing a graph bitmap as a sequence of a plurality of words each being of a same predetermined size, wherein the graph bitmap is representative of a graph having a plurality of nodes with each node being represented by a bit indicating whether the node has been visited, and each of the words includes two or more of bits representing nodes of the graph;
constructing an auxiliary bitmap having a plurality of bits with each individual bit corresponding to a respective one of the words of the graph bitmap by, for each individual bit of the auxiliary bitmap, setting the bit to a first logic value if the respective word of the graph bitmap corresponding to the bit matches a predetermined default value and setting the bit to a second logic value if the respective word of the graph bitmap corresponding to the bit does not match the predetermined default value, wherein the predetermined default value is variable and has a first value for a beginning word in the sequence and a second value different from the first value for a last word in the sequence;
constructing a compressed graph bitmap by including in the compressed graph bitmap the words of the graph bitmap corresponding to bits of the auxiliary bitmap that are set to the second logic value but not the words of the graph bitmap corresponding to bits of the auxiliary bitmap that are set to the first logic value;
encoding the auxiliary bitmap; and
transmitting the encoded auxiliary bitmap and the compressed graph bitmap together as a compressed representation of the graph bitmap.

2. The method of claim 1 , wherein the encoding of the auxiliary bitmap is performed using Huffman encoding.

3. The method of claim 1 , wherein constructing the graph bitmap includes first determining whether any nodes of the graph are isolated nodes and identifying any such isolated nodes as visited nodes.

4. The method of claim 1 , wherein, for at least one word of the graph bitmap, the bits of the at least one word represent successive nodes of the graph.

5. The method of claim 1 , wherein, for at least one word of the graph bitmap, the bits of the at least one word represent interleaved nodes of the graph.

6. The method of claim 5 , wherein the interleaved nodes are column interleaved.

7. The method of claim 1 , wherein the words of the graph bitmap are at least partially determined using a breadth-first search.

8. The method of claim 1 , wherein:
the predetermined default value has a size defined by a plurality of bits with the size of the predetermined default value being equal to the predetermined size of each word;
all bits of the predetermined default value are set to zero when the predetermined default value is the first value; and
all bits of the predetermined default value are set to one when the predetermined default value is the second value.

9. A data processing apparatus comprising:
a data output terminal;
memory to store instructions;
a processor to execute the instructions stored in the memory, wherein execution of the instructions by the processor causes the data processing apparatus to:
construct a graph bitmap as a sequence of a plurality of words each being of a same predetermined size, wherein the graph bitmap is representative of a graph having a plurality of nodes with each node being represented by a bit indicating whether the node has been visited, and each of the words includes two or more of bits representing nodes of the graph;
construct an auxiliary bitmap having a plurality of bits with each individual bit corresponding to a respective one of the words of the graph bitmap by, for each individual bit of the auxiliary bitmap, setting the bit to a first logic value if the respective word of the graph bitmap corresponding to the bit matches a predetermined default value and setting the bit to a second logic value if the respective word of the graph bitmap corresponding to the bit does not match the predetermined default value, wherein the predetermined default value is variable and has a first value for a beginning word in the sequence and a second value different from the first value for a last word in the sequence;
construct a compressed graph bitmap by including in the compressed graph bitmap the words of the graph bitmap corresponding to bits of the auxiliary bitmap that are set to the second logic value but not the words of the graph bitmap corresponding to bits of the auxiliary bitmap that are set to the first logic value;
encode the auxiliary bitmap; and
output the encoded auxiliary bitmap and the compressed graph bitmap together as a compressed representation of the graph bitmap via the data output terminal.

10. The data processing apparatus of claim 9 , wherein the encoding of the auxiliary bitmap is performed using Huffman encoding.

11. The data processing apparatus of claim 9 , wherein constructing the graph bitmap includes first determining whether any nodes of the graph are isolated nodes and identifying any such isolated nodes as visited nodes.

12. The data processing apparatus of claim 9 , wherein, for at least one word of the graph bitmap, the bits of the at least one word represent successive nodes of the graph.

13. The data processing apparatus of claim 9 , wherein, for at least one word of the graph bitmap, the bits of the at least one word represent interleaved nodes of the graph.

14. The data processing apparatus of claim 13 , wherein the interleaved nodes are column interleaved.

15. The data processing apparatus of claim 9 , wherein the words of the graph bitmap are at least partially determined using a breadth-first search.

16. The data processing apparatus of claim 9 , wherein:
the predetermined default value has a size defined by a plurality of bits with the size of the predetermined default value being equal to the predetermined size of each word;
all bits of the predetermined default value are set to zero when the predetermined default value is the first value; and
all bits of the predetermined default value are set to one when the predetermined default value is the second value.

Assignees

• Texas Instruments Inc

Inventors

• Mansour Mohamed Farouk

Classifications

• H03M7/70

  Type of the data to be coded, other than image and sound · CPC title

• G06F17/30324

  Physics · mapped topic

• H03M7/46 Primary

  Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind · CPC title

• G06F17/30153

  Physics · mapped topic

• H03M7/40 Primary

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title