  Compressed inverted indices in use today are based on the idea of gap
compression: documents pointers are stored in increasing order, and the gaps
between successive document pointers are stored using suitable codes which
represent smaller gaps using less bits. Additional data such as counts and
positions is stored using similar techniques. A large body of research has been
built in the last 30 years around gap compression, including theoretical
modeling of the gap distribution, specialized instantaneous codes suitable for
gap encoding, and ad hoc document reorderings which increase the efficiency of
instantaneous codes. This paper proposes to represent an index using a
different architecture based on quasi-succinct representation of monotone
sequences. We show that, besides being theoretically elegant and simple, the
new index provides expected constant-time operations and, in practice,
significant performance improvements on conjunctive, phrasal and proximity
queries.
