Inverted Index Construction: From Sparse Matrices to Scalable IR Storage

[00:00:07]let's now look at a slightly more realistic scenario where the number of documents in the Corpus is not 37 as in Shakespeare's Corpus but about a million documents that's not quite a lot lot it's still orders of magnitude smaller than the number of documents on the web but it's still slly more realistic than uh just 37 documents in the corpus now for a million documents let's say these are uh news documents for a million news documents it turns out that if you do some Empirical research you find that the number of distinct terms in in such a corpus will be about 500,000 this is something we kind of find empirically and the actual values for different corpora may be different but let's just work with uh values that are approximately in this range what we're going to see is that even for this slightly larger Corpus the term document incidence Matrix solution that we just came up with is going to encounter some issues if we build a term document incidence Matrix using a million documents which have 500,000 distinct terms the the the Matrix that we build will have 500 th000 rows because the number of rows is the number of distinct terms in the Corpus and the number of columns is going to be 1 million because that's the number of documents in the Corpus so the number of cells in the term document incidence Matrix will be 500,000 multiplied by 1 million which is 10 ^ 6 and this turns out to be uh5 * 10 ^ 12 or about half a trillion cells in The Matrix now if you want to store a matrix with half a trillion cells in in memory in order to work with it how much memory would you require well we have each cell containing either a value of Zer or one so even if we assume simplistically that we can store each cell in one bit well let's work with one bite first let's say that each cell is going to take up just one bite that means we need these many number of bytes in main memory to work with this Matrix now this turns out to be so how much is5 * 10 ^ 12 bytes this turns out to be 500 * 10 ^ 9 bytes or 500 GB now no computer today at least not the PCS that you find in the market are going to have a ram of size 500 GB and even if we were to store each cell using just one bit in some way that would still be 500 divided 8 number of 500 GB divided by 8 because we would be using 1/8 of the space since there are 8 bits in a bite that would still be quite large compared to the amount of ram that is available in in a typical laptop or PC today so you can see that we're going to run out of space even with a small corpus with a million news documents and as an aside this corpus with a million documents if they are typical news documents will be about two to three book pages long each document will be about two to three book pages long which is about 1,000 words so let's also assume that each of these million documents is about a th000 words long and let's let's assume that each word is about 6 bytes long these are not unreasonable assumptions these are in fact uh numbers calculated empirically from a typical News Corpus we'll come to that in a later uh chapter how we arrive at these values but let's just assume them for now so each document has about 1,000 words and each word has uh takes up six bytes which includes the accompanying space or punctuation marks like commas full stops and so on so these six bytes include not just the characters of the word but also the accompanying spaces and punctuation marks so if each document has 1 th000 Words 6 bytes word the size of a typical document will be 6,000 bytes and because there are a million documents the size of the Corpus as a whole will be a million * 6,000 bytes which is 6 * 10 ^ 3 * 10 ^ 6 or 6 * 10 ^ 9 bytes which is 6 GB now that's reasonably large compared to Shakespeare's Corpus but it's still orders of magnitude smaller than the amount of data that's available on the web so going back to this uh term document incidence Matrix we saw that it's impractical to build a term document incidence Matrix even for a corpus of these many documents or this much size so how do we cut down on the space we really need to cut down on the space in order to successfully build a system which will be able to handle queries on this Corpus and the first thing the first thing that we need to notice here in order to come up with a more efficient solution is that this term document incidence Matrix is going to be a very sparse Matrix what is a sparse Matrix if you've done a course on data structures you would remember that a sparse Matrix is a matrix in which most of the entries are zero that is the number of nonzero entries is a small fraction of the total number of entries in The Matrix now I'm going to claim here that the Matrix the term document incidence Matrix that we generate over here is going to be a very sparse Matrix that is the non zero or the one entries are going to be sparsely present in The Matrix why is that true well to see why that's true let's just focus Fus on a particular column of the Matrix let's say we focus on this document Antony and Cleopatra of course I just said that we looking at a typical new whereas here we have a play of Shakespeare but we just working with a toy example for the purpose of illustration here um we want to show something diagrammatically here that's why I'm using this example so if you just focus on this document you can see that it's going to have a certain number of ones in the column Vector which correspond to The Words which appear in this document now let's try to derive an upper bound on the number of ones that can appear in this column vector and see what percentage of the total number of entries in the vector that is so how can we maximize the the number of ones in this column Vector the larger the diversity of words that appears in this document the more the number of ones in this column Vector because if there are if there are more words of different kinds present in a document then when we pre-process the Corpus and pass that document for the purpose of generating this Matrix we will we will be adding a one to The Matrix whenever we encounter a new word for the first time so if every word in the document is a new word that is how we will maximize the number of ones in the Matrix whereas if there are words which appear multiple times in the document then we are not going to work with the when we encounter that word again the first time we encounter that word we're going to add a one but when we encounter that word again we not going to do anything because we are dropping information about how many times the word is appearing in the document we just keeping track of the presence or absence of the word in the document and we're also not tracking what the positions of the words in the documents uh were so if you just have to note the presence or absence it's basically how many distinct words appear that appear in the document that that are important that's important so if you want to maximize the number of ones we have to that's going to happen with a document where all the thousand words are different so what is the maximum percent AG of ones possible in a column Vector we can at most have a th000 ones in a in a single column Vector whereas we know that the length of the column Vector is 500,000 because there are 500,000 rows here so if you calculate the percentage of once in such an artificial extreme scenario that turns out to be 10 ^ 5 / 500,000 which is just just 1X 5 or 2% so 2% is the upper bound on the percentage of ones in a column vector and this applies to any column Vector this means that even in the Matrix as a whole the maximum percentage of mons is bounded from above by 2% we could have alternately just computed the maximum possible number of ones in the Matrix as a whole which would be the maximum possible number of ones in a single column Vector multiplied by the number of columns so that would be 1,000 multiplied by the number of columns which is the number of documents and that's a million so this comes out to be about 10 ^ 9 or a billion ones now since the total number of cells in The Matrix are.5 trillion the percentage of once in this case would be a billion divid.5 trillion time 100 which also comes out to be 2% because that would be 10 ^ 9 /5 * 10 ^ 12 * 100 and and this is 1x 5 or2 2% so this means that at most 2% of the entries in The Matrix are 1 or at least 99.8% of the entries in The Matrix are zero so this shows that this term document incidence Matrix is a highly sparse Matrix now how do we cut down the amount of space so that we can have a more practical solution for U building a system system that can answer the query that we had so typically how sparse matrices are represented is not by storing is not by allocating space for every cell in The Matrix but just recording the nonzero positions if we just keep track of the non-zero positions we will need to keep track of only 2% of the original number of cells so by default we're going to assume that an entry is going to be a zero unless we are explicitly recording that it's a one so for example if you look at the row Vector here for Brutus Brutus appears in three of the plays in this toy example the first one the second one and the fourth one so instead of storing this entire row Vector which will be uh a million documents long in the example in the example that we saw we just have to store we just have to record in which documents Brutus is actually present so that's document number one document number two and document number four um it Brutus is not present here so this entry is a zero so it's we just have three ones in this row vector and notice that for the purpose of um this example we are assuming that each document is assigned a unique doc ID so the documents are numbered from 1 to a million the first document is uh numbered one the second one is assigned an ID of two and so on so the way we will store this row Vector for Brutus is not by storing all the entries but by only recording the doc IDs 1 2 and 4 with Brutus likewise we are going to associate at with the term Caesar not this entire row Vector but just a list of five doc IDs 1 2 4 5 and 6 and if you look at the calponia row Vector because calponia appears in only one of the plays which is the second document we'll just record the number two for calonia so we are only recording the one positions and this is the standard way in which spar matrices are represented in order to conserve space now notice that this is pretty much what the index at the back of a typical book or novel looks like in a book index you have an alphabetical list of words at the end and for each word you have a list of page numbers on on which that word appeared so if you were to imagine uh each page of the book as a separate document with the page numbers being the doc IDs then the structure we have here is identical to the index at the back of a book so in case you forget what this solution is you can just remember what how the index at the back of a book looks like and you'll be able to immediately recall this structure where you have uh terms on one side and then a list of Doc IDs on the other side in increasing order of IDs and this brings us to the notion of an inverted index which is at the heart of what information retrieval is about an inverted index is this structure that we just came up with where for each term T we store a list of all the documents that contain T and we don't actually store the documents here we we would have assigned a unique doc ID to each document and we store a list of Doc IDs corresponding to the documents containing that term T so this is an inverted index you have these terms on one side and then you have lists of Doc IDs on the other side most often we just call this not as an inverted index but just an index or a search index so when the word index appears in the context of an information retrieval system it means an inverted index or the index at the back of a book as a close analogy a database index is different so you shouldn't get confused between uh uh these two these two indices a database index and an IR index which are two different things