## 2 Materials and Methods
### Stip
#### 2.2.4 Compress Sequence Tag Index  
In order to optimize the storage efficiency of large-scale protein databases, STIP designed a compression algorithm specifically for tag indexing, using a three-layer compression mechanism to reduce the storage cost of the tag index. The compression methods employed in this paper are lossless compression techniques, including delta encoding, index dimensionality reduction, and dynamic bit-width encoding. The first step of compression is delta encoding, which stores the difference between adjacent numbers in the index rather than storing the numbers themselves. This is highly effective for storing sequences of incrementing numbers. Since the tag index generation process traverses the protein information in sequence, for each inverted list of the tag index, the protein IDs exhibit a monotonically increasing property. Therefore, the differential encoding strategy is applied to compress the protein IDs. For example, if the protein IDs in the tag index are [2; 5; 8; 10], after applying delta encoding, only the differences [2; 3; 3; 2] need to be stored, and these differences can be represented using fewer bits. The specific implementation process is shown in formula (5). In each inverted list, the first protein ID is used as the base value and remains unchanged, while the differences between each pair of adjacent protein IDs are calculated and stored in the tag index instead of the actual protein IDs. The formulas are as follows:  
\[\Delta ID_{k}=ID_{k}-ID_{k-1},k\geq 1 \tag{6}\]  
\[\text{Enc}(ID_{1},ID_{2},\ldots,ID_{n})=\langle ID_{1},\Delta ID_{2},\ldots, \Delta ID_{n}\rangle \tag{7}\]  
where \(ID_{i}\) represents the unique identifier of the protein. The differential encoding strategy not only compresses the data scale within linear time complexity but also transforms the protein IDs into low-value data. Based on statistics from the human proteomics dataset downloaded from the UniProt official website, which includes human protein sequences, this conversion can improve the compression effect of subsequent dynamic bit-width encoding, compressing the original 32-bit integer protein ID into an average of 6.2 bits per value. The second step is to generate a two-level hierarchical index which consists of a tag index array. The tag index obtained in the previous step is reduced to one dimension. The starting positions of different types of tag in the one-dimensional index form the auxiliary index. This step involves the linear reconstruction of the high-dimensional tag index. During retrieval, the auxiliary index allows the tag positioning information in the tag index array to be accessed in \(O(1)\) time complexity. The third step is to use dynamic bit-width encoding to compress the tag index array and the auxiliary index. First, the protein IDs and starting positions in the tag index are stored separately, generating two tag index arrays: one for the protein IDs and one for the starting positions. STIP utilizes the local similarity of the data within the tag index array to divide the array into fixed-size blocks, and each block by default stores 256 data entries. Each block is compressed independently, using dynamic bit-width encoding to store different values. Specifically, STIP calculates the minimum number of bits (denoted as b) required for 80% of the values in each block. Regular data is encoded using b bits, while values exceeding \(2^{\text{b}}-1\) are treated as outliers. A patch mechanism is used to store these outliers in a separate index, recording the position of each outlier. Extra space is used to store the values of the outliers, preventing the bit-width for regular data from being inflated due to the presence of outliers. After compression, the tag index consists of three parts: the protein ID array, the starting position array, and the auxiliary index. The compressed tag index is then stored on the disk, making it easy to retrieve directly during search.