## 3 Positional Inverted Self-Index  
We address a scenario that is typical for web search engines or for other IR systems [PERSON] et al. (2016). The necessary data structures of the system are distributed among internal RAM memory of many interconnected servers. The used data structures must provide extremely fast search performance across the whole data collection and still allow decompression of individual documents of the collection. Our proposed data structure Positional Inverted Self-Index (PISI) is depicted in Figure 1. The basic idea behind PISI is to interleave the inverted lists of single terms. The inverted lists are stored as the offsets between word positions (using gap encoding). Suppose we store the offsets in the form of an arbitrary byte code. Single inverted lists can be transformed into a sequence of pointers where one occurrence points to the next one (using the offset in terms of a vector of all word positions in the processed file). Once the inverted lists are interleaved, we obtain a data structure that provides: (i) a very fast access to the sequences of single terms; (ii) a vector of all terms occurring in the processed file that can replace the file itself; (iii) the notion of a left-hand neighbour and the right-hand neighbour for each of the terms in the processed file. The interleaved inverted list now represents the vector of term positions where a pointer at every position points to the next occurrence of the same term instead of the term position in the vocabulary. However, during the decompression process it is necessary to determine a certain word in the vector in a reasonable time. PISI inverted list (see array \(I\)) is equipped with so-called back pointers that point to  
Figure 1: Positional Inverted Self-Index (PISI) data structure: The original text is divided into single entries each of them containing exactly one stem (disregarding stop words and separators). The underscored values in the Inverted list represent the back pointers to the Vocabulary. The underscored bits in the Presentation layer represent Huffman codewords of stem variants. The coloured dotted lines refer to Example 1.  
the vocabulary position of the term. The period of the back pointers \(\alpha\) represents clearly the trade-off between the size of the inverted list and the decompression speed and it means that exactly every \(\alpha\)-th occurrence is followed by a back pointer. Finally, the last occurrence of the given term is followed by a back pointer as well. PISI naturally undergoes all the following procedures during the construction phase. The indexed text is case folded (all letters are reduced to lower case), stopped (so-called stop words are omitted) and stemmed (all words are reduced to their stems using Porter stemming algorithm [21]). PISI uses its presentation layer (proposed by [PERSON] et al. [17]) to store the information lost during the aforementioned procedures. The presentation layer (see the array \(F\)) contains one (possibly empty) entry for every word of the inverted list. The entry is composed of the Huffman codes of all non-alphanumeric words and all stop words preceding the corresponding word. The entry is terminated by the Huffman code of a variant of the word (the underscored bits in the array \(F\)). The presentation layer needs to be synchronized with the inverted list (array \(I\)). PISI stores a pointer to the presentation layer for every \(\beta\)-th word position in the inverted list. The pointers are stored as the offset from the previous pointer in the array \(FP\). For \(\beta=3\), PISI stores the pointer for: 3 rd, 6 th and 9 th position in the inverted list. These positions are: 6, 23 and 38. Thus, the stored offsets are: 6, 17 and 15. Furthermore, the vocabulary stores the textual representation of the stems, their word variants and the corresponding Huffman trees used for encoding of these variants. For the stems with just one variant, no Huffman tree needs to be stored and the variant is not encoded in the presentation layer either.