  The data structure at the core of large-scale search engines is the inverted
index, which is essentially a collection of sorted integer sequences called
inverted lists. Because of the many documents indexed by such engines and
stringent performance requirements imposed by the heavy load of queries, the
inverted index stores billions of integers that must be searched efficiently.
In this scenario, index compression is essential because it leads to a better
exploitation of the computer memory hierarchy for faster query processing and,
at the same time, allows reducing the number of storage machines. The aim of
this article is twofold: first, surveying the encoding algorithms suitable for
inverted index compression and, second, characterizing the performance of the
inverted index through experimentation.
