Lossless Compression Method for Graph Traversal

Patent metadata

Field	Value
Publication number	US-2017346503-A1
Application number	US-201615168992-A
Country	US
Kind code	A1
Filing date	May 31, 2016
Priority date	May 31, 2016
Publication date	Nov 30, 2017
Grant date	—

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 lossless compression comprising the steps of:
creating a graph bitmap where each node of a graph is represented by a single bit indicating whether said node has been visited or not; combining said bits into arbitrary length words; selecting a default value of all zeroes or all ones; creating an auxiliary bitmap where each bit represents a word in said graph bitmap; setting each bit in said auxiliary bitmap to 0 or 1 indicating whether the corresponding word in the graph bitmap matches said preselected default value; Huffman encoding said auxiliary bitmap; transmitting as the output of the compression algorithm the encoded auxiliary bitmap and the graph bitmap words indicated as not default by the auxiliary bitmap.

2 . The method of claim 1 , wherein:
all isolated nodes are marked as visited during the creation of said graph bitmap.

3 . The method of claim 1 , wherein:
said nodes may be consecutive or interleaved during the creation of said graph bitmap.

4 . An apparatus for lossless compression comprising of:
a processor operable to: create a graph bitmap where each node of a graph is represented by a single bit indicating whether said node has been visited or not; combine said bits into arbitrary length words; select a default value of all zeroes or all ones; create an auxiliary bitmap where each bit represents a word in said graph bitmap; set each bit in said auxiliary bitmap to 0 or 1 indicating whether the corresponding word in the graph bitmap matches said preselected default value; Huffman encode said auxiliary bitmap; transmit as the output of the compression algorithm the encoded auxiliary bitmap and the graph bitmap words indicated as not default by the auxiliary bitmap.

5 . The apparatus of claim 4 , further operable to mark all isolated nodes as visited during the creation of said graph bitmap.

6 . The apparatus of claim 4 , wherein said processor is further operable to arrange said nodes to be consecutive or interleaved during the creation of said graph bitmap.

Assignees

• Texas Instruments Inc

Inventors

• Mansour Mohamed Farouk

Classifications

• 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

• H03M7/70

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

• G06F16/1744

  using compression, e.g. sparse files · CPC title

• H03M7/40 Primary

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

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title