## 3 Positional Inverted Self-Index
: _The upper bound for space of PISI inverted list defined by Definition 1 is \(\mathcal{O}((N-n)\lceil\log_{2^{b}}N\rceil+(\lfloor\frac{N-n}{\alpha}\rfloor+n )\times(\lceil\log_{2^{b}}n\rceil+1))\) where \(N\) is a number of stems, \(n\) is a number of unique stems, \(\alpha\) is a step/period of the back pointers in the inverted list and \(b\) is a size of the word of computer memory given in bits._  
Proof. : Suppose \(b=8\), which implies that the following space complexities are given in bytes. Consider the PISI inverted list depicted as \(I\) array in Figures 1 and 2. The inverted list \(I\) is composed of \(N\) entries. \((N-n)\) of the entries contain the pointers to the next occurrence of the stem of size \(\lceil\log_{2^{b}}N\rceil\). This gives the upper bound of space \(\mathcal{O}((N-n)\lceil\log_{2^{b}}N\rceil)\). Suppose \(N=\sum_{i=1}^{n}N_{i}\) where \(N_{i}\) represents the number of occurrences of the stem \(i\). Furthermore, suppose \(N_{i}=\alpha\times k_{i}+1\) for all \(i\in\{1,..,n\}\), i.e., the number of occurrences of each stem reduced by one is divisible by \(\alpha\). It follows that \(N-n=\sum_{i=1}^{n}N_{i}-n=\sum_{i=1}^{n}(\alpha\times k_{i}+1)-n=\alpha\times \sum_{i=1}^{n}k_{i}\). Then \(N-n\) is clearly divisible by \(\alpha\) and this composition of stem occurrences represents the maximum possible number of back pointers \(\sum_{i=1}^{n}k_{i}\) for the given parameters \(N\) and \(n\). The sequence of the occurrences of a certain stem is always terminated by the last back pointer for each stem which means another \(n\) back pointers. Each back pointer is encoded using \(\lceil\log_{2^{b}}n\rceil\) bytes and it is marked by a reserved one-byte codeword (\((1)\) for the last back pointer and \(\langle 0\rangle\) otherwise). This gives the space \(\mathcal{O}((\lfloor\frac{N-n}{\alpha}\rfloor+n)\times(\lceil\log_{2^{b}}n \rceil+1))\) consumed by the back pointers. We conclude the upper bound for space needed for PISI inverted list is \(\mathcal{O}((N-n)\lceil\log_{2^{b}}N\rceil+(\lfloor\frac{N-n}{\alpha}\rfloor+n )\times(\lceil\log_{2^{b}}n\rceil+1))\). **Theorem 2**. : _The space needed for PISI presentation layer defined by Definition 2 is bounded by \(\mathcal{O}(-\sum_{i=1}^{N}\lceil\log_{2}p_{i}^{n(i)}\rceil-\sum_{j=1}^{N^{ \prime}}\lceil\log_{2}p_{j}^{\prime}\rceil+N)\) with respect to \(p_{i}^{n(i)}\) as the probability of a stem variant at position \(i\), \(p_{j}^{\prime}\) as the probability of a separator or a stop word at position \(j\) and \(N^{\prime}\) as the number of separators and stop words._  
Proof. : The PISI presentation layer is composed of the entries corresponding to the entries of the PISI inverted list. The number of entries is \(N\). Every entry is terminated by a special \(\langle\text{STOP}\rangle\) word followed by encoded stem variant. The presentation layer stores basically text preceding the indexed terms (stems) and the stem variants. Suppose the text surrounding the indexed terms is parsed using the space-less word-based model. Furthermore, suppose an entropy coder working with statistical model \(p^{\prime}\) composed of these words (separators and stop words) and the special \(\langle\text{STOP}\rangle\) word. The \(\langle\text{STOP}\rangle\) is usually the most frequent word of the model and it is encoded by a constant number of bits (usually one bit). This implies \(\mathcal{O}(N)\) bit needed to encode all the \(\langle\text{STOP}\rangle\) words. The number of unique stems is \(n\) and every stem stores its statistical model \(p^{stem}\) of all its variants for \(stem\in\{1,..,n\}\). Then \(p_{i}^{n(i)}\) represents the probability of the stem variant at position \(i\) in terms of the statistical model of stem \(n(i)\). Entropy coder encodes this variant using \(-\lceil\log_{2}p_{i}^{n(i)}\rceil\) bits, which implies the maximum number of \(-\sum_{i=1}^{N}\lceil\log_{2}p_{i}^{n(i)}\rceil\) bits necessary to encode all stem variants.