Block-aware encoding of bitmap for bitmap index eliminating...

Details Block-aware encoding of bitmap for bitmap index eliminating... Block-aware encoding of bitmap for bitmap index eliminating...

2005-10-25

2008-12-16

LeRoux, Etienne P (Department: 2169)

Data processing: database and file management or data structures

Database design

Data structure types

C341S050000, C341S051000, C341S055000, C341S092000, C341S095000, C707S793000, C707S793000, C708S210000, C708S211000, C708S212000, C710S068000

Reexamination Certificate

active

07467150

ABSTRACT:
Under block-aware encoding, a bitmap represented by atoms comprises a series of bitmaps for each data block in a database. Each bitmap in the series is referred to herein as a block bitmap. Each block bitmap may have a different number of bytes or bits. Gaps are represented in atoms using a pair of numbers referred to as a gap code. A gap code includes a block-skip code and slot-skip code. A block-skip code represents how many block bitmaps to advance to reach a subsequent block bitmap; a slot-skip code represents how many bytes to advance within the block bitmap to reach a byte with at least one bit set. A gap code is represented by bit positions within a byte, with some bit positions allocated to represent the block-skip code and some to represent the slot-skip code. The allocation is adjusted dynamically during encoding and decoding.

REFERENCES:
patent: 4626829 (1986-12-01), Hauck
patent: 5363098 (1994-11-01), Antoshenkov
patent: 5884307 (1999-03-01), Depledge et al.
patent: 5903888 (1999-05-01), Cohen et al.
patent: 5924088 (1999-07-01), Jakobsson et al.
patent: 6205442 (2001-03-01), Cohen et al.
patent: 6405187 (2002-06-01), Egan et al.
Bookstein et al., Models of Bitmap Generation: A Systematic Approach to Bitmap Compression, 1992, Information Processing & Management, pp. 1-20.
Wu et al., A Performance Comparison of bitmap indexes, 2001, Association for Computing Machinery, pp. 1-3.
Wu et al, On the Performance of Bitmap Indices for High Cardinality Attributes, Mar. 5, 2004, Lawrence Berkeley National Laboratory, pp. 1-17.
Koudas, Nick, Space Efficient Bitmap Indexing, 2000, ACM, pp. 1-8.
Wu et al., Using Bitmap Index for Interactive Exploration of Large Datasets, 2003, IEEE, pp. 1-10.
Moffat et al., Space-Efficient Construction Of Optimal Prefix Codes, 1995, IEEE, pp. 1-10.
Wu et al., Compressing Bitmap Indexes for Faster Search Operations, 2002, IEEE, pp. 1-10.
Wu et al., An Efficient Compression Scheme For Bitmap Indices, Apr. 13, 2004, Lawrence Berkeley National Laboratory, pp. 1-27.
Antoshenkov, Gennady, Byte-Aligned Bitmap Compression, 1995, IEEE, p. 1.
Pinar et al., Compressing Bitmap Indices by Data Reorganization, 2005, pp. 1-12.
Buchmann et al., Encoded Bitmap Indexing for Data Warehouses, Feb. 23-27, 1998, DVS1, pp. 1-11.
Wu et al., Compressed bitmap indices for efficient query processing, date: unknown, Lawrence Berkeley National Laboratory, pp. 1-16.
IBM Corporation, “IBM eServer iSeries Support: Software Technical Document: 13511033 [online]”. Retrieved on Jan. 27, 2006. Retrieved from the Internet: http://www-912.ibm.com/s—dir/slkbase.NSF/lac66549a2140218862..., 2 pages.
IBM Corporation, “DB2 UDB for iSeries Database Performance and Query Optimization V5R2, Bitmap processing method [online]”. Retrieved on Jan. 27, 2006. Retrieved from the Internet: http://publib.boulder.ibm.com/iseries/v5r2/ic2924/info/rzajq/rzajpm..., pp. 1-5.
IBM Corporation, “DB2 UDB for iSeries Database Performance and Query Optimization V5R2, What are encoded vector indexes?[online]”. Retrieved on Jan. 27, 2006. Retrieved from the Internet: http://publib.boulder.ibm.com/iseries/v5r2/ic2924/info/rzajq/rzajqm..., pp. 1-5.
Chee-Yong Chan et al., “Bitmap Index Design and Evaluation,” pp. 1-12. Date: Unknown.
IBM Corporation, Michael W. Cain, “Indexing and Statistics Strategies for DB2 UDB for iSeries, Version 3.0,” Updated Nov. 2003, 63 pages.
Oracle Press Release, “Oracle 7 Release 7.3 Extends Oracles's Lead in Data Warehousing Market”, Apr. 30, 1998, 3 pages.
Oracle Press Release, “Oracle to Host First Developer Conference: Preview New Products”, May 6, 1998, DBMS, vol. 8, No. 13, 4 pages.
Martin Rennhackkamp, “DBMS Server Comparison Supplement Server Review Evaluation”, Oracle 7 7.3 and Universal Server, DBMS vol. 9, No. 12, Nov. 1996, 5 pages.
Broadbase Information Systems, Inc. letter to Peter C. Mei, Oracle Corporation, Jul. 9, 1997, 2 pages.
U.S. Appl. No. 08/808,560, Rule 1.132 Declaration from Hakan Jakobsson, filed Sep. 17, 1998, 3 pages.
U.S. Appl. No. 08/808,560, Office Action Summary mailed May 13, 1998, 4 pages.

Affiliated with

Also associated with

Rating

Block-aware encoding of bitmap for bitmap index eliminating... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Block-aware encoding of bitmap for bitmap index eliminating..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block-aware encoding of bitmap for bitmap index eliminating... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4027167