Yann Barsamian
email: yann.barsamian@teacher.eursc.eu

André Chailloux
email: andre.chailloux@inria.fr

Compressing integer lists with Contextual Arithmetic Trits

Inverted indexes allow to query large databases without needing to search in the database at each query. An important line of research is to construct the most efficient inverted indexes, both in terms of compression ratio and time efficiency. In this article, we show how to use trit encoding, combined with contextual methods for computing inverted indexes. We perform an extensive study of different variants of these methods and show that our method consistently outperforms the Binary Interpolative Method -which is one of the golden standards in this topic -with respect to compression size. We apply our methods to a variety of datasets and make available the source code that produced the results, together with all our datasets. 1

Introduction

When faced with a large database, storing the information contained in its documents is one of the concerns, but the most prominent one is searching the database. One of the standard tools to help queries is an inverted index. Each document in the database has an associated identifier, and the index stores, for each word, the (sorted) list of identifiers whose associated documents contain this word. A sorted list of this kind is known as a posting list.

Techniques for efficiently representing those posting lists have to reach a difficult balance between two main parameters: the size of the inverted index, and the time needed to query it. For instance, the cmix compression algorithm [START_REF] Knoll | cmix[END_REF] is extremely space efficient but constructing and querying the inverted index takes a prohibitive amount of time -22 hours for a few MB. Regarding more efficient algorithms, the technique that yielded the best compression ratio was the Binary Interpolative Method [START_REF] Moffat | Exploiting clustering in inverted file compression[END_REF] from 1996 -where a few MB are handles in a few seconds. Its compression ratio has been recently outperformed, on some datasets, by the Packed+ANS2 method [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF].

In this article, we focus on the size of the resulting index, i.e., we focus on the compression ratio but for algorithms with a running time comparable to the Binary Interpolative Method. We present a representation for the posting lists (transformation into a trit list) that consistently outperforms those methods (up to 13%) on databases ranging from a few MB (e.g., personal e-mails) to many GB (e.g., large Information Retrieval databases employed for the World Wide Web).

We make available the source code that produced the results, together with all our datasets.

Formal statement of the problem

We want to answer the following question: what is the best compression algorithm that can be crafted, that targets inverted indexes? The posting lists we want to compress can each be viewed as a binary matrix, where the bit 0 means that the word does not appear in the document and the bit 1 means that the word appears in the document 1 . An example is given in Figure 1. 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 2 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 3 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 5 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 1 Storing this full table requires nbWords * nbDocuments bits, which is 80 bits in this example 2 . This would be fine if we had to encode any kind of binary table but those arising from inverse indexes have much more structure. Exploiting this structure has been the key for deriving more and more successful compression algorithms. We present below two kinds of structure that are identified and exploited in most real life posting lists.

Words

     

Sparcity and Clustering

Sparcity. The most frequent structure that we see is that inverse indexes are very sparse. Typically, in the databases we consider, posting lists have an average density below 0.3%. This means it is more efficient to store the list of documents IDs (i.e.the position of 1s) in which each word appears. Since these form an increasing sequence for each word, it is often more efficient store the gaps between each document ID and to work on the corresponding gap lists. The matrix given in Figure 1 thus becomes the arrays in Figure 2, where the transformation between position and gaps is pictured. Most efficient methods work on the gap lists, even though one of the best-performing ones, the Binary Interpolative Method [START_REF] Moffat | Exploiting clustering in inverted file compression[END_REF], works directly on the document lists.

Clustering. Inverted indexes have a property which is called clustering: the 1s appearing in the gap lists are much closer to each other than what they should be if the document IDs were uniformly distributed. This depends of course on the ordering of the documents and can be explained as follows: suppose for example that the documents are newspaper articles sorted by date. If a tornado happens at a current date then the word 'tornado' will appear in many articles close together i.e.close to this date, but will appear rarely at other times. This clustering implies not only that small gaps appear more often but also that they are close to each other on average. Using this structure is the key for giving the most efficient compression algorithms.

Different performance measures for posting list compression

There are two main aspects that we can care about when compressing. First, of course is the size of the compression: the smaller the size, the better the compression algorithm is. We can also be interested in efficiency but here, many questions arise: do we care about the time to build the index? to decompress it? to query it? if so on which kind of queries? This makes comparing different compression algorithms difficult because each of them has different upsides and downsides.

In this work, we are mostly interested in the first aspect, i.e.the space efficiency of the compression algorithm. We take everything into account when measuring the size of the compressed database and the results we provide correspond to actual file sizes from which we can recover the original posting lists.

Concentrating mainly on the compression efficiency is really advantageous regarding benchmarking. Indeed, the same compress list compressed using a specific algorithm should yield the same result independently on the code, or the computer it runs on. This makes it therefore very easy to compare the compression performance of different algorithms. This is contrast with timing benchmarks which vary depending on implementation and hardware.

State of the art

Even though some compression techniques encode the gaps one by one, most compression techniques take advantage of local properties of the posting lists. One way to do it is to encode the posting lists by blocks (methods that resort to this technique sometimes dynamically adapt the block sizes to enhance the compression ratio), another way to do it is to search similarities between the posting lists in order to reorder the document IDs. A large portion of the state-of-the-art also covers ways to speed up the encoding, the decoding, and/or the queries in the index; usually, this hinders compression performance, sometimes by a factor that can be greater than 2.

Before this article, the state-of-the-art techniques that yielded the best compression ratios were the Binary Interpolative Coding (Interp) [START_REF] Moffat | Exploiting clustering in inverted file compression[END_REF] and the Packed+ANS2 method [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF]. For 20 years, Interp was undefeated, and it is only recently that, on some datasets, it has been outperformed. There has then been an extensive amount of work to improve compression algorithms but only Packed+ANS2 outperformed Interp regarding compression ratio; as we will show, if one is only interested in the compression ratios, the gains are lesser than what was shown in the article presenting the Packed+ANS2 method, and are not present on all kinds of datasets.

" [W]e have shown that the two-decade-old benchmark set by Interp can be consistently beaten, a milestone outcome for index compression.

"

Another recent paper [START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF] claimed to match and even outperform Interp on some datasets. While reproducing these results, however, we found out that this was not the case. In short, we view their idea mostly as a reordering method which is outperformed by another one, namely the graph bisection algorithm [9].

We reproduced the results of the two papers we just mentioned [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF][START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF] by using the code they provide. By doing so, we found some minor issues that explains why we thought that a more careful analysis of their results was necessary: First, they use the same base code from [21] and since they operate on gap blocks (of size 128 or 256), they rightfully compare their methods to a variant of Interp: Block-Interp. However, the Block-Interp implementation they use stores useless information that hinders its compression ratio. In short, the authors compare to a non-optimal version of Block-Interp 3 . Comparing to the best Block-Interp method changes the claims made. Second, both these articles use only 2 posting lists for comparison: Gov2 and ClueWeb09. Moreover, those posting lists are truncated in both articles (posting lists of size less than 128 are excluded in [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF], and posting lists of small size are removed in [START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF] until 10% of the posting are removed4 ). Finally, these results do not use the best method for document reordering, namely the graph bisection algorithm [9].

In conclusion, we consider that the Interp and the Packed+ANS2 methods are the two best compression algorithm for posting lists in terms of pure compression performance, and most of our results will therefore only mention those two methods -we give in Appendix A comparisons against more methods to prove this claim.

Contributions

