How Search Really Works: The Compressed Index

This post is part of an ongoing series: How Search Really Works.
Last week: Recognize this index?

Memory is much faster than looking things up.

In order for a search engine in high demand to serve its users efficiently it should keep things in memory instead of looking it up on a disk.

Traditionally large scale search engines will keep their complete dictionary in memory and the posting list on disk.

Inefficient Storage

Obviously the more you can keep in memory and the more information can be read back with one disk action, the better.

Unfortunately computer information gets inefficiently stored in boxes with fixed dimension: if a box is 10 characters wide a 4 character word still takes up 1 box of 10 characters.

Compression

The solution is to squeeze information together so the least amount of space contains the maximum amount of information.

Big String Compressed Dictionary

could become:

By adding the length of each word to every entry we can make the list of words hundreds of characters shorter.

Gap Compressed Posting List

could become:

By storing the difference between the document ID's (the gaps) we can save hundreds of characters.

The same could be done for storing the gaps between the index numbers for the occurrence positions in each document.

This "compressed representation encodes occurrences of a term as a pointer to the next occurrence of the term to facilitate rapid enumeration of the occurrences of the term".

You could search "occurrences of the terms in the set of documents by following pointers through the compressed representation".

Partial Decompression

An index stored this way is completely lossless: it retains all information from document identifier to document positional identifier.

By starting with the least frequently used term in the search it is very easy to unravel to do a partial decompression of this index by

"identifying occurrences of the terms in the set of documents"

(the dictionary) - to then use;

"the corresponding term identifiers for the terms in the search request to look up a term offset table for a pointer to a first occurrence of the terms in the compressed representation of the set of documents"

(the very first posting document ID);

"and following a chain of pointers starting at the first occurrence to identify other occurrences of the terms in the compressed representation of the set of documents"

(the gap compressed document ID list)

Recommended reading:

• New Google Approach to Indexing and Stopwords