This may be old news, but I recently came across an interesting approach to compressed bit vectors: http://sdm.lbl.gov/fastbit/
They describe ways of using Bit Vectors for range queries that I hadn't considered, as well as a compression scheme that tries to work efficiently with modern CPUs. They also describe tests of using multiple bit vectors as a fast replacement for an inverted index! General intro: http://crd-legacy.lbl.gov/~kewu/ps/LBNL-2164E.pdf "Word Aligned Hybrid" compression: http://crd-legacy.lbl.gov/~kewu/ps/LBNL-49627.pdf Bit maps as alternative to inverted index: http://crd-legacy.lbl.gov/~kewu/ps/LBNL-61768.pdf --nate
