Bitmap index compression

US6205442A · kind A · utility

Assignee

• Oracle Corporation · US

Inventors

• Jeffrey Ira Cohen · Sunnyvale, US
• Michael Depledge · San Jose, US
• Hakan Jakobsson · San Francisco, US
• Mark Kremer · Sunnyvale, US
• Cetin Ozbutun · Redwood City, US
• Quoc Tai Tran · Mountain View, US

Key dates

• Filing date: May 13, 1999
• Grant date: Mar 20, 2001
• Expiry date: May 13, 2019

Classification

• Technology area (CPC Y): Emerging Cross-Sectional Technologies
• CPC primary: Y10S707/99937
• WIPO field: Basic communication processes
• WIPO sector: Electrical engineering

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.