Lossless compression method for graph traversal

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.

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.