CN108932738B - Bit slice index compression method based on dictionary - Google Patents

Abstract

A dictionary-based bit-slice index compression method and optimization strategy, applicable to the 0/1-bit slice index structure represented by BitFunnel. The method of the present invention includes: 1. Document rearrangement: the document is rearranged according to the density of bit 1 in the index column with the block size as an interval, so as to increase the repetition degree between blocks. 2. Partial compression: Select some query low-frequency access rows for compression. 3. Dictionary compression: Divide the index into blocks, and store a full 1-bit block and high frequency blocks in the index into the dictionary. Replace blocks that appear in the dictionary with block numbers with fewer bits; replace blocks that don't appear in the dictionary with the number of the closest block in the dictionary (which will cause misnomer results for query requests but guarantees that they will not be lost) . The invention is applicable to the scene of bit-slice index compression in the field of information retrieval. The present invention can significantly improve the index compression effect without causing a large decompression delay, which is of great significance to the optimization of the search engine system.

Description

A Dictionary-Based Bit Slice Index Compression Method

【Technical field】

The invention belongs to the technical field of compression of bit slice indexes represented by BitFunnel in search engines, and particularly relates to a dictionary-based compression method for bit slice indexes and optimization strategies for partial compression, document rearrangement and the like. The invention is also applicable to other bitmap-like index structure compression in the field of information retrieval.

【Background technique】

In today's era of rapid technological development, the Internet has become an indispensable part of people's lives. The search engine has also become the most important Internet entrance. It uses tools such as web crawlers to regularly scrape the web page content of the Internet, and after reorganization and storage, provides retrieval services for users. The modern commercial search engine system mainly includes three parts: network server, index server and document server. The web server is used to receive the user's query and submit the query to the index server. After receiving the query, the index server performs operations such as accessing, caching, and intersecting the indexes involved in the query word to obtain the document number containing the query word, and then sorts it according to the query relevancy and sorts the K highest scoring documents ( topK) number returned to the web server. Next, the web server sends the document number and query to the document server to generate a summary containing the query words and return it to the user.

In the existing search engine system, index compression, decompression and intersection is one of the most important parts, which directly affects query efficiency and user experience. Compressing indexes can not only save storage space, but also reduce the overhead of storage devices. During the query process, since files of the same size contain more compression information, index compression can also increase the throughput rate from disk to memory and increase the cache hit rate, thereby increasing the cache hit rate. Improve query efficiency. The index compression scheme has two main evaluation indicators, one is the compression rate, which directly reflects the compression effect; the other is the decompression time, which is related to the query efficiency. The search engine will choose an appropriate compression scheme to balance the compression ratio and decompression time according to actual needs.

In 2017, Microsoft proposed a new index bit slice structure - BitFunnel. Its index is a bitmap-like bitmap index structure based on Bloom Filter. Each column represents a document, and each row represents the mapping of one or more words on the document. The word appears in the document and is set to 1, otherwise it is set to 0. Because of its application of Bloom Filter, query processing may get solutions other than true solutions—false positives. Since it uses bitwise operations to replace the traditional inverted index comparison and judgment, it reduces the possibility of branch prediction failure, so it has high query efficiency and has huge application space in the future. The specific index structure is shown in Figure 2. However, the bitmap-like structure incurs a much larger storage overhead than an inverted index.

For the above application scenarios, there are currently two solutions - arithmetic coding and bitmap compression. The existing arithmetic coding compression scheme for inverted index is more focused on integer compression, hoping that the compressed sequence is monotonous or the value is small, so it is not suitable for the BitFunnel index structure. The traditional compression method for bitmaps mainly uses run-length encoding, which requires large-scale continuous 0 or continuous 1 in the data, and the BitFunnel structure is difficult to guarantee to meet this condition.

[Content of the invention]

In order to solve the above problem, different from the traditional compression method using run-length, the present invention proposes a dictionary-based bit slice index compression method, which can achieve better compression effect without more continuous 0/1 sequences, Better for BitFunnel indexing. Specifically, the blocks with a higher degree of repetition in the BitFunnel index are replaced by numbers with fewer bits to achieve the purpose of compression, and the dictionary saves the mapping of the repeated blocks to the numbers.