Our paper may be viewed as the happy wedding between trits -as exploited by Elias in 1955 [39, p. 31] -and a coding satisfying Shannon's theorem [START_REF] Shannon | A Mathematical Theory of Communication[END_REF]. We chose arithmetic coding, as also described by Elias [36, pp. 61-62], to match as closely as possible the entropy. We note that Asymmetric Numeral Systems (ANS) [START_REF] Duda | Asymmetric Numeral Systems[END_REF] could also have been chosen, if one wishes to have quicker running times and is willing to lower the compression ratios. First, we transform each gap array to a trit list, then we encode this trit list with an arithmetic contextual method: the knowledge of the last trits gives a good insight into the possible values of the next ones.

We note that previous works on inverted index compression also used contextual encodings: contextual arithmetic encoding on bit vectors [START_REF] Bookstein | Modeling Word Occurrences for the Compression of Concordances[END_REF], contextual arithmetic encoding on words [START_REF] Moffat | Word-based text compression[END_REF], contextual ANS encoding on the result of binary packing blocks of integers [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF]. Most of the previous works make two passes on the dataset. One to set the model, and one to encode the dataset with the model (static arithmetic coding). In this article, we used static arithmetic coding but also adaptive arithmetic coding, that requires only one pass over the dataset, and turned out to give better compression rates on most cases.

From a theoretic point of view, we present a new compression algorithm: Arithmetic Coding with Hybrid Contexts on Trits. This method outperforms Interp consistently on all the datasets we tested but one and the gain with respect to the Interp method goes up to 13%this method also outperforms Packed+ANS2 on all datasets. In order to perform our benchmarking, we re-implemented many other compression techniques (around 30). Since we are only interested in the space compression, we managed to make for this metric a fair comparison with other methods. By doing this, we also saw that the Block-Interp method used in [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF][START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF] stores too much information and can be easily optimized. We use for our tests around 15 posting lists which we make publicly available in order to facilitate future comparisons with our work.

Overview of our methods and results

Trit encoding

The trit encoding of a number x is thus its binary representation, minus the leading "1", plus a closing "2", e.g., 19 10 → 10011 2 → 00112. The "2" at the end of each encoded integer serves as a delimiter between two successive integer encodings.

The trit encoding by itself doesn't have very good compression rates. On top of that, it doesn't take advantage of the clustering the databases we consider. We therefore add a contextual method on this trit encoding to get our efficient compression methods.

Arithmetic coding [36, pp. 61-62] for trits. Suppose you have a sequence of n trits with an estimate of the proportion of "0", "1" and "2" symbols denoted respectively P (0), P (1), P (2) with P (0) + P (1) + P (2) = 1. If the trit sequence has n i symbols i for i ∈ {0, 1, 2} with n 0 + n 1 + n 2 = n, then a perfect arithmetic encoder will encode your sequence using n 0 log 2 (P (0)) + n 1 log 2 (P (1)) + n 2 log 2 (P (2)) bits. This is optimal for random trit sequences with respective symbol frequencies of 0, 1, 2 equal to P (0), P (1), P (2). However, our trit encoding of the gaps of the posting list are not independent because of the clustering. We therefore add some context in our arithmetic coding.

Context arithmetic coding for trits. In context coding, we don't use absolute probabilities P (0), P (1), P (2) but use instead some probabilities that depend on the previously decoded tritsthe context. In order not to store too many probabilities, we only use as context the last γ encoded trits and use the probabilities P (i|C) as our probabilities in our arithmetic coding 5 .

For example, if γ = 8 and our encoding so far is 20102102022021, we will use the probabilities P (0|02022021), P (1|02022021), P (2|02022021) in our arithmetic encoder to encode the next trit. This method requires to store 2 • 3 γ probabilities P (i|C) 6 which implies that we cannot have a very large depth γ.

Hybrid contexts. The above presents contexts of size γ where we store each trit of the context. Instead we write γ = k + w for some non-negative integers k, w and consider the following context encoding:

On the last k trits of the context, store for each position whether you have a "2" symbol encoded by T or another symbol (i.e."0" or "1") encoded by N meaning not "2". There are hence 2 k possibilities. On the w previous trits, store only the total number of "2" symbols. This is an integer in {0, . . . , w}.

Our contexts C are therefore elements of {N, T } k × {0, . . . , w}. If we take our example, with γ = 8 and k = 3, w = 5, and our encoding so far is 20102102022 w 021 k , we will use the probabilities P (0|N T N, 3), P (1|N T N, 3), P (2|N T N, 3) in our arithmetic encoder. This means we have to store 2 • ((w + 1)2 k ) probabilities which can be significantly smaller than 2 • 3 γ . Our arithmetic encoding will be less efficient for the same γ but we will be able to take much larger values of γ which will make our encoder better overall.

Dynamic vs. static estimation of the probabilities P (i|C). Finally, an important aspect of our method is to determine how we compute our estimates for P (i|C). There are two main ways to compute these estimates:

1. Static: when compressing the posting list, we first read all the gap lists of the posting list to determine these probabilities exactly. In order to decompress, we need these probabilities so we have to store them in the index. 2. Dynamic: we start from P (i|C) = 1 3 for each i and C -it is highly probable that better initial estimates are possible -and start our encoder with these probabilities. Each time we encode a new trit i with context C, we update our probabilities7 and continue our context arithmetic encoding with these new probabilities. This method has the drawback of having less precise estimates for P (i|C), it has 2 advantages though:

The probabilities P (i|C) can be reconstructed from scratch at the decoding phase, by initializing the decoder again with P (i|C) = 1 3 for each i and C and updating the probabilities as you decode. This means we don't need to store these probabilities which reduces the storage of the compressed posting lists. We don't need to make a first pass on the posting list in order to compute these P (i|C) which improves the running time of the method.

We compared these 2 methods which are very close in terms of storage, the dynamic estimation is even usually slightly better.

To summarize, the method we use is a context arithmetic encoder, where we use a hybrid context and dynamic estimation of the probabilities. We perform also other optimizations: regarding the ordering of the documents, we use the bisection method, which we also use for concurrent methods for a fair comparison. We also analyze the use of batching in Section 5.3, i.e.splitting the words set into batches depending on their density in the posting list and apply a compression on each batch separately. We also analyze whether sorting the words depending on the density helps or not.

We made an extensive analysis of our methods and of other methods existing in the literature for a variety of methods. We focused on posting lists that come from mailboxes as it was one of our first motivations but also consider larger posting lists that come from the web.

We managed to break the Interp barrier up to 13%, even if we sometimes achieve only a few percent of gains. Keep in mind that we were only interested in the raw compression size while other methods could have other advantages in terms of multiple queries or running times.

The remainder of this paper is organized as follows: in Section 2 we introduce the existing techniques. In Section 3 we present our compression algorithm. In Section 4 we show the datasets and our results. In Section 5 we present variants of our compression algorithm. Section 6 summarizes the work and presents some future directions.

Existing compression methods

To compress the posting lists, the literature gives us a lot of different approaches. Section 2.1 shows what has been done in a first approach, to find a suitable encoding of the integer lists. Section 2.2 gives a rapid insight into another approach which enhances the clustering property of the posting lists, by reordering the document IDs. Section 2.3 gives a reference to a really different path that may be taken if one is willing to have more efficient ways to make complex queries: the suffix trees.

Last but not least, there are of course a lot of other approaches to compression, that do not target integer lists. The arithmetic coding, that we use in this work, is one of the multiple possible general-purpose algorithms to compress data. We note that the state-of-the-art for general-purpose compression is the cmix [START_REF] Knoll | cmix[END_REF] algorithm, a successor of the PAQ8 [START_REF] Knoll | A Machine Learning Perspective on Predictive Coding with PAQ8[END_REF] algorithm. The interested reader may find in this latter reference an introduction to arithmetic coding, that is used together with machine learning in those algorithms, to predict the input characters based on a static dictionary and on the previous characters read from the file to compress.

