Storing Inverted Index

Question

I know that inverted indexing is a good way to index words, but what I'm confused about is how the search engines actually store them? For example, if a word "google" appears in document - 2, 4, 6, 8 with different frequencies, where should store them? Can a database table with one-to-many relation would do any good for storing them?

Incurable

This is a bit too vague to answer. It really would come down to storing it as something like JSON or creating tables and referencing a foreign key. Storing it as a table means a table for each word you ever want to index though. Foreign key allows for normalization and easier modifying of a single record. – Sporophyll

Answer 1

It is highly unlikely that fullfledged SQL-like databases are used for this purpose. First, it is called an inverted index because it is just an index. Each entry is just a reference. As non-relational databases and key-value stores came up as a favourite topic in relation to web technology.

• You only ever have one way of accessing the data (by query word). That is why it's called an index.
• Each entry is a list/array/vector of references to documents, so each element of that list is very small. The only other information besides of storing a documentID would be to store a tf-idf score for each element.

How to use it:

If you have a single query word ("google") then you look up in the inverted index in which documents this word turns up (2,4,6,8 in your example). If you have tf-idf scores, you can sort the results to report the best matching document first. You then go and look up which documents the document IDs 2,4,6,8 refer to, and report their URL as well as a snippet etc. URL, snippets etc are probably best stored in another table or key-value store.

If you have multiple query words ("google" and "altavista"), you look into the II for both query words and you get two lists of document IDs (2,4,6,8 and 3,7,8,11,19). You take the intersection of both lists, which in this case is (8), which is the list of documents in which both query words occur.

Grigson

Answer 2

It's a fair bet that each of the major search engines has its own technology for handling inverted indexes. It's also a moderately good bet that they're not based on standard relational database technology.

In the specific case of Google, it is a reasonable guess that the current technology used is derived from the BigTable technology described in 2006 by Fay Chang et al in Bigtable: A Distributed Storage System for Structured Data. There's little doubt that the system has evolved since then, though.

Floccule

Answer 3

Traditionally, an inverted index is written directly to file and stored on disk somewhere. If you want to do boolean retrieval querying (Either a file contains all the words in the query or not) postings might look like so stored contiguously on file.

Term_ID_1:Frequency_N:Doc_ID_1,Doc_ID_2,Doc_ID_N.Term_ID_2:Frequency_N:Doc_ID_1,Doc_ID_2,Doc_ID_N.Term_ID_N:Frequency_N:Doc_ID_1,Doc_ID_2,Doc_ID_N

The term id is the id of a term, the frequency is the number of docs the term appears in (in other words how long is the postings list) and the doc id is the document that contained the term.

Along with the index, you need to know where everything is on file so mappings also have to be stored somewhere on another file. For instance, given a term_id, the map needs to return the file position that contains that index and then it is possible to seek to that position. Since the frequency_id is recorded in the postings, you know how many doc_ids to read from the file. In addition, there will need to be mappings from the IDs to the actual term/doc name.

If you have a small use case, you may be able to pull this off with SQL by using blobs for the postings list and handling the intersection yourself when querying.

Another strategy for a very small use case is to use a term document matrix.

Glia

What Inverted Index format should I use? All I want to find out the documents where a certain term was found. – Giacomo

Answer 4

Possible Solution

One possible solution would be to use a positional index. It's basically an inverted index, but we augment it by adding more information. You can read more about it at Stanford NLP.

Example

Say a word "hello" appeared in docs 1 and 3, in positions (3,5,6,200) and (9,10) respectively.

• Basic Inverted Index (note there's no way to find word freqs nor there positions)

"hello" => [1,3]

• Positional Index (note we don't only have freqs for each docs, but we also know exactly where the term appeared in the doc)

"hello" => [1:<3,5,6,200> , 3:<9,10>]

Heads Up

Will your index take a lot more size now? You bet!

That's why it's a good idea to compress the index. There are multiple options to compress the postings list using gap encoding, and even more options to compress the dictionary, using general string compression algorithms.

Related Readings

Index compression

Postings file compression

Dictionary compression

Leung

What if the map is stored in JSON format on Disk and pull back and convert back to map? – Giacomo