The dictionary-based bit slice index compression method (and the optimization strategy for compression) provided by the present invention, with reference to FIG. 1 , the main methods include:

Step 1 (S1), rearrange the document according to the column density of bit 1 in the index with the block size as an interval;

Step 2 (S2), select a part of the query access low-frequency rows to compress according to the custom threshold value of the query data set characteristics;

In step 3 (S3), dictionary compression is performed on the compressed row selected by S2.

S1, a strategy for rearranging documents according to the density of bits 1 in the index column at block size intervals. specifically:

Suppose the number of index columns is d and the block size is k bits;

Step 1.1, count the density of 1 in each column of the index, and arrange the columns in descending order of density;

列放入索引第1,k+1,2k+1,…,

列；将1密度次高的

列放入索引第2,k+2,2k+2,…,

列，以此类推，最后将比特1密度最低的

列放入k,k+k,2k+k,…,

列。Step 1.2, initialize an empty index, set the highest density of bits 1

Columns are put into index 1,k+1,2k+1,…,

column; put 1 with the next highest density

Columns are put into index 2,k+2,2k+2,…,

column, and so on, and finally the lowest density of bit 1

Columns put k,k+k,2k+k,…,

List.

S2, a partial compression strategy that selects a part of query access low-frequency rows for compression according to a custom threshold value of the characteristics of the query data set. specifically:

Step 2.1, define the threshold α∈[0,1] of the access frequency of high-frequency access rows in the query process.

其中N是所有行的总访问频率之和，f(i)表示第i行的访问频率；根据部分查询数据集和自定义阈值对行进行如下分类：高频访问行，低频访问行；Step 2.2, sort the rows in the matrix according to the query access frequency from high to low, and select the least q row with the highest frequency access to the high frequency access row to ensure that

where N is the sum of the total access frequencies of all rows, and f(i) represents the access frequency of the i-th row; according to some query data sets and custom thresholds, the rows are classified as follows: high-frequency access rows, low-frequency access rows;

Step 2.3, establish a line compression flag bit file, and determine whether each line is a low-frequency access line, that is, a line that needs to be compressed.

S3, perform dictionary compression on the compressed rows selected by S2, specifically:

Step 3.1: Divide the rearranged BitFunnel bit slice index into blocks in units of rows, establish a dictionary to save a block of all 1 block of compressed rows that appear frequently in S2, and record the mapping relationship between high-frequency blocks and block numbers;

Step 3.2, traverse the index, replace the block that appears in the dictionary with the block number with fewer bits; for the block that does not appear in the dictionary, replace it with the number of the closest block in the dictionary, although this will cause the query request to be misnamed. But make sure not to lose it.

For convenience of description, we assume that the block size is k bits, the block number size is b bits and b<k.

After performing steps S1 and S2, for the selected rows that need to be compressed, each row is divided into aligned blocks that are longer than a specific length of k, and the repeated blocks are mined in units of this. Starting from the first row, k-bit blocks are scanned one by one, looking for duplicate blocks and recording their frequency, until the last row is processed. The discovered duplicate blocks are sorted in descending order of frequency. Store the most frequently occurring 2 ^b -1 blocks and an all-1 block into the dictionary. Traverse the matrix again.

A. If a certain block exists in the dictionary, replace it with a b-bit block number.

B. If the block x does not exist in the dictionary, look for the nearest block y that contains it (x AND y=x) and has the least number of 1s in the dictionary (since the dictionary holds all 1 blocks, it is always possible to find such y), replace x with the number of y.

Dictionary-based compression methods take advantage of the sparseness of matrices and the non-uniformity of 1's. Since the density of the overall 1 is low, the blocks of high density 1 appear less frequently, resulting in an increase in the proportion of repeated blocks and a small gap between approximate blocks. These features are beneficial to the dictionary-based compression of the present invention without greatly increasing the misnomer rate.

Advantages and beneficial effects of the present invention:

The block repetition of BitFunnel index is increased by document rearrangement, and the misnomer rate caused by compression is controlled to about 10% by partial compression. Finally, dictionary-based compression is used to compress the bit slice index to improve the compression effect of BitFunnel index. The invention can be widely used in the fields of search engine performance optimization and index compression.