Compressing posting lists

We will suppose that, given a database of N documents, the document IDs are in {1, 2, . . . , N }. If N < 2 32 , this means that each posting list can be represented by a sequence of 32-bit unsigned integers. "Raw" databases often use this simple strategy, because it is easy to use [START_REF] Mallia | PISA: Performant Indexes and Search for Academia[END_REF][START_REF] Lemire | Integer Compression 2014 Dataset[END_REF]. However, as already discussed, in a given database, the gaps tend to be small. We can thus, instead, use more specialized techniques.

Universal codes. Some techniques encode each gap independently. In this category there are some codes that operate on a bit-by-bit basis, e.g., Unary, Gamma, Delta [START_REF] Elias | Universal Codeword Sets and Representations of the Integers[END_REF][START_REF] Bentley | An almost optimal algorithm for unbounded searching[END_REF], Zeta [START_REF] Boldi | Codes for the World Wide Web[END_REF], Golomb, Rice [START_REF] Golomb | Run-length Encodings (Correspondence)[END_REF][START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets (Correspondence)[END_REF] codes. Those codes are presented in detail in, e.g., [START_REF] Witten | Managing Gigabytes[END_REF]. However, codes that operate on a byte-by-byte basis are often preferred, because they allow faster decoding: Variable Byte [START_REF] Thiel | Program design for retrospective searches on large data bases[END_REF] and its variants, e.g., Varint GB [START_REF] Dean | Challenges in building large-scale information retrieval systems: invited talk[END_REF], Varint-G8IU [START_REF] Stepanov | SIMD-Based Decoding of Posting Lists[END_REF]. It is also possible to operate on different bases, e.g., Variable Nibble [24, Section 5], which outputs nibbles.

Block codes. Instead of treating the sequence gap by gap, a relatively recent idea is to treat them by block. In this category, the Simple family of codes encode a variable-size number of gaps in a fixed-size output (e.g., 32 bits for Simple9 [START_REF] Anh | Inverted Index Compression Using Word-Aligned Binary Codes[END_REF], 64 bits for Simple8b [START_REF] Anh | Index Compression Using 64-Bit Words[END_REF]). The Quantities, Multipliers, and eXtractor (QMX) [START_REF] Trotman | Compression, SIMD, and Postings Lists[END_REF] code almost falls in this category, as it outputs most of the time 128 bits, and sometimes 256.

Other types of codes treat a fixed-size number of gaps (e.g., 128 gaps) and output a variable-size number of bytes. The most notable encoding of this type is the Binary Packing, closely related to the Frame-of-Reference (FOR) [START_REF] Goldstein | Compressing relations and indexes[END_REF] encoding. It first outputs b, the number of bits required to store the largest of the 128 gaps in binary notation, then outputs the gaps as 128 b-bits numbers. Sometimes, one gap in a block has a big binary magnitude, whereas all the others have a small one. This is called an exception. Different authors have come with different solutions to mitigate the cost of such exceptions, and the resulting encodings are called Patched Frame-of-reference (Pfor) [START_REF] Zukowski | Super-Scalar RAM-CPU Cache Compression[END_REF]. Codes in this category can exhibit high throughput thanks to the use of vectorization, e.g., SIMD-BP128 [START_REF] Lemire | Decoding Billions of Integers Per Second Through Vectorization[END_REF][START_REF] Lemire | JavaFastPFOR: A simple integer compression library in Java[END_REF].

Another possibility to mitigate the cost of big gaps is to dynamically adapt the block size: Vector of Split Encoding (VSE) [START_REF] Silvestri | VSEncoding: Efficient Coding and Fast Decoding of Integer Lists via Dynamic Programming[END_REF], Adaptive Frame-of-reference (AFOR) [START_REF] Delbru | Searching Web Data: An Entity Retrieval and High-Performance Indexing Model[END_REF][START_REF] Delbru | SIREn: Efficient semi-structured Information Retrieval for Lucene/Solr/Elasticsearch[END_REF].

Last but not least, it is possible to combine one of these methods with another compression method, e.g., Packed+ANS2 [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF].

Working directly on the document sequence. Another possibility is to work on the sequence of document IDs, instead of working on the gap sequence. The Quasi-Succinct Indices [START_REF] Vigna | Quasi-Succinct Indices[END_REF] is a relatively recent re-engineering of the Elias-Fano [START_REF] Elias | On binary representations of monotone sequences[END_REF]11] encoding. This encoding depends on the maximal possible value encoded, so it is quite natural to apply the same block techniques that we have seen before: encoding document sequences by fixed-size chunks is more efficient (e.g., with chunks of 128 IDs), and dynamically adapting the chunk size offers yet another improvement in the compression ratio: it is the Partitioned Elias-Fano encoding [21].

Last, but not least, comes the Binary Interpolative Encoding (Interp) [START_REF] Moffat | Exploiting clustering in inverted file compression[END_REF]. This technique has set the standard for compression ratio since 1996, and has been recently outperformed, on some datasets, by the Packed+ANS2 method [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF]. We note that a variant of Interp exist, that yields better running time but not more compression [START_REF] Cheng | Unique-order interpolative coding for fast querying and spaceefficient indexing in information retrieval systems[END_REF].

Working on the bit vector. Another possibility is to work on the bit vector, sometimes also called bitmap, associated with the document sequence. There is a wide literature covering this subject, but few papers make the link between this possibility and the previous ones. Indeed, working on bitmaps is mostly done in the database community, whereas working on posting lists is mostly done in the information retrieval area.

We mention it here for completeness, but also because our method is the pendant on trit vectors to what has been applied on bit vectors in the past. Indeed, Bookstein et al. [START_REF] Bookstein | Modeling Word Occurrences for the Compression of Concordances[END_REF] worked on contextual methods on bit vectors, and we present, in this article, contextual methods on trit vectors. This method, as other methods that rely on models, can be enhanced with batching [START_REF] Moffat | Parameterised Compression for Sparse Bitmaps[END_REF], see Section 5.3.

A recent study [START_REF] Wang | An Experimental Study of Bitmap Compression vs. Inverted List Compression[END_REF] compared 21 compression methods for integer lists, and the interested reader will find in this study references to methods that work on bit vectors.

Remark: as a rule of thumb, most methods that work on bit vectors take more space than methods that work on document sequences, unless the sequences are very dense.

Reordering the document IDs

As argued before, if the gaps are small -or equivalently, if the document IDs in the posting lists are close to one another -the compression methods will usually benefit from it. Another path has hence been taken to reduce the size of an inverted index: to reorder the document IDs.

The interested reader may find more information about this strategy in [13, Table 1]. In the present paper, we used the state-of-the-art algorithm of [9], more precisely the implementation from [START_REF] Mackenzie | Compressing Inverted Indexes with Recursive Graph Bisection: A Reproducibility Study[END_REF].

A recent strategy called Clustered Elias-Fano (CPEF) [START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF][START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF] divides the full dataset into clusters, and computes a reference list for each cluster. Each document sequence S is then coded as two sequences: the intersection I between S and the reference list of its cluster, and of course S\I. For clustering, the authors used the same algorithms as the ones usually used in other reordering strategies. To encode the resulting sequences, they use Partitioned Elias-Fano [21]. What is novel is that the sequences to encode are now different. We slightly modified their algorithm to improve the compression ratio, see Appendix A.

