Index Compression

"People are good at intuition, living our lives. What are computers good at? Memory" - Eric Schmidt

With great power comes great responsibility. Memory indeed is an area of prime concern in nearly each and every operation a computer performs and is a valuable resource, often possesing dominion over regulating the "speed" of computation. Realizing its significance, utilizing it judiciously is without a doubt desirable and wise.

In our IR system, we would like to store our Inverted Index in the least possible space and conserve the "all-powerful" resource. Compressing does this for us. So, before storing the Inverted Index, we involve one more step - "Index Compression" and as you would have expected, while retrieving we will need to "decompress" the information instead of using as is.
Fortunately, the addition of this step contributes to speeding up our system rather than bogging it down.

The preferred indexing scheme - Inverted indexing, stores the information classified as "Dictionary" and "Posting lists".
Here Dictionary contains:
• "terms"(obtained after tokenization, normalizing, removing stop words*, stem/lemmatization* and sorting),
• "document frequency"(no. of documents that contain this term) and
• "pointers" to each postings list

And the posting list record the document ids where the corresponding term appears(can be extended to store position within the document).
*: optional, not considered here

Now, to make sure you understood it right try constructing an inverted index for:
d1: Don't be evil
d2: Be what's next

 
            

            

Dictionary compression If parts of the dictionary are on disk, then many more disk seeks are necessary in query evaluation. Thus, the main goal of compressing the dictionary is to fit it in mainmemory, or at least a large portion of it, to support high query throughput. One of the most trivial approach for storing dictionary terms is storing it as "Fixed Array Entries". But owing to varying term lengths in the dictionary which imply memory wastage due to the unoccupied space, it is not a feasible choice. Next, we could store the "Dictionary as a String" where each term can be accessed using a pointer. This offers considerable improvement over the previous approach. However, it can be improved further using "Blocked Storage". We can compress the dictionary by grouping terms in the string into blocks of size k and keeping a term pointer only for the first term of each block. We store the length of the term in the string as an additional byte at the beginning of the term. We thus eliminate k - 1 term pointers, but need an additional k bytes for storing the length of each term.
One source of redundancy in the dictionary is the fact that consecutive entries in an alphabetically sorted list share common prefixes. This observation leads to "Front Coding". A common prefix is identified for a subsequence of the term list and then referred to with a special character. This avoids storing redundant prefixes and usually offers significant benefit in compression.
Learn about Front Coding in detail here

Posting list compression Usually, any practical IR system will contain a large number of documents and storing document ids in posting is often expensive. As for the terms occuring in documents with document id of higher magnitude will need more space. One observation could be that the gaps between postings are short, requiring a lot less space than used by their magnitudes. In fact, gaps for the most frequent terms such as 'the', 'and', 'for' are mostly equal to 1. But the gaps for a rare term that occurs only once or twice in a collection and give negligible advantage. One solution to this is "Variable Byte Encoding", where the gaps are compressed further and shorter gaps take less space.
Learn about VB Encoding in detail here



Recommended References
• An Introduction to Information Retrieval. Christopher D. Manning, Prabhakar Raghavan, Hinrich Schutze.
• Information Retrieval course by Dr. Venkatesh Vinayakarao(Sep - Dec 2021)
• Video by Dr. Venkatesh Vinayakarao