【Description of drawings】

1 is a flowchart of a dictionary-based bit slice index compression method of the present invention;

Figure 2 is a schematic diagram of the BitFunnel index structure;

FIG. 3 is an example diagram of the process and result of rearranging documents according to the density of bit 1 in the index column at intervals of block size;

Fig. 4 is a dictionary compression process and an example diagram of the result;

【Detailed ways】

In order to facilitate the understanding of the above objects, features and advantages of the present invention, the present invention will be further described in detail below with reference to the accompanying drawings and specific embodiments.

Example 1 Document rearrangement

Since BitFunnel's mapping matrix is determined by the hash function (Bloom filter) and the document content, we can change the density of 1's in the matrix by adjusting the word-to-row mapping and the number of matrix rows. Although the 0/1 matrix has a high degree of repetition, the distribution of 1 in the matrix is very uneven due to the agglomeration of document distribution (BitFunnel only guarantees the density of global 1), so we propose a density-based document rearrangement scheme to increase the similarity between blocks in the matrix, thereby improving the compression effect. Obviously, the higher the block repetition, the better for dictionary compression. It is manifested in two aspects: the possibility of each block appearing in the dictionary becomes larger; the ratio of setting 1 for block compression that is not in the dictionary becomes smaller, thus greatly reducing the misnomer rate caused by dictionary compression.

For the convenience of description, we assume that the mapping matrix has a total of d columns, and each block contains k bits. Figure 3 takes d=16, k=4 as an example to describe the process of document rearrangement. First, the density of 1 in each column is counted and arranged in descending order. For convenience of presentation, here each d/k bits are grouped as a group. Mark with different backgrounds. Rearrange the highest density columns O, J, M, and G first to columns 1, 5, 9, 13 (shaded with diagonal lines), and so on, and finally rearrange the lowest density K, L, P, and F documents Columns 4, 8, 12, 16 (unshaded). After rearranging by column density in this way, we find that the density of each k column decreases from the first column to the kth column, and the repetition degree between blocks increases, which is more conducive to dictionary compression.

Example 2 Partial Compression

By analyzing the actual data set, we found that during the query process, only a few rows are accessed frequently, and most rows are accessed less frequently. Compression of high-frequency access lines will lead to a higher missymmetry rate, while compression of low-frequency access lines has little effect on the missymmetry rate. Based on this finding, we consider a partial compression scheme, that is, compress the low-frequency access lines, and leave no compression for the high-frequency access lines that have a greater impact on the misnomer rate.

其中N是所有行的总访问频率之和，f(i)表示第i行的访问频率；根据部分查询数据集和自定义阈值对行进行如下分类：高频访问行，低频访问行。仅对低频访问行进行压缩。Sort the rows in the matrix by frequency from high to low, and select the row with the smallest q accessed with the highest frequency to access the row with high frequency to ensure that

where N is the sum of the total access frequencies of all rows, and f(i) represents the access frequency of the i-th row; the rows are classified as follows according to the partial query dataset and custom threshold: high-frequency access rows, low-frequency access rows. Only low-frequency access lines are compressed.

为高频访问行。对剩下的31行(行号31至1)进行压缩。由于实际数据集的特征，在真实数据的查询过程中，只有少部分行被高频访问，大部分行访问频率较低，所以部分压缩可以在保证误称率的条件下得到较好的压缩效果。For the convenience of description, we assume that the matrix has 100 rows in total, and the access frequency and row number of each row are equal, that is, f(i)=i. First, we sort the rows in the matrix from high to low frequency, and the access frequency of each row decreases in turn, specifically 100, 99, 98, ..., 1. where N=(100+99+98+...+1)=5050. If we customize the threshold to α=0.9, then we select the most frequently accessed minimum 69 rows (row numbers 100 to 32) guaranteed

row for high frequency access. The remaining 31 lines (line numbers 31 to 1) are compressed. Due to the characteristics of the actual data set, in the query process of real data, only a few rows are accessed frequently, and most rows are accessed less frequently, so partial compression can achieve better compression effect under the condition of ensuring the misproportion rate. .

