I'm one of the authors of the paper they compare against (Partitioned Elias-Fano), and since I saw the StrangeLoop talk I've been curious to see a more detailed description of the index, so I was very eager to read the paper as soon as it came out.

I think it's an interesting approach, but I have a few questions about its practical applicability.

For one, space utilization seems to be a serious issue: bits per posting are more than double than the Elias-Fano indexes in their experiments, and furthermore, they claim that they used the Java Partitioned Elias-Fano implementation of MG4J, but MG4J does not have one! It only has an Elias-Fano index; since they get the same space from PEF and MG4J, this means that either they are using a random ordering of the document identifiers (otherwise they'd get another 2x improvement from PEF with proper docid ordering) or they're misusing the PEF code.

Also, they claim to use 5 corpora, but they're actually 5 slices of the same corpus (Gov2), sharded by document size classes, so both the collection sizes and document sizes vary and it's not easy to correlate them with the observed performance characteristics. A trend shows up anyway, that as the collection size grows the performance difference between BitFunnel and EF-based indexes gets thinner, which suggests that on very large collections they might even cross. This is not surprising, as BitFunnel query execution is linear in the collection size, while inverted indexes have empirical performance closer to the number of returned results. Also, I could not find in the paper the exact definition of "false positive rate": is the denominator the number of results, or the number of documents in the collection?

The experiments are on a 4-core desktop-class machine; would the results hold up on, say, a recent 28-core Xeon processor, or the memory throughput would become the bottleneck given that scanning the Bloom filters requires to go through a large fraction of the data?

I got the impression that a good use case for BitFunnel is not to replace inverted indexes altogether, but just for the "fresh" part of a large index (say, newly crawled documents). In that case we have fast insertion of new documents, and a small collection (where the performance gap with inverted indexes seems to be high). However, there does not seem to be an efficient way to update existing documents (add/remove terms), because changing the term set could change the document size shard.