SIMD Compression and the Intersection of Sorted Integers. arXiv:1401.6399, 2014 [10

Sorted lists of integers are commonly used in inverted in-dexes 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 com-pression schemes. By making use of superscalar execution together with vectorization, our S4-BP128-D4 scheme uses as little 0.7 CPU cycles per decoded integer while still pro-viding 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) vec-torize and optimize the intersection of posting lists; (2) in-troduce the SIMD Galloping algorithm. We exploit the fact that one SIMD instruction can compare 4 pairs of inte-gers at once. We experiment with two TREC text collections, GOV2 and ClueWeb09 (Category B), using logs from AOL and 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