  Sorted lists of integers are commonly used in inverted indexes and database
systems. They are often compressed in memory. We can use the SIMD instructions
available in common processors to boost the speed of integer compression
schemes. Our S4-BP128-D4 scheme uses as little as 0.7 CPU cycles per decoded
integer while still providing state-of-the-art compression.
  However, if the subsequent processing of the integers is slow, the effort
spent on optimizing decoding speed can be wasted. To show that it does not have
to be so, we (1) vectorize and optimize the intersection of posting lists; (2)
introduce the SIMD Galloping algorithm. We exploit the fact that one SIMD
instruction can compare 4 pairs of integers at once.
  We experiment with two TREC text collections, GOV2 and ClueWeb09 (Category
B), using logs from the TREC million-query track. We show that using only the
SIMD instructions ubiquitous in all modern CPUs, our techniques for conjunctive
queries can double the speed of a state-of-the-art approach.
