advertise
« STRUCTURE 09 IS BACK! | Main | Presentations: MySQL Conference & Expo 2009 »
Friday
May012009

FastBit: An Efficient Compressed Bitmap Index Technology

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

 

  • FastBit: Digging through databases faster. An excellent description of how FastBit works, especially compared to b-trees.
  • References (1)

    References allow you to track sources for this article, as well as articles that were written in response to this article.

    Reader Comments (3)

    is it faster than an in memory bitfield lookup in an array of bitfields? :)

    -=r

    November 29, 1990 | Unregistered Commenterroger

    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

    November 29, 1990 | Unregistered CommenterAnonymous

    Thanks for the great article! Also wanted to share this one on bitmap indexes:

    Bitmap index

    September 13, 2013 | Unregistered CommenterPrerna

    PostPost a New Comment

    Enter your information below to add a new comment.
    Author Email (optional):
    Author URL (optional):
    Post:
     
    Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>