Skip to Content
Find More Like This
Return to Search

Word aligned bitmap compression method, data structure, and apparatus

United States Patent

December 14, 2004
View the Complete Patent at the US Patent & Trademark Office
Lawrence Berkeley National Laboratory - Visit the Technology Transfer and Intellectual Property Management Department Website
The Word-Aligned Hybrid (WAH) bitmap compression method and data structure is a relatively efficient method for searching and performing logical, counting, and pattern location operations upon large datasets. The technique is comprised of a data structure and methods that are optimized for computational efficiency by using the WAH compression method, which typically takes advantage of the target computing system's native word length. WAH is particularly apropos to infrequently varying databases, including those found in the on-line analytical processing (OLAP) industry, due to the increased computational efficiency of the WAH compressed bitmap index. Some commercial database products already include some version of a bitmap index, which could possibly be replaced by the WAH bitmap compression techniques for potentially increased operation speed, as well as increased efficiencies in constructing compressed bitmaps. Combined together, this technique may be particularly useful for real-time business intelligence. Additional WAH applications may include scientific modeling, such as climate and combustion simulations, to minimize search time for analysis and subsequent data visualization.
Wu; Kesheng (Fremont, CA), Shoshani; Arie (Berkeley, CA), Otoo; Ekow (Albany, CA)
The Regents of the University of California (Oakland, CA)
10/ 701,655
November 4, 2003
STATEMENT REGARDING FEDERAL FUNDING This invention was made with U.S. Government support under Contract Number DE-AC03-76SF00098 between the U.S. Department of Energy and The Regents of the University of California for the management and operation of the Lawrence Berkeley National Laboratory. The U.S. Government has certain rights in this invention.