Browse Prior Art Database

Set of Algorithms for Performing Logical Operations On Compressed Bitmaps

IP.com Disclosure Number: IPCOM000100196D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 6 page(s) / 177K

Publishing Venue

IBM

Related People

Kearney, MP: AUTHOR

Abstract

Disclosed is a set of programs that perform logical operations such as OR, AND, and XOR, on compressed bitmaps in their compressed form. Existing algorithms must uncompress a bitmap before manipulating it. The algorithms are: Add_a_bit; Or_two_trees; Xor_two_trees; And_two_trees; Split_a_tree; Skip_a_level; and Copy_a_level.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Set of Algorithms for Performing Logical Operations On Compressed Bitmaps

       Disclosed is a set of programs that perform logical
operations such as OR, AND, and XOR, on compressed bitmaps in their
compressed form.  Existing algorithms must uncompress a bitmap before
manipulating it.  The algorithms are:  Add_a_bit; Or_two_trees;
Xor_two_trees; And_two_trees; Split_a_tree; Skip_a_level; and
Copy_a_level.

      How The Compressed Bitmap is Stored: A compressed bitmap can be
visualized as a tree.  The order of the tree is equal to the length,
in bits, of each node in the tree.  The example in Fig. 1 shows the
order of the tree as eight.  This is convenient because eight bits
make a byte, but are not required.  The bits are numbered from 0 to
n-1, where n is the length of the node.  The value of a bit is
given by Equation 1.

      The value of bit 0 in node 3 of level 0 of the example
tree is:  8(0) x 0 + 8(1) x 1 + 8(2) x 0 = 8.
The example tree can represent numbers between 0 and 8(3) = 512.  A
tree with 7 levels and a node length of 8 can represent numbers
between 0 and 7(8) = 5,764,801.

      The compressed bitmap is stored in memory in an array of nodes.
 The nodes are stored in pre-order traversal form. To do a pre-order
traversal of the tree in Fig. 1:
1.   Visit the root node of the tree.  In the example the

      root node is node 1.
2.   Traverse the left-most subtree.
3.   After traversing the left-most subtree, traverse the next left-
most subtree and so on until the right-most subtree has been
traversed.

      The result of a pre-order traversal of the sample tree in Fig.
1 is shown in Fig. 2.

      Note:  No pointers or counters have been stored in the array of
nodes.  This means that no extra memory is used for the bookkeeping
pointers and counters.  The amount of memory saved is significant
when storing thousands or millions of nodes.

      A bitmap too large to store in a single record or to keep in
memory must be segmented.  The record is segmented across the tree.
In the sample tree in Fig. 1 the segmenting could occur between
levels 0 and 1 or between levels 1 and 2.  If the tree was segmented
between levels 1 and 2, the result would be five segments:
     ...