Last but not least, some authors take advantage of the highly repetitive nature of some document collections, e.g., versioned documents: universal indexes for Highly Repetitive Document Collections (uiHRDC) [START_REF] Claude | Universal indexes for highly repetitive document collections[END_REF] and Pattern Identification Sequentially (PIS) [START_REF] Zhang | Leveraging Context-Free Grammar for Efficient Inverted Index Compression[END_REF]. It would be great to see if those algorithms can be used on our datasets to improve compression. Indeed, a previous e-mail is usually included when we write an answer or when we transfer it, so e-mail datasets are no doubt suitable for such algorithms. Unfortunately, we were only able to test the uiHRDC algorithm, and it gives less good results, because their algorithm was optimized for in-memory size and not for output-file size.

Suffix trees

Other data structures (e.g., suffix arrays) allow more efficient searches when performing advanced queries, at the cost of additional memory overhead. In this article, we focus on the memory requirement of the index, and will thus not go into the details of these data structures. The interested reader may find more information about this data structure in, e.g., [START_REF] Navarro | Compressed Full-text Indexes[END_REF].

Detailed presentation of our method and implementation details

The main pseudo-code of our method is detailed in Figure 3. In this section, we will detail the different parts.

Pre-processing

As explained in Section 2.2, there is a rich literature that explains that most compression methods can be used together with a method that reorders the document IDs. We thus first apply graph bisection on each dataset [9,[START_REF] Mackenzie | Compressing Inverted Indexes with Recursive Graph Bisection: A Reproducibility Study[END_REF]. There has to be somewhere, stored, a bijection between the actual documents and {1, . . . , nbDocuments}. We believe that this reordering do not change the size of this bijection (this bijection is not accounted for in our results).

For our method that uses adaptive arithmetic coding, there is another reordering that yields superior compression rates: a reordering on the word IDs. We store the words by increasing density.

Remark: this time, we believe that the cost of storing the bijection between the actual words and {1, . . . , nbWords} might be slightly more -because standard techniques that apply, e.g., when the words are sorted alphabetically, are no longer available. We note that if we use a stable sort, the original ordering can be retrieved without needing to store additional data -even though we did not implement it.

Choosing the contexts

When using a static arithmetic encoding, we make two passes over the data. In a first pass, we collect, for each context, the number of trits that have this context. In the second pass, we will encode those trits according to those occurrences (transformed into probabilities).

We distinguish two kinds of contexts. We would like to have γ = k +w trits of context available, but of course, this is impossible for the first trits to encode. We thus resort, for those trits, to smaller contexts. The first trit is encoded with an empty context, the second trit is encoded with a context of only one trit, the third trit is encoded with a context of only two trits, and so on, until we reach kInit trits of context. Then, the context of a trit is the last kInit trits. This way, we encode the first trits in each trit list until we have encoded k + w trits. Recall that we split γ in two parts k + w because having 3 γ different contexts was not efficient. This explains why we have yet another parameter kInit: fixing kInit to γ -1 is possible but is not efficient, thus we use another, smaller, value.

As we saw in Section 1.4, in the contexts, we "merge" 0s and 1s. This means that we view the contexts [120] and [020], for example, to be the same one, denoted as [NTN] ("T" for two and "N" for not-two). This allows to use bigger values for k and w at the cost of having less precise contexts, and overall this is more efficient.

First trits -merge 0s and 1s

The first k + w trits of each trit list l are encoded with an initial arithmetic contextual method -where the context of the i-th trit (we start counting at 1) is the min(i -1, kInit) previous trits, where the trits 0 and 1 are undistinguished. There is a number of occurrences to track for the initial contexts equal to:

kInit i=0 3 × 2 i = 3 × 1 -2 kInit+1 1 -2
Rest of the trit list -merge 0s and 1s

The rest of the trits are encoded with another contextual arithmetic method -where the context of a trit is the k previous trits (0 and 1 are undistinguished) and the number of 2 in the w trits before those k trits.

There is a number of occurrences to track for the general contexts equal to:

3 × (w + 1) × 2 k .

Storing the probabilities

For each context c, we now have the number of times, in the trit lists to encode, where we have a 0 with this context (= occ(c, 0)), where we have a 1 with this context (= occ(c, 1)), and where we have a 2 with this context (= occ(c, 2)).

We must now find a good encoding of all those numbers occ(c, t). We could keep things exact and store, for each context, the three values. We found that it was more effective to let the model be a little bit inexact, but only store two values. To do so, we normalize, for each context, those three values (e.g., we take integer values occ (c, 0), occ (c, 1) and occ (c, 2) such that t occ (c, t) = 255 and such that for each trit u, occ (c, u) ≈ occ(c, u) × 255 t occ(c, t)

). We can then encode those three values on only 16 bits by encoding occ (c, 0) and occ (c, 1) on 8 bits each (they are values no greater than 255), and deducing occ (c, 2) = 255occ (c, 0)occ (c, 1).

The more bits we use to encode those normalized occurrences, the closest this approximate model will be to the actual data, but the more space it takes to store it in the index for decoding.

Choosing the parameters

A crucial point in every method that needs parameters is the choice of those parameters.

Static Arithmetic Coding

Our parameters, for the static arithmetic encoding, are: k, w, kInit for the contexts the number of bits on which to normalize the occurrences We made experiments on our datasets that showed that (a) the best value for k was growing in accordance to nbPointers, (b) a value for w close to k was the best choice, (c) all kInit choices neither too small nor too big with respect to k were all good choices, and (d) normalizing the occurrences on 8 bits was a very good choice.

We thus choose our parameters to be:

k, w = k + 1, kInit = k/3 and number of bits = 8,
where k is chosen as big as possible without making the storage space of the model, in bits, going further than 2% of nbPointers.

As a small optimization, we remarked that, for any database with nbDocuments documents in total, if the last nbDocuments -1 trits of context are all different from 2, then the next trit will always be a 2 (because there is no gap bigger than nbDocuments). We thus made sure that this "free 2" was available to the eyes of our encoder, by making sure that k + w would be equal to this value, in the case where a bigger value for w would have been selected automatically.

Adaptive Arithmetic Coding

Unlike in the static case, the symbol occurrences we are handling are always estimates of the true ones, based on what has been read so far (the encoding is done in one pass, thus we have never access to the occurrences of the symbols in the full message). First, we provide initial estimates of the probabilities, and then, we periodically "forget" some of the occurrences that have been read so far, in order to adapt to the latest symbols read [START_REF] Gallager | Variations on a theme by Huffman[END_REF]. Last, we must also find good values of the parameters, exactly as in the static case. When using an adaptive arithmetic encoding, we do not need to store the model in the index, so the choice of those parameters is not according to a balance between the precision of the model and its size. Instead, it is a balance between the precision of the model and the cost associated with the time needed to initialize it.

Our parameters, for the adaptive arithmetic encoding, are: k, w, kInit for the contexts the initial estimates of the probabilities P (i|C), for each trit i and each context C the number of steps N before dividing by two the occurrences

After some experiments, we chose our parameters to be:

                   w = k =

Storing the posting lists lengths

We store explicitly, for each posting list, its total length -the number of gaps in it -before encoding it. Indeed, to be able to decode the output of our arithmetic encoder, it suffices to know in advance when to stop decoding. Here, the number of gaps in a posting list is equal to the number of "2" in its associated trit list. As soon as we have decoded that number of "2", we know we reached the end of the encoding. Storing those lengths is not mandatory, though, and we picture a variant in Section 5.

We tried different strategies to encode those lengths, and the best performing one is to encode those lengths with the Delta method.

Remark: in our datasets, the encoding of those lengths remains negligible in front of the encoding of the posting lists. It is possible, though, that on other datasets, another method would be better to encode those lengths.

Methodology and results

Methods studied and implemented

Our goal in this paper was to search for the best compression method on inverted indexes, without any further requirement. There are already a lot of implementations that can be directly used to compress inverted indexes, but their purpose is usually different: they also want to minimize the time elapsed during queries in the index. By doing so, they usually add an overhead. Needless to say, each team working on the subject has a different way of dealing with those overheads, and it is most of the time not possible to compare the compression ratios given in different papers. Furthermore, it is sometimes useful to combine different techniques, and it cannot be done without a common framework. We thus re-implemented methods from the state-of-the-art, in Java. The result is the repository https://gitlab.inria.fr/ybarsami/compress-lists, that combines the following compression methods: the methods presented in this paper the Interp method [START_REF] Moffat | Exploiting clustering in inverted file compression[END_REF], together with its variants. We rewrote the method with all the optimizations, as described in the paper -note that some optimizations are not applied in other papers that use it. the methods Binary Packing [START_REF] Goldstein | Compressing relations and indexes[END_REF], FastPFOR [START_REF] Lemire | Decoding Billions of Integers Per Second Through Vectorization[END_REF], NewPFD, OptPFD [START_REF] Yan | Inverted Index Compression and Query Processing with Optimized Document Ordering[END_REF], Simple9 [START_REF] Anh | Inverted Index Compression Using Word-Aligned Binary Codes[END_REF], Simple16 [START_REF] Zhang | Performance of Compressed Inverted List Caching in Search Engines[END_REF], directly taken from the JavaFastPFOR library [START_REF] Lemire | JavaFastPFOR: A simple integer compression library in Java[END_REF]. the methods QMX [START_REF] Trotman | Compression, SIMD, and Postings Lists[END_REF], Simple8b [START_REF] Anh | Index Compression Using 64-Bit Words[END_REF], whose implementation straightforwardly derive from the one of Simple9 from the JavaFastPFOR library in the previous point. the method AFOR3 [START_REF] Delbru | Searching Web Data: An Entity Retrieval and High-Performance Indexing Model[END_REF], directly taken from the SIRENe library [START_REF] Delbru | SIREn: Efficient semi-structured Information Retrieval for Lucene/Solr/Elasticsearch[END_REF]. the Quasi-Succinct indices [START_REF] Vigna | Quasi-Succinct Indices[END_REF], also known as the Elias-Fano method, and its refinements with partitioning (PEF [21]) and with clustering (CPEF [START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF]). The partition algorithm is a simple Java translation of the code from the original repository [START_REF] Ottaviano | Data Structures for Inverted Indexes[END_REF]. The clustering algorithm has been entirely rewritten from the original paper, in order to be able to use not only the Elias-Fano method, but other ones as well. We also modified the code to add two optimizations, see Appendix A. a variant of the Packed+ANS2 method [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF]. We re-implemented the algorithm described in the article, and, in our variant, we use arithmetic coding instead of ANS. This allows us to gain space in the index with respect to the original implementation (thus, providing more than fair comparisons), see Appendix A. the Four-State Markov models that work on bit vectors from [START_REF] Bookstein | Modeling Word Occurrences for the Compression of Concordances[END_REF]. They are contextual arithmetic methods, so we used the arithmetic coder from the Reference arithmetic coding library [START_REF] Nayuki | Reference arithmetic coding[END_REF], and re-implemented the ideas of the paper from their description. the Bernoulli, Golomb and Rice [START_REF] Golomb | Run-length Encodings (Correspondence)[END_REF][START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets (Correspondence)[END_REF] methods, which also use the arithmetic coding. and finally the Unary, Binary, Delta, Gamma [START_REF] Elias | Universal Codeword Sets and Representations of the Integers[END_REF][START_REF] Bentley | An almost optimal algorithm for unbounded searching[END_REF], Zeta [START_REF] Boldi | Codes for the World Wide Web[END_REF], Variable Byte [START_REF] Thiel | Program design for retrospective searches on large data bases[END_REF] and Variable Nibble [START_REF] Scholer | Compression of inverted indexes for fast query evaluation[END_REF] methods, which are straightforward to implement given their expressions. It is worth noting that for these methods, we explicitly use the fact that we never have to code the integer 0. The encoding is thus the same as described in "Managing Gigabytes" [START_REF] Witten | Managing Gigabytes[END_REF], even though in other libraries, the authors chose to be able to encode 0. That being said, there still remains a lot to be said about how to encode an inverted index with a given method.

Datasets

To validate our approach, we used different datasets. Some datasets are commonly used in the state-of-the-art, and we added e-mails datasets, because one of our concerns was the use of inverted index to search through e-mails. Indeed, one of the applications we have in mind, for this work, is an encrypted mail service. In such a service, the compressed lists would be stored in the cloud, and would have to be sent to the users that want to use it without using permanent storage on their device. In that case, unlike most works on inverted index compression, we need efficient compression even for small datasets. our personal mails: we computed the inverted indexes of 3 personal e-mail boxes, 2 of which are from the authors. the Enron corpus of e-mails [START_REF] Klimt | The Enron Corpus: A New Dataset for Email Classification Research[END_REF][START_REF]Enron Email Dataset[END_REF]: this corpus contains professional e-mail boxes of 150 persons. We cleaned the original folders by removing duplicate e-mails, as suggested [49, Section 2]. We present results on the e-mails of 4 users who have the biggest e-mail boxes in the corpus: the e-mails of Dasovich, Jones, Kaminski, and Shackleton. manuals / books: we took four commonly used databases for inverted indexes: the Authorized Version (King James') Bible [START_REF] Andrewes | Authorized Version (King James') Bible[END_REF], a bibliographic dataset "GNUbib", a collection of law documents "Comact" (the Commonwealth Acts of Austria), and a collection of documents from the Text Retrieval Conference (TREC disks 4 and 5 [START_REF]TREC disks 4 and 5[END_REF]). 1. The (Optimized) Interp method [START_REF] Moffat | Exploiting clustering in inverted file compression[END_REF]. 2. A variant of the Interp method that works by blocks of 128 integers (to allow better comparison against the next method, that also uses blocking). 3. A variant of the Packed+ANS2 method [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF], that we call Packed+Arithmetic, that uses arithmetic coding instead of ANS. 4. Our TC Method: TritContext method, with the generic parameters presented in Section 3.4. 5. Our TCA Method: TritContextAdaptative method, with the generic parameters presented in Section 3.4.

Tables 5,6, 7 and 8 present our results. Before applying the different methods, we first apply to the datasets the bisection (b) algorithm [9,[START_REF] Mackenzie | Compressing Inverted Indexes with Recursive Graph Bisection: A Reproducibility Study[END_REF] and sort (s) the resulting integer lists by increasing length, hence the (bs) in the dataset names. The gain corresponds to the gain in percentage of our best method (in bold) compared to the Interp method. All results are written in bits/pointer and include the size required to compute the number of occurrences for each word, encoded using the Delta [START_REF] Elias | Universal Codeword Sets and Representations of the Integers[END_REF][START_REF] Bentley | An almost optimal algorithm for unbounded searching[END_REF] method. All values are rounde at ±0.001 bits/pointer. The gain is rounded ±0.01%. 8: Results on web crawling datasets. On each dataset, we applied the bisection (b) algorithm [9,[START_REF] Mackenzie | Compressing Inverted Indexes with Recursive Graph Bisection: A Reproducibility Study[END_REF] or we let the documents Ids sorted with a lexicographical sorting on the corresponding URIs (u) [25, Section 5], and the resulting integer lists were sorted (s) by increasing length.

Mail1

5 Detailed analysis, interpretation and variants of our method

Choosing the parameters

In Section 3.4, we identified automatic parameters to be set with probabilities normalized on 8 bits, and such that the total size of the model would not exceed, in bits, 2% of nbPointers. We also set our parameters w, kInit such that w = k + 1 and kInit = k/3 . It is, in the general case, possible to find better parameters. However, of course, finding the best set of parameters would be very time consuming. For instance, on Gov2, we found that normalizing probabilities on 16 bits and having the total size of the model not exceeding 0.5% of nbPointers was slightly better.

More subtle contexts

At the beginning of our work is the empirical establishment that contexts are very useful for entropy coding. We then searched a balance between the precision of the contexts used and the size of the probabilities needed to store those contexts.

The most efficient compromise we found was to divide a context of size γ into the k last trits, and the w trits before. On the k last trits, what is looked at is whether each trit is a 2 or not, and on the w trits before, what is looked at is the number of 2 in total.

We also tested to have a larger number of sub-boxes inside the γ last trits, and it did not turn out to be useful. For instance, we would divide the γ last trits in the k last trits, where we would, as before, take the full context (just merging 0s and 1s), then look at the w 0 previous trits, only counting the number of 2 in it, then the w 1 trits before, also only counting the number of 2 in it, etc.

In a way, our experiments are a specialized version of the more general GRASP algorithm pictured in [START_REF] Mrak | A context modeling algorithm and its application in video compression[END_REF], which also tries to merge contexts in order to get information from a greater context without having to pay for the full price. It would be interesting to see if this more general idea could lead to better compression rates, and to analyze the kind of contexts that would be merged together.

Batching

We can refine our contextual methods with batching. We experimented and found that sometimes, a logarithmic batching (with respect to the gap list lengths) gives slightly better results (on half of the datasets), but the gains were marginal. We used 7 batches and use, for each batch, the best method between Interp, TC and TCA. Our batches have the following delimiters: {0, 0.0002, 0.001, 0.01, 0.03, 0.1, 0.2, 1} in terms of pointer density (gap list lengths divided by the nbDocuments).

Quatritlist

In all previous papers, and in previous sections, the index was always created with an explicit storage of the gap array lengths. For most methods, this knowledge is mandatory. But in our case, we can avoid storing the gap array lengths. When using arithmetic coding, in order to decode we need a way of knowing when to stop decoding. Instead of using the gap array lengths, we can thus encode a special "end" character, at the end of each gap array. If we note this special character "3", and we are now dealing with quatrits (integers in {0, 1, 2, 3}).

We tested all our methods with quatrits, and the results are equivalent to the results with the explicit storage of the gap array lengths. However, if one is dealing with a dataset for which this storage of lengths is higher, this method surely helps.

Context on the bit vector

In Section 2, we noted that previous works on inverted index compression also used contextual encodings, e.g., contextual arithmetic encoding on bit vectors [START_REF] Bookstein | Modeling Word Occurrences for the Compression of Concordances[END_REF]. We thus also tested contextual encodings on the bit vector. Our experiments showed that these methods are outperformed by our trits -even though contextual encodings on the bit vector are also outperforming both Interp and Packed+Arithmetic methods. It would be interesting to see if a more careful setting of parameters would lead to better results.

SplitB2B01 methods

Instead of directly working on trit lists, we also tried to split the trit list in different ways. In the SplitB2B01 methods, we first transform each trit list in two parts: the part that contains only the 2, and the part that contains only the 0 and 1.

SplitB2B01 methods

g = [4, 1, 1, 3, 5, 2] ⇒ l = 002221201202 ⇒ B2 = 001110100101 B01 = 001010
B2 is obtained from l by replacing each 0 and 1 by a 0, and each 2 by a 1. B01 is obtained from T by removing all the 2.

On each of those bit vectors B2 and B01, we tried to apply different methods. Our idea was that, in B2, there is more clustering than in the original bit vector associated to the posting list, and it could potentially be worth trying to go in that direction. Nevertheless, we did not achieve better compression rates when doing this.

SplitTLB01 methods

The SplitTLB01 methods do not work directly on the gap array g nor on the trit list T as the context methods. Instead, they first transform the gap array g in the following way. They first build gl, the gap lengths array -the array that contains the lengths of the gaps (number of bits needed to write each gap in base 2) and B01, the sub-list of T containing only the 0 and 1. Indeed, it is easy to reconstruct T from gl and B01. Let us see that on the same example g = [4, 1, 1, 3, 5, 2]. In this array, 4 10 = 100 2 needs 3 bits to be written in base 2. 1 10 = 1 2 needs 1 bit to be written in base 2, etc. We thus have the gap length array gl = [3, 1, 1, 2, 3, 2]. In this example, T = 002221201202 and the sub-list containing only the 0 and 1 is thus equal to B01 = 001010.

If we want to reconstruct g, it is easy: gl[0] = 3 means that g[0] takes 3 bits. In T , we removed the leading 1, hence in B01, the first 2 bits come from g[0]. T thus starts with 002. Then gl [START_REF] Anh | Index Compression Using 64-Bit Words[END_REF] = 1 means that g [START_REF] Anh | Index Compression Using 64-Bit Words[END_REF] takes 1 bit. In T , we removed the leading 1, hence in B01, the next 0 bits come from g [START_REF] Anh | Index Compression Using 64-Bit Words[END_REF]. T thus starts with 0022. etc.

As in the context methods, we do not work directly on gl but we work on its associated trit list. In our example, the binary representation of the numbers in gl is [11,[START_REF] Anh | Index Compression Using 64-Bit Words[END_REF][START_REF] Anh | Index Compression Using 64-Bit Words[END_REF][START_REF] Elias | On binary representations of monotone sequences[END_REF]11,[START_REF] Elias | On binary representations of monotone sequences[END_REF]. The associated trit list is thus T L = 1222021202 (we remove the leading 1 in each of the gap lengths as all the gap lengths gl i verify gl i ≥ 1).

SplitTLB01 methods

g = [4, 1, 1, 3, 5, 2] ⇒ gl = [3, 1, 1, 2, 3, 2] ⇒ T L = 1222021202 T = 002221201202 ⇒ B01 = 001010
On those two vectors T L and B01, we tried to apply different methods. Our idea was the same: in T L, there would be more clustering than in the original trit list T , and it could potentially be worth trying to go in that direction. Nevertheless, we did not achieve better compression rates when doing this neither.

Conclusion

In this article, we developed a novel idea to compress inverted indexes, that beats the Interp and Packed+ANS2 methods, two methods that are the state-of-the-art regarding compression ratios. We applied our method to a wide range of datasets, including e-mail datasets.

We understand that, in most applications, the most useful feature is not always compression. We hope that, in the future, the trits we used in this paper can be used together with other algorithms, to provide better time complexities, while maintaining the compression rate showed in this paper.

We mentioned contributions taking advantage of the highly repetitive nature of some document collections, e.g., versioned documents. We hope that, in the future, it will be possible to combine those ideas with ours.

Last but not least, we think that our methods can still be enhanced. Throughout this paper, we highlighted that the contextual probabilities of the trits are the key to the success of our methods. We tried, in different ways, to reach a balance between the precision of the probabilities (bigger contexts) and the cost of the model (in case it needs to be stored) or the time needed to read sufficiently enough trits to have a good estimate of the true probabilities (in case the model is built on-the-fly). What we did not do is to look at what those probabilities look like. We think that it could probably enhance our methods if we could look at the probabilities and extract a pattern from them, or use machine learning to enhance prediction, as is done in cmix [START_REF] Knoll | cmix[END_REF] and PAQ8 [START_REF] Knoll | A Machine Learning Perspective on Predictive Coding with PAQ8[END_REF]. This is left for future work. is needed, with and without enforcing fast-skipping of blocks. This comparison is done in this appendix.

We picture in Figure 4 the encoding as it is implemented in those repositories. It is obvious from this figure that the VariableByte encodings of 6601, 6043 and 2784 can be avoided, as they can be recomputed from the block maximums array. This optimization leads to a better space usage without using more time (neither to construct, nor to query) -it would even marginally use less time because a subtraction of two integers already in the memory is probably quicker than a decoding of the VariableByte method. In the actual implementation, there is a slight optimization for the values encoded with VariableByte. Because we know the block size (always 32 except for the last block whose size can be deduced because we know the full size of the gap array -here 81 mod 32 = 17), we can always subtract the block size to the value encoded. Indeed, the document IDs are strictly increasing, thus it is safe to subtract the block size to the maximum value, it will still be a positive number, and it is straightforward to reconstruct the value at decoding time, by adding back the block size that was subtracted. Figure 4: Example encoding of a document array of length 81 with blocks of size 32 with the Block-Interp method as implemented in [START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF].

PS: For the blocked-Elias-Fano method, there is a specialized code in those repositories. We did not check whether their implementations avoid this waste.

Another difference is that in the two articles, the methods are only tested on a subset of the full dataset, where the small posting lists are removed. In [START_REF] Pibiri | Space and Time-Efficient Data Structures for Massive Datasets[END_REF], the same methods are tested on the same datasets, but without removing from the datasets the small posting lists, and the Interp method is shown to beat the two other methods.

The Gov2 and ClueWeb09 datasets we have at our disposal are already versions of the datasets where the small posting lists were removed (in Gov2 (resp. ClueWeb09), the posting lists have lengths no less than 100 (resp. 250) postings). These datasets are thus really close to the datasets filtered in [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF]. To reproduce as closely as possible the work in [START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF], we also present results, in this appendix, on datasets where even more small posting lists are removed (in Gov2(*f) (resp. ClueWeb09(*f)), the posting lists have lengths no less than 14182 (resp. 16618), to match [START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF]Section 4.1,Table II]).

In our repository 8 , we first re-implemented the different versions of Interp. Then, we reimplemented the cluster method, with two changes from the original CPEF method: (a) we only considered the frequency-based construction for the reference list, to be able to also use the cluster method in concordance with other methods than the PEF method and (b) we found and implemented an optimization with respect to index size called "shrinking". Recall that each document sequence S is coded as two sequences: the intersection I between S and the reference list of its cluster, and of course S \ I. For our optimization, instead of coding directly the integers in S \ I, we first apply a mapping m from S \ I to N where m(x) = x -#i ∈ referencelist|i < x. Last, we implemented a method as close as possible to the Packed+ANS2 method, but using arithmetic coding instead of ANS coding. We called this method Packed+Arithmetic. The additional differences between the original method and our implementation are that (a) we did not optimize the RAM usage -there is still a huge array allocated for the probabilities (hence, we do not use "ANSmsb" from [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF]Section 3.3]) and (b) we keep all the 16 × 17/2 = 136 contexts instead of merging them in 64 different ones. The use of 64 contexts in the original paper is done in order to keep the number of bits used for the context as low as 6 (instead of 8), thus gaining 2 bits per block. Here, we code the selector for the context with an arithmetic coder and as a result, it takes less than 6 bits, even with the 136 contexts (between 4.5 and 4.9 bits per selector on mail datasets, 4.6 bits per selector on Gov2), and permits to distinguish more contexts, thus gaining space also on the compression of the gaps. We show the results of these different methods in Table 9. As can be seen in the table, the Interp method is almost always the best, even though the Packed+Arithmetic method is close -sometimes better. Blocking makes a noticeable difference (2.7% on Mail1, 1.6% on TREC, 1.2% on Gov2, more if we add padding), and we recall that in the current article, we provide comparisons against the original Interp method, which provides the best compression ratio.

B Implementation details

Our implementation is available at https://gitlab.inria.fr/ybarsami/compress-lists. We use the arithmetic encoder from the Reference arithmetic coding library [START_REF] Nayuki | Reference arithmetic coding[END_REF]. We slightly modified the original codebase in order to more efficiently use adaptive contexts.

All our methods work gap list by gap list. They first read a full gap list from an index, store it in main memory in an IntsRef (it is more or less the Java equivalent of a pointer on an array of ints), and then work on this IntsRef. This design choice was made in order to facilitate the use of the "SIRENe" [START_REF] Delbru | SIREn: Efficient semi-structured Information Retrieval for Lucene/Solr/Elasticsearch[END_REF] (implementation of the AFOR [START_REF] Delbru | Searching Web Data: An Entity Retrieval and High-Performance Indexing Model[END_REF] method) library that uses this data structure, and it also facilitates the use of the "JavaFastPFOR" [START_REF] Lemire | JavaFastPFOR: A simple integer compression library in Java[END_REF] library, that uses int[] to store the gap lists.

If one is interested in the running time of the methods implemented in our repository, it would be more efficient to avoid the use of this intermediate data structure, that incurs a 2x overhead in memory transfers (first, read from file and store in the array, then read from this array and do the computations).

The implementation of the bit lists, trit lists and quatrit lists all use the java.util.BitSet data structure internally, in order to be memory efficient. This is not required as those lists may be constructed on the fly instead of being stored in main memory -there is another 2x overhead in memory transfers behind this choice.

All the methods are implemented inside the gaparrayencoding folder.

Figure 1 :

 1 Figure 1: Posting lists represented as a binary matrix M such that M [i, j] = 1 ⇔ the word i appears in the document j.

Figure 2 :

 2 Figure2: From posting lists to document lists and gap lists. We took the posting lists from Figure1and derived the document lists and the gap lists.

A

  . Moffat & M. Petri[START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF] Section 5]

Figure 3 :

 3 Figure 3: Pseudo-code for our static arithmetic encoding method.

log nbPointers a + b + 0. 5 ,

 5 where a = 1.67264 and b = -2.24758, kInit = min(2 × k -1, 16), bits set to k meaning that we halve all the occurrences every N = 2 k steps. Remark: the values for a and b have been set thanks to a linear fitting.

Table 3 :

 3 Main properties of manuals / books datasets.

	Document collection	Bible	GNUbib	ComAct	TREC
	Number of documents	31 102	64 267	261 829	528 155
	Number of words	9 423	51 910	296 351	1 098 349
	Number of gaps	705 989 2 228 876 12 919 692 119 802 501
	Total size (MB)	4.44	14.1	135	1 643
	Document collection			Gov2	ClueWeb09
	Number of documents		25 205 179	50 220 423
	Number of words			1 107 205	1 000 000
	Number of gaps		5 979 715 441 15 641 166 521
	Total size (MB)			n/a	n/a

Table 4 :

 4 Main properties of web crawling datasets.

Table 5 :

 5 Results on our personal e-mails datasets. On each dataset, we applied the bisection (b) algorithm[9,[START_REF] Mackenzie | Compressing Inverted Indexes with Recursive Graph Bisection: A Reproducibility Study[END_REF] and the resulting integer lists were sorted (s) by increasing length.

	(bs) Mail2 (bs) Mail3 (bs)

Table 6 :

 6 Results on datasets from the Enron corpus. On each dataset, we applied the bisection (b) algorithm[9,[START_REF] Mackenzie | Compressing Inverted Indexes with Recursive Graph Bisection: A Reproducibility Study[END_REF] and the resulting integer lists were sorted (s) by increasing length.

	Bible(bs) GNUbib(bs) ComAct(bs) TREC(bs)

Table 7 :

 7 Results on manuals / books datasets. On each dataset, we applied the bisection (b) algorithm[9,[START_REF] Mackenzie | Compressing Inverted Indexes with Recursive Graph Bisection: A Reproducibility Study[END_REF] and the resulting integer lists were sorted (s) by increasing length.

	Gov2(bs) Gov2(us) ClueWeb09(bs) ClueWeb09(us)

  6500} are the first 31 document IDs. {53, . . . , 5855} are the document IDs number 33 to 63 from which 6601 was subtracted. {92, . . . , 2399} are the document IDs number 65 to 80 from which 12644 was subtracted.

	Block maximums	6601	12644	15428
	Pointers to blocks	X	X	X
	Block 1 Block 2 Block 3	VariableByte of 6601, then Interp of {84, . . . , 6500} with 6601 as upper bound VariableByte of 6043, then Interp of {53, . . . , 5855} with 6043 as upper bound VariableByte of 2784, then Interp of {92, . . . , 2399} with 2784 as upper bound
	{84, . . . ,

Posting lists can be generalized to the case where we store the number of times a word appears in a document. We do not consider this generalization in our work.

This assumes we know the values nbWords and nbDocuments.

This fact was already known by the programmers of the original base code, as they write in a comment: // XXX wasting one word! regarding this issue. The original programmers certainly didn't need some optimal bounds for the Block-Interp method and this inefficiency was probably overlooked by the subsequent papers using this method. We discuss this issue more in detail in Appendix A.

Comparisons on the full dataset are made in[START_REF] Pibiri | Space and Time-Efficient Data Structures for Massive Datasets[END_REF], where Interp is shown to remain undefeated.

That doesn't say how we encode our first γ trits since there is no or not enough context. We use an arithmetic encoder with less context (or no context at all for the firts trit) to handle these first trits.

For each C, we only store P (0|C) and P (1|C) since we know that P (2|C) = 1 -P (0|C) -P (1|C). How we encode these probabilities is also very important and will be discussed when we perform a full description of our method.

Again, there are several ways of doing this update and we will describe our choices when describing the details of our methods.

https://gitlab.inria.fr/ybarsami/compress-lists

Acknowledgments. We would like to thank A. Moffat for unearthing the GNUbib and ComAct datasets. We would like to thank K. Merckx for porting to our attention the ENRON dataset. We would like to thank the authors of the various softwares we used in this experiment. No comparison could have been done without their previous efforts. We directly included in our code, by alphabetical order, "JavaFastPFOR" [57], "jsoup" [55], "Mime4j" [54], "Reference arithmetic coding" [59], "SIRENe" [53], and "Snowball" [62]. We also used the following softwares, by alphabetical order, "CPEF" [61] (to split the dataset by clusters), and "PISA" [58] (to reorder the datasets using graph bisection). Following their path, we also provide the source code of our experiments, see https://gitlab.inria.fr/ybarsami/compress-lists. Special thanks to the Thalys train which made this collaboration easy.

web crawling: we took two commonly used databases, which are substantially bigger than the other datasets: Gov2 and ClueWeb09 [START_REF] Lemire | Integer Compression 2014 Dataset[END_REF].

We do not index directly all the words in the datasets, but we first normalize the text: casefolding ("C" is treated as "c"), accent removal ("é" is treated as "e"), splitting of unicode characters representing two letters ("oe" is treated as "oe"). The resulting text is then split into words (which are any sub-string contained into non alphanumerical characters), and those words are finally stemmed (no stop-words were removed -frequent words have posting lists which are the most compressed in indexes). We used the Porter2 algorithm, improved from the Porter algorithm [START_REF] Porter | An algorithm for suffix stripping[END_REF], as implemented in the Snowball library [START_REF] Porter | Snowball[END_REF]. To index e-mails in MIME format, we made the following choices: we first parse the e-mails with Apache Mime4j [START_REF]Apache JAMES Mime4j[END_REF] we index the headers (date, subject, from, to, cc, bcc) we do not index attached files when we encounter a text/html part, we first extract the text from the html code with jsoup [START_REF] Hedley | jsoup: Java HTML Parser[END_REF] (to avoid indexing words in tags) when we find a url in the text ("http://...", "https://..." or "mailto:..

."), we remove what is after question marks (parameters of mailto or of php webpages), and remove what is between two consecutive "/" if the number of characters exceeds 30 (to avoid indexing what is usually hashed text).

While this hand-crafted normalization process is not perfect, it follows the "Keep It Simple Stupid" idea.

Tables 1,2, 3 and 4 give the main properties of those different datasets.

Results

We compare here 5 different methods:

A Detailed comparison to the state-of-the-art

The Interp method was first described in 1996 [START_REF] Moffat | Exploiting clustering in inverted file compression[END_REF]. In 2009, the method was claimed to be improved by remarking that blocking could improve the overall compression ratio [32, Table 1]. This was not true. Already in the original article, the authors remarked that blocks of size 2 n -1 were beneficial [18, Section 6], and the "balanced recursion" refinement already made recursions have these sizes whenever it is possible.

In 2017, a new method, based on clusters, claimed to beat the Interp method on one of the two datasets tested [START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF]Table VIII]. In 2018, a new method, Packed+ANS2, also claimed to beat the Interp method on two datasets similar from the previous paper [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF]Table 5]. However, those two papers do not compare their results to the original Interp method, but to a modified version of the Interp method, where a posting list is not coded as a whole, but rather divided by blocks (of size 128), with additional overhead to enable fast queries inside those blocks. To enable fast queries, in addition to the encoding of each block of 128 integers is added, for each block, the maximum value of an integer in that block and the size, in bytes, of the encoded block. This way, one can "jump" over an encoded block without having to decode it if needed. As an example, we show the encoding of a document array of size 81, with blocks of size 32.

The first block covers the document IDs from 84 to 6601. The maximum of that block is 6601. The second block covers the document IDs from 6654 to 12644. The maximum of that block is 12644. Because the previous maximum was 6601 (and it is a known value when decoding), we remove 6601 to all document IDs before encoding that block. We hence encode document IDs between 53 and 6043. The second block covers the document IDs from 12736 to 15428. The maximum of that block is 15428. Because the previous maximum was 12644 (and it is a known value when decoding), we remove 12644 to all document IDs before encoding that block. We hence encode document IDs between 92 and 2784.

If we want to know whether 12345 is in that posting list, we do not need to decode the first block: all values in the first block are ≤ 6601, so 12345 may not be in that block. We thus use the pointer to the second block (because 6601 < 12345 ≤ 12644), and directly decode the second block to answer this question (and find out that the answer is "no").

However, when encoding a block of integers (here, the blocks are of size 2 k , but this also holds in the general case) with the Interp method, it is a good idea to first encode the largest value of the block. Indeed, the Interp method requires to know an upper bound on the largest value. One could always use the number of documents as an upper bound, but this would result in a very inefficient way of encoding small blocks of the full posting list. Writing the maximum value in the block, followed by an encoding of the remaining 2 k -1 values is better (we use a better upper bound, and we are now left with a block of size 2 k -1, optimal for the recursion of the Interp method). Thus, this information is written twice in the index. And indeed, if we go through the code, we find, at line 281 in block_codecs.hpp from the repository of the Packed+ANS2 method [START_REF] Moffat | Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts[END_REF], the following comment:

// XXX wasting one word!

The same code appears in block_codecs.hpp from the repository of the CPEF method [START_REF] Pibiri | Clustered Elias-Fano Indexes[END_REF] -although, without this comment. Wasting a word per block of 128 integers makes a noticeable difference on the resulting index size, hence, we think that the comparisons made in those two articles are misleading, and a comparison to an optimized implementation of the block-Interp