2
$\begingroup$

In p. 7 of the book "Introduction to Information Retrieval" (by Manning et al), the authors explain how, given a collection of text documents, an inverted index is built by tokenizing, then sorting the (term, docID) pairs, merging multiple occurrences of the same pairs, and the pairs for each term are grouped into a posting list. It is then mentioned that "Because a term generally occurs in a number of documents, this data organization already reduces the storage requirements of the index." My question is: how are the storage requirements reduced? It seems to me that if a term occurs in $k$ documents, then these $k$ documents' ID's must all be mentioned in the linked list for this term.

If a term occurs multiple times in the same document, then because the inverted index mentions a docID at most once in a term's list, there is a reduction in storage. But this condition is different from the condition that a term occurs in multiple (distinct) documents.

$\endgroup$
1
$\begingroup$

I think the author meant that by separating the index into the "dictionary" part and the "postings" part, we reduce the storage requirements of the strings themselves, because now we only have to store one string for each unique word. It's as if you are storing the vocabulary of the language itself, independent from the documents. It is also mentioned later that the dictionary is usually kept in memory, so it is important to make sure it doesn't take up much space.

$\endgroup$
  • $\begingroup$ ok, that makes sense. $\endgroup$ – jm jm Jul 2 '20 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.