Lecture 4: Indexing and inverted files | by Arjen de Vries
Abstract IR architecture, with an online and offline segment.
In this lecture we assume there's a query, i.e. the user knows what she wants to ask and search in a collection of documents.
In practice collections are always growing. In IR research, we usually work with snapshots.
The techniques we show today are most suitable for collections that don't grow very fast. In practice, for example for twitter, you need extra measures to deal with a collection growing at a fast pace.
Q: What is a major difference between the datasets used for IR research and real-world datasets?
Today we discuss the index, which stores documents such that they are easier and faster to access.
Representations
Representation function: from query to query representation, from document to document representation.
Representations are fed into a comparison function (doc representations first go through the indexer).
The main takeaway is: we work with document representations and not directly with documents. How do we represent documents?
If you would have a very good dictionary, lemmatization would be preferable. In practice, stemming is used widely to reduce words to a common form (good enough). Con: policies and police will get same stem 'polic'. But on average on a large scale, stemming is still beneficial.
Q: What is a issue with lemmatization? Is this issue problematic in practice?
Retrieval system usually ignore á, ä, é and reduce to a, a, e. This doesn't introduce too many extra synonyms.
Usually, metadata is merged into the document itself.
In web crawling, a variant of this is to include text in the document that originates from webpages referring to the document currently indexed. It's common to include anchor texts of pages referring to the current one.
IR researches usually do not use markdown, but commercial IR systems do.
Inverted Index
Without index, the comparison function is very slow. With indexing, you find exact matches more efficiently assuming the query is "correct".
An inverted index is the most efficient and flexible index structure; and a default technique to rank documents efficiently on their similarity to the query.
Everyone uses inverted index. But in practice, everyone even uses the same base implementation, namely of the open source project: Lucy.
The alternative is a hashing based approach.
The inverted index looks a bit like this:
term -> [posting{docID, payload}; posting{docID, payload}; posting{docID, payload}]
The main point of the inverted index is to point to docIDs where that term occurs. Note that the payload is optional.
A web collection easily has 14 million unique terms in the document representations (after processing documents). So our list of terms is already very very long, and for each term, we have pointers to postings, which contain a document ID and a payload. A payload is associated information such as word count and position of the term in the document.
How do we represent postings?
We start with a binary matrix. You'll see that if we encode this as a matrix we need far too much memory. You'll also see most cells are empty, so this matrix would be extremely sparse.
(For sparsity, consider Zipf's law ) (if you let a monkey type on a keyboard with a space bar that's 20% of the keyboard, the distribution of (nonsense) terms will still follow Zipf's law. So this law does not necessarily show something about human intelligence/psychology)
Q: Why do we not store postings in a binary matrix?
So, instead, we can only save pointers to document identifiers. Pointers are slow! So this is still not how we do it in practice. Instead, we store the docIds in blocks and then chain together the blocks with pointers.
The drawback of this approach is that in this Zipfian distribution there are many terms that only occur in a few documents. If you make your blocks to large, you'll end up with underfilled blocks.
So there's a trade-off here when it comes to the actual engineering of storing the representations: do I work with many pointers (slow retrieval) or do I accept that I'll have to waste a lot of space with underfilled blocks.
For each term, the postings list is kept in sorted order (i.e. the postings are sorted on DocID)
Q: Why is the postings list usually kept in sorting order?
We should remember that queries contain multiple terms usually and that often we want to look for all of them at the same time. If we sort both query and the posting list, we can do smarter efficient lookups during query processing. For example, we want to find documents that contain all query terms in a document. E.g. "fish green": we immediately see there's no match because if the first posting does not correspond; we no longer have to look at the rest. So in this case, the lookup is better because we are comparing two lists. This would be way harder if the lists were unsorted.
This speedup is especially significant if you consider Zipf's law again. Let's say one term occurs in 75% of the documents and our webcrawl contains 400 million documents. Then our posting list is 300 million entries long... The sooner we can stop traversing that, the better!
A second reason is a bit more nuanced. If a term occurs in almost all documents, the corresponding DocID occurs in almost all the postings. It is then smart to assign this document a DocID that takes very little memory in order to reduce the space usage of the index.
Q: Why do we not use pointers to DocIDs for a posting?
Variant with tf and df
Important detail: We store the document frequency together with the term id, in the term dictionary. Of course we only have a single document frequency per term, so we include that once at the beginning in the term dictionary.
Those we map onto (docId, termFreq) pairs. Term frequency is specific to a single document so that information has to be coupled to the docID.
To save memory we need to think about how do we group these together to reduce the number of pointers.
Now, of course we may also have more info in the payload. For example, we can also store the positions of the term in the documents.
Example:
fish -> 2 -> (1,2,[2,4])->(2,2,[2,4])
Format: term -> df -> (DocID,TF,[term position,term position])
The payloads can still get pretty large for very large files.
Example of previous exam question: Given a named entity recognition scenary, how would you store information in an inverted index?
Compression
bzip and gzip are the best algorithms for compressing size.
bzip is the best around if you want to compress the data the most. The problem is that if you decompress the document, this is very CPU costly. So the goal of compression is not only to compress the most, but also to keep decompressing cheap! You'd want decompression methods optimized for CPU to boost speed from MBs/s to Gbs/s.
So we don't care about compressing as much as we possible can. So bzip is disqualified.
Modern webcrawl is 150Tb. Inverted list are very large, so we store them on disk. Collections are usually larger than available memory. (As soon as memory hardware is better, people apparently also start storing more things).
Compression methods used in inverted file structure:
- Bit-aligned
- Byte-aligned
Questions in exam will probably be focused on byte-aligned techniques, i.e. on Vbyte.
Byte-aligned: use smaller amount of bits for the most frequently used terms. (Remember the exponential distribution a.k.a. Zipf's law) We gain a lot if the term identifier for the most frequent word is a very small amount of bits.
Vbyte encoding
Vbyte encoding: use 7 bits for information, 1 bits with 0 indicating that we have all info, and 1 indicating that we also need the information stored in the next byte. So the first bit of each byte is the continuation bit. This way we "chain" away.
The idea is that you use the first 7 bits (i.e. the byte + continuation bit) for the very frequent term identifiers. You use the second byte for slightly less frequent terms; the third byte for even less frequent term IDs and so on.
The continuation bits ensure that you always only read what you actually need and not more. This encoding is very very simple and doesn't require complex lookups in internal tables. This saves time and facilitates very fast decoding. The trade-off is obviously space: you give up a single bit of each byte. (And this compression method is also not as effective in terms of space reduction as gzip and bzip).
Q: What is the different between bit-aligned and byte-aligned compression methods?
Q: How does Vbyte encoding aids compression / storage reduction of the inverted index?
Q: What's the advantage and downside of Vbyte compared to compression algorithms such as bzip and gzip?
Gap encoding / delta encoding for the postings list
Another encoding trick to save memory: In the posting list, do not store the document identifiers, but the difference between the identifiers of two consecutive documents.
We sort the documents in sorted order anyways because that was handy for processing two lists for multiple terms. For the frequent terms, there are a lot of different documents that contain that term. So if you then take the difference, the idea is that on average you get a smaller number. By compressing the gaps between the identifiers instead of the identifiers, you get an even tinier posting list, because on average the difference will be a smaller number.
But consider a bad case: If you take the difference between two document IDs that are really far apart, you'll still get a large number; so taking the difference here does not really help (and you'll have a bit more overhead anyways). But the central insight here is that this does not really matter on average!
In VByte, smaller numbers will occur a lot because the frequent DocIDs are the ones encoded with less space (e.g. the 1byte representation). Large gaps/differences only occur infrequently (because this happens for infrequent terms by design of the VByte encoding), so on average this approach wins space.
Q: Why is gap encoding space-efficient in combination with VByte encoding?
Retrieval and query processing
Retrieval is the manipulation of an inverted file structure in order to rank documents.
How to produce query results?
- Document-at-a-time
- Calculates complete scores for documents by processing all term lists, one document at a time.
- Term-at-a-time
- Accumulates scores for documents by processing term document lists one at a time
- This one is conceptually easier
- Mix both when you have longer queries
Optimization research into mix and match; or stopping early.
Remember: Where was doc frequency stored? In the term dictionary right before the postings. If we have a query of 5 terms, which term would we start with? The one with low document frequency, because that one's posting lists is very small. This increases your chances of potentially benefiting from stopping early. Why? Let's say that we want to produce 10 ranked results. Well, we may at some point know that the 11th document can never amass enough score to rank higher than the 10th score, even though we have not processed all query terms yet. Then we can safely stop. Of course, in IR we don't know anything for sure so there's also plenty of unsafe approaches.
If you do early stopping you need a partial document store to keep intermediate results until you are done.
Q: How can knowing the document frequency of a term potentially speed up query processing?
Document-at-a-time vs term-at-a-time
Data structure: If we are interested in a top K ranking, then a data structure where we only keep track of the top-20 results is appropriate. We can use an accumulator like a min heap to keep track of the best scores.
For document-at-a-time, we align the postings on documents, accumulate the score per document, and then store in on e.g. a min heap.
N.B. Min heap (accumulator) is completely different from a regular heap with pointers and does in fact not use pointers! Min heap is a smart efficient method for updating an array in order to maintain a top-k ranking. Can be theoretically shown it's an order 1 operation k times (so order k) to maintain the top k ranking.
Trade-offs:
- Pro: Small memory footprint because...
- We only need one document at a time; we only maintain the min heap throughout
- We do not need to load the full postings into memory!
- Pro: We can skip some postings
- Recall that we stored postings in blocks (and not with pointers; even though the illustrations suggest that because it's conceptually easier to display). Each block contains metadata about its contents (e.g. lowest and highest DocID) that quickly allows you to see whether you need that block or not.
- Con ?
For term-at-a-time, we have:
- Pro: Optimization by starting with most rare terms
- Allows for early termination heuristics
- Accumulate document stores while traversing terms
- Con: Large memory footprint, because we need to have the whole listing in memory and store intermediate results
- Pro: Filtering heuristics are possible though; but are complicated.
Q: Explain the difference and the trade-offs between document-at-a-time and term-at-a-time query processing.
Q: What is a typical data structure that is used in document-at-a-time query processing?
Boolean Retrieval
Some people still prefer boolean retrieval (do not produce ranking) over ranked retrieval. Why?
They are still standard practice in domains where only experts are searching, for example patent lawyers or medical researchers. They tend to construct large complicated boolean queries.
Why do they work with an outdated paradigm? They earn their money with finding the right answers to their query. E.g. when a lawyer says "there is no patent", which may trigger business decisions of 100s of millions of dollars. In this case, you don't want a search machine to rank results and miss one. So in this case, the cost of missing a result is too high.