"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