<$BlogRSDUrl$> Marcus P. Zillman, M.S., A.M.H.A. Author/Speaker/Consultant
Marcus P. Zillman, M.S., A.M.H.A. Author/Speaker/Consultant
Internet Happenings, Events and Sources


Wednesday, June 01, 2005  



Berkeley Lab Technology Dramatically Speeds Up Searches of Large Databases
http://www.lbl.gov/Science-Articles/Archive/CRD-STAR.html

The technology, known as the Word-Aligned Hybrid (WAH) compression method, was developed and recently patented by John Wu, Arie Shoshani and Ekow Otoo of Berkeley Lab’s Scientific Data Management (SDM) Research Group. The technique and its application are described in a paper recently selected as a “best paper” by the International Supercomputer Conference, and Wu will present the paper at the conference to be held June 21-24 in Heidelberg, Germany. WAH is currently used in a software package called FastBit to compress bitmap indexes. A bitmap index is a method of reducing the response time of queries involving common types of conditions in data objects, such as "state = CA" and "age >= 21." It achieves this by storing certain pre-computed answers as bitmaps. For example, a bitmap index for "state" might have one bitmap for each state in the U.S. Because computers can manipulate bitmaps efficiently, bitmap indices are efficient in searching for interesting records in large datasets. WAH compression makes the bitmap index optimal in terms of computational complexity. A small number of the most efficient indexing schemes have this optimality property. What makes the new technology unique is that WAH-compressed indexes significantly outperform other schemes in tests. “In tests conducted using actual data from high-energy physics experiments, we confirmed that our FastBit software is an order of magnitude faster than the best-known bitmap indexing schemes on average,” according to Wu, the lead developer of FastBit.

posted by Marcus Zillman | 4:00 AM
archives
subject tracers™