Friday
May012009
FastBit: An Efficient Compressed Bitmap Index Technology
Friday, May 1, 2009 at 1:42AM Data mining and fast queries are always in that bin of hard to do things where doing something smarter can yield big results. Bloom Filters are one such do it smarter strategy, compressed bitmap indexes are another. In one application "FastBit outruns other search indexes by a factor of 10 to 100 and doesn’t require much more room than the original data size." The data size is an interesting metric. Our old standard b-trees can be two to four times larger than the original data. In a test searching an Enron email database FastBit outran MySQL by 10 to 1,000 times.
FastBit is a software tool for searching large read-only datasets. It organizes user data in a column-oriented structure which is efficient for on-line analytical processing (OLAP), and utilizes compressed bitmap indices to further speed up query processing. Analyses have proven the compressed bitmap index used in FastBit to be theoretically optimal for one-dimensional queries. Compared with other optimal indexing methods, bitmap indices are superior because they can be efficiently combined to answer multi-dimensional queries whereas other optimal methods can not.
It's not all just map-reduce and add more servers until your attic is full.
Related Articles
Reader Comments (3)
is it faster than an in memory bitfield lookup in an array of bitfields? :)
-=r
Hi, Roger,
FastBit is intended to work with data that are too large to be stored in memory and are required to persist over time. Depending on how the bit field you've mentioned is organized, it might be possible to reorganize them the same way FastBit organizes the bitmaps in the indexes. It might also be possible to apply compression used by FastBit to reduce the memory footprint and increase performance at the same time.
John
Thanks for the great article! Also wanted to share this one on bitmap indexes:
Bitmap index