US 6,205,442 B1 · Bitmap index compression

Abstract

A method and apparatus for compressing data is provided. The invention compresses an input bit stream into a compressed output bit stream. The input bit streams are byte aligned and classified. Bytes with all bits set to value zero are classified as gap bytes. Bytes with only one bit set to value one are classified as offset bytes. All other bytes are classified as map bytes. Groups of adjacent bytes are organized into two types of groups. The first type is a gap bit group. A gap map group contains gap bytes and one offset byte. The second type is the gap map group. It contains gap bytes and map bytes. The number of gap bytes in a group is called a gap size. The groups are compressed into four types of atoms. Each type of atom has one control byte, zero or more gap size bytes, and zero or map bytes. A control byte describes the atom. The map bytes in an atom are copies of the map bytes in the control group.

Claims19

Dependent claims

A computer-readable media containing compressed output, comprising:

compressed sets of one or more bit sequences that represent groups of bit sequences;
wherein each bit sequence of said groups of bit sequences contains an identical number of bits;
wherein each group of bit sequences of said groups of bit sequences includes either a gap bit sequence,
an offset bit sequence, or
a map bit sequence;
and
wherein at least one compressed set of one or more bit sequences of said compressed sets contains a set of one or more gap size bit sequences, wherein each gap size bit sequence of said set of one or more gap size bit sequences includes a flag, wherein said flag indicates whether a subsequent gap size bit sequence follows within said at least one compressed set.

4 more elements

A computer-readable media containing compressed output, comprising:

compressed sets of one or more bit sequences that represent groups of bit sequences;
wherein each bit sequence of said groups of bit sequences contains an identical number of bits;
wherein each group of bit sequences of said groups of bit sequences includes either
a gap bit sequence,
an offset bit sequence, or
a map bit sequence;
and
wherein each compressed set of one or more bit sequences of said compressed sets contains a set of one or more gap size bit sequences, wherein said control bit sequence contains a field representing a range of numbers, wherein said range of numbers includes a first subrange and a second subrange;
wherein a first subgroup of said group of bit sequences has a first bit sequence with one bit set to value one and said field set to a particular value within said first subrange, wherein said value represents the gap size of said group;
and
wherein a second subgroup of said group of bit sequences has a second bit sequence with one bit set to value one and said field set to a particular value within said second subrange, wherein said value represents the gap size of said second group, and wherein the gap size of said second subgroup and said first subgroup are the same.

8 more elements

Dependencies are inferred from the claim text.

Bitmap index compression

Life of this patent

Bitmap index compression

Life of this patent

Abstract

Claims19