Decoding billions of integers per second through vectorization

By Daniel Lemire, Leonid Boytsov. Software, Practice & Experience, 2012

345 citations recorded by the source corpus.

In many important applications—such as search engines and relational database systems—data are stored in the form of arrays of integers. Encoding and, most importantly, decoding of these arrays consumes considerable CPU time. Therefore, substantial effort has been made to reduce costs associated with compression and decompression. In particular, researchers have exploited the superscalar nature of modern processors and single‐instruction, multiple‐data (SIMD) instructions. Nevertheless, we introduce a novel vectorized scheme called SIMD‐BP128⋆ that improves over previously proposed vectorized approaches. It is nearly twice as fast as the previously fastest schemes on desktop processors (varint‐G8IU and PFOR). At the same time, SIMD‐BP128⋆ saves up to 2 bits/int. For even better compression, we propose another new vectorized scheme (SIMD‐FastPFOR) that has a compression ratio within 10% of a state‐of‐the‐art scheme (Simple‐8b) while being two times faster during decoding. © 2013 The Authors. Software: Practice and Experience Published by John Wiley & Sons, Ltd.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/66713fbcb8d5e48a9eb6425bd7fdbb53751e60b1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Query Driven Algorithm Selection in Early Stage Retrieval (2017, background): “The key observation in Bmw is that since many index compression algorithms are block-based [30, 58], skipping can be achieved at the block level, thus saving an entire block decompression.”
Efficiency Implications of Term Weighting for Passage Retrieval (2020, methodology): “Indexes were compressed in fixed-sized blocks of 128 elements with SIMD-BP128 [12], which was recently shown to give good time-space trade-offs during decoding [12, 16].”
A Comparison of Document-at-a-Time and Score-at-a-Time Query Evaluation (2017, methodology): “Finally, we reflect on the characteristics of the different query evaluation algorithms in light of modern processor architectures.”
Anytime Ranking for Impact-Ordered Indexes (2015, methodology): “Experiments [17] have shown QMX to be more eﬃcient to decode than SIMD-BP128 [13] (previously the most decoding eﬃcient overall) and competitive with all SIMD and non-SIMD techniques in terms of size.”
High Speed Lossless Image Compression (2015, methodology): “2, but the scheme still has to overcome several hurdles compared to the bit packing method using 32 bit integers from [14]: Less latitude: For image data, the bit depth is normally 8 bit compared to at least 32 bit in database indices, so each additional bit needed for the encoding has four times th”