APPLICATIONS OF TECHNOLOGY

Highly efficient searching of large scale, dynamically growing databases for:

• multidimensional database applications
• data warehousing/OLAP
• real-time business intelligence
• discovering patterns in semantic networks, e.g. homeland security
• data mining
• transactional database management
• managing time series data

ADVANTAGES

• Performs logical operations on compressed indices as much as ten times faster than one of the fastest known methods: byte-aligned bitmap code (BBC)
• Enables efficient searching of categorical and non-categorical numerical data
• Allows rapid, combined searching over a large number of attributes
• Can be applied easily to computer architectures with any word length

ABSTRACT

Scientists at Berkeley Lab have developed a patented method for searching and managing large-scale, dynamically growing databases that significantly outperforms all other known methods.  Kesheng Wu, Arie Shoshani, and Ekow Otoo have demonstrated that their compute-friendly compression bitmap indexing method, FastBit, performs logical operations as much as ten times faster than the byte-aligned bitmap code (BBC) indexing method, one of the fastest indexing methods currently on the market.  The performance ratio of FastBit is even greater compared to conventional indices used in commercial systems.

The Berkeley Lab indexing method is based on a simple yet elegant word alignment strategy for compressed bitmaps.  The counts used to represent compressed bit sequences are always an integer multiple of bits stored in uncompressed literal words.  This allows common operations to be performed without breaking any literal word, which significantly improves the compute efficiencies on compressed bitmaps.  In addition, answers produced by separate bitmap indexes can be combined easily and efficiently to answer multi-dimensional range conditions.  The FastBit compression scheme significantly reduces the response time to ad hoc queries, which is crucial for efficient advanced data mining operations.  The Berkeley Lab software implementation of this method has been further optimized for in-memory logical operations, and shown to scale on parallel machines.  The software package has been applied successfully to multiple application domains for real-time searches over large-scale datasets.

FastBit offers competitive advantages for any application that demands rapid, ad hoc searching of large, dynamically growing datasets.  Such applications include data warehousing, performing exploratory data mining search and business intelligence functions, and discovering patterns in semantic networks.

STATUS:

• U.S. Patent #6,831,575. Available for licensing

FOR MORE INFORMATION:

• FastBit: An Efficient Compressed Bitmap Index Technology
• FastBit : An Efficient Indexing Technology for Accelerating Data-Intensive Science
• "Berkeley Lab Technology Dramatically Speeds Up Searches of Large Databases," LBNL Research News, May 16, 2005

FastBit in the news:

• http://news.taborcommunications.com/msgget.jsp?mid=561069&xsl=story.xsl
• http://cerncourier.com/main/article/45/7/24/1

REFERENCE NUMBER: IB-1852