For row selection, we randomly divide the entire query data set into two equal parts, and one is used as the training set. The row access frequency f(i) obtained from the training set and the threshold α determine whether each row is compressed. The other half of the query set is used as a test set to test the performance of query time, misnomer rate and so on. It can be seen that we do not simply select fixed parameters for compression, but take advantage of the similarity of query requests from the same source to learn suitable parameters from the query history, in order to obtain the compression results in future query requests. for better performance. The value of the specific custom threshold α is related to the original misnomer rate of the index and the block repetition.

Example 3 Dictionary compression

For convenience of description, we assume that the block size is k bits, the block number size is b bits and b<k.

FIG. 4 takes k=4 and b=2 as an example to describe the process of dictionary compression and the result after compression. First record the frequency of occurrence of each block in the original dictionary, select the most frequent 2 ² -1 = 3 blocks and an all-one block to generate a dictionary (lower left in Figure 4); the first block in the fourth row of Figure 4 is 1100, because It appears in the dictionary, so it is replaced with the number 10; the second block 0010 in the first row (in the dashed box), since it does not appear in the dictionary, and the third bit position is set to 1. The third bits of blocks 1111, 1110, and 1010 in the dictionary are all 1, and all contain blocks 0010 that meet similar conditions. We choose 1010 with the least number of 1. This strategy ensures that the query request will not be lost, and the possible increase of misnomers is as small as possible. The shaded part in Figure 4 represents the case where the block is not in the dictionary and is replaced by an approximate block. The compressed data is divided into two parts: dictionary and compressed index.

Assuming that the matrix has m rows and d columns, the compression ratio of the above dictionary compression method is:

The size of the dictionary here is k*2 ^b , and the size of the mapping matrix after compression is mdb/k. In practice, the dictionary is small and can be ignored, so the compression rate is approximately equal to

In the intersection process, we simply use the b-bit block number as an index to extract the original block definition from the dictionary and perform an AND operation. Since the dictionary size is generally small and frequently accessed during the intersection (decompression) process, most of the dictionary data will reside in the CPU cache, reducing memory access overhead and improving intersection performance.

Example 4 Experimental Results

We test the effect of the dictionary-based bit-slice index compression method of the present invention on the TREC GOV2 dataset. Among them, Pri and Opt are indexes generated by BitFunnel's two strategies, PrivateSharedRank0 and Optimal. The block size in the experiment is set to 32 bits, and the block number size is set to 16 bits.

A description of the inverted index dataset used is as follows:

(1) We use TREC GOV2 as the data set crawled from the .gov domain name in 2004, which contains more than 25 million web pages as the indexed document collection, in which all document content has been stripped of HTML tags, and the title and body parts have been extracted. After indexing;

(2) We use MillionSet as query set 1, including 2007, 2008, and 2009 TRECMillion Query Track, a total of 60,000 queries;

(3) We use TerabyteSet as query set 2, which contains a total of 100,000 queries of 2006 TREC Terabyte Track.

Table 1

Table 1 describes the compression ratio of the dictionary-based bit-slice index compression method. According to Table 1, we can see that the overall compression ratios corresponding to the two query sets of MillionSet and TerabyteSet in the Pri mode are 0.73 and 0.72, respectively; the overall compression ratios corresponding to the two query sets of MillionSet and TerabyteSet in the Opt mode are 0.71 and 0.70, respectively. MillionSet is slightly better than TerabyteSet, but the difference is only 0.02-0.01, indicating that the query set has little effect on the compression rate, and our partial compression method is universal to different query data sets.

We also try to treat every 32 bits as an unsigned integer (unsigned int type), and compress using arithmetic coding and bitmap compression methods. We found that using Pfor, VByte, and EWAH for compression only reduced file size by -1%, 11.3%, and 4.35%, respectively. This is because the distribution of 1 in the BitFunnel matrix is irregular and uneven, so the values in the integer sequence are very large, which is not conducive to numerical conversion such as d-gap, resulting in poor compression of arithmetic coding. The compression scheme for bitmaps cannot meet the conditions because it requires more consecutive 0s and consecutive 1s using run-length, and the BitFunnel index construction completely depends on the document characteristics. To sum up, the traditional compression algorithm has poor compression effect on the BitFunnel index, while the dictionary-based compression scheme adopted in the present invention can effectively improve the compression rate.

Table 2

Table 2 shows the average intersection time and misnomer rate of each query under the two strategies. From Table 2, we can see that using the Pri strategy to generate the matrix to decompress on the MillionSet and TerabyteSet datasets increases the intersection time by 21% and 16%, respectively. Using the Opt strategy to generate matrices for decompression on the MillionSet and TerabyteSet datasets increases the intersection time by 48% and 37%, respectively. This part of the increase in intersection time is due to the use of partial compression so that some high-frequency access rows are not compressed, and it is necessary to determine whether each row is compressed when intersecting. At the same time, we can also find that dictionary compression increases the miscall rate by about 7 to 10 percentage points.

In terms of intersection, since the index needs to be decompressed, the compressed index takes 16%-48% more time to query. However, due to the characteristics of BitFunnel itself, only simple bitwise operations can be used to obtain relevant documents, so the intersection of its own The time is very small, accounting for a small proportion of the entire query time (the complete query includes the process of seeking intersection, calculating topK documents, generating summaries, etc.), so the intersection time of about 5 milliseconds has little effect on users. In addition, the compression will introduce an additional misnomer rate, which we use the threshold α to control within a certain range of 7 to 10 percentage points. Since the search engine will sort the documents obtained from the intersection by relevance and select the top K documents with the highest scores to return, the misrepresented documents caused by compression can be quickly filtered out due to their low scores. Therefore, we predict that in the actual search engine system, this part of the misnamed documents will not have a great impact.

Considering the three aspects of compression rate, intersection time and misnomer rate, the compression scheme proposed by the present invention has a better effect on compressing BitFunnel bit slice index.

The dictionary-based compression method of the present invention has been described in detail above, and specific examples are used in this paper to illustrate the principles and implementations of the present invention. The descriptions of the above embodiments are only used to help understand the method of the present invention and its core idea; Meanwhile, for those of ordinary skill in the art, according to the idea of the present invention, there will be changes in the specific embodiments and application scope. In summary, the contents of this specification should not be construed as limiting the present invention.

Claims (4)

1. A dictionary-based bit slice index compression method, wherein the method comprises: Step 1. Rearrange the documents according to the column density of bit 1 in the index column with the block size as an interval; Suppose the number of index columns is d and the block size is k bits; Step 1.1, count the density of bit 1 in each column of the index, and arrange the columns in descending order of density; Step 1.2, initialize an empty index, set the highest density of bits 1

column into index

column; put 1 with the next highest density

column into index

column, and so on, and finally the lowest density of bit 1

column put

List; Step 2, select a part of the query access low-frequency rows for compression according to the custom threshold value of the query data set characteristics; Step 2.1, customize the threshold for the frequency of high-frequency access row access during the query process; Step 2.2: According to some query data sets and custom thresholds, the rows are classified as follows: high-frequency access rows, low-frequency access rows; Step 2.3, establish a line compression flag file, and determine whether each line is a low-frequency access line, that is, the line needs to be compressed; Step 3, perform dictionary compression on the compressed row selected in step 2; Step 3.1: Divide the rearranged BitFunnel bit slice index into blocks in units of rows, build a dictionary to save a block of all 1s and a block that frequently appears in the compressed line selected in step 2, and record the mapping of high-frequency blocks and block numbers relation; Step 3.2, traverse the index, replace the block that appears in the dictionary with the block number with fewer bits; for the block that does not appear in the dictionary, replace it with the number of the closest block in the dictionary, although this will lead to errors in the query request. Claimed but guaranteed not to be lost. 2. The method according to claim 1, wherein the method application field comprises: Bitmap, Bloom Filter, and BitFunnel-based bit slice index structure based on Bloom Filter. 3. The method according to claim 1, wherein the threshold value of the high-frequency access row access frequency in the query process is defined in step 2.1: The threshold setting of the row access frequency of high-frequency and low-frequency rows in the query process is customized according to the repetition degree of the BitFunnel index block and the original miscall rate of the BitFunnel index. 4. method according to claim 1, is characterized in that, recovering the corresponding decompression method of original data after compression, specifically: During decompression, the original block definition is simply extracted from the dictionary using the block number as an index to restore the original data.

Images