Aug 22, 2005
WAH compression speeds up searches
A new technique to quickly locate interesting "rare events" out of hundreds of millions of particle collisions was presented at the International Supercomputer Conference, held on 21-24 June in Heidelberg. This search technology, known as the Word-Aligned Hybrid (WAH) compression method, was developed and recently patented by John Wu, Arie Shoshani and Ekow Otoo of Lawrence Berkeley National Laboratory.
WAH is currently used in a software package called FastBit to compress bitmap indexes. These provide a method of reducing the response time of queries involving common types of conditions in data objects, by storing pre-computed answers as bitmaps. Because computers can manipulate bitmaps efficiently, bitmap indices efficiently search for interesting records in large datasets.
"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," says Wu, the lead developer of FastBit.
The effectiveness of FastBit has attracted the attention of other institutions. At CERN, the developers of ROOT, an object-oriented data-analysis framework, have started evaluating the incorporation of FastBit into their software. Since the ROOT software is used by most major high-energy physics projects around the world, fully integrating FastBit into ROOT would make the efficient search capability of FastBit available to a large user community.
Compiled by Hannelore Hämmerle and Nicole Crémel