"In a number of tests, we observed that our indexing scheme can answer range queries tens of times faster than the well-known indexing schemes." - Tracy

Using bitmap indices, range queries can be answered with bitwise logical operations. Since bitwise logical operations are generally very well supported by computer hardware, uncompressed bitmaps involving relatively smaller number of bitmaps can be efficiently answered. In most scientific applications, the number of bitmaps in a bitmap index is typically large, say more than 1000. This causes the uncompressed bitmaps to be very large. Our compression scheme addresses the size problem by reducing the compressed size to the level that is below a typical B-tree implementation [3]. In addition, because our compression scheme supports fast bitwise logical operations on the compressed bitmaps, the time to answer a one-dimensional range query is a linear function of the number of hits [3]. This is theoretically optimal, since any system to answer a query must at least list all the hits and therefore has the same theoretical time complexity as our approach. This theoretical property is remarkable as only a few most efficient indexing schemes including B+tree and B*tree have it. There are two factors that make FastBit even more remarkable. Since answers to one-dimensional queries produced from bitmap indices can be easily combined to answer multi-dimensional queries, bitmap index scheme that is efficient for one-dimensional range queries is also efficient for multi-dimensional range queries. The same is not true for other optimal indexing schemes. In addition, FastBit is not only theoretically efficient; it is also efficient in tests involving various different application datasets - Tracy