11
$\begingroup$

In my notes is represented like this:

enter image description here

From wikipedia:

In computer science, an inverted index (also referred to as a postings file or inverted file) is a database index storing a mapping from content, such as words or numbers, to its locations in a table, or in a document or a set of documents.

Where is the inversion with respect to a normal index (like the one found at the end of books)?

Index: (in a book or set of books) an alphabetical list of names, subjects, etc. with reference to the pages on which they are mentioned.

Am I missing something? Like a nuance of the meaning of the name due to the fact that english is not my main language.

$\endgroup$
1
  • 1
    $\begingroup$ You spotted this very well, many real world usecases of an index work exactly like what IT calls inverted index. It’s just that he inverted index is a somewhat newer concept and the word index was already used for indexing positions in sequences. Also, often when inverted index s used, there might no longer be a. Original document to work on. So search Engines can find sentences by looking up each component and then retrieving the subset of positions which are close to each other. That’s a somewhat unique usecase implied by the new term. $\endgroup$
    – eckes
    Oct 5 '20 at 20:49
16
$\begingroup$

Here is an array:

  • A[0] = Alice
  • A[1] = Bob
  • A[2] = Charlie

Here 0,1,2 are indices.

Now suppose that we want to know which index contains a given word. Then we use a dictionary:

  • D[Alice] = 0
  • D[Bob] = 1
  • D[Charlie] = 2

This is an inverted index (according to your Wikipedia quote).


The word index has different meaning in different contexts:

  • Technical books often have an index of terms at the end.
  • The Catholic church held an index of forbidden books.
  • In economics, there are financial indices.
  • In computer science, an index is usually an integer used to index into an array.
$\endgroup$
4
  • 3
    $\begingroup$ Yes, but where is the difference with a normal, non-inverted, index? To me the definition of an inverted index (both on wikipedia and on the image on the notes) seems the same as the one of an index $\endgroup$ Oct 4 '20 at 19:39
  • 8
    $\begingroup$ The word index in computer science has a different meaning from its usual meaning. This is what you're missing. In A[i], we call i an index. This is the meaning of index in computer science. An index at the end of a book is not what index means in computer science. $\endgroup$ Oct 4 '20 at 21:09
  • 3
    $\begingroup$ I agree with the answer from @Pseudonym. I would disagree with "In computer science, an index is usually an integer used to index into an array". There is a whole field of index structures (tree indexes, spatial indexes, ...) all of which are neither arrays nor do they require an integer key. I suppose the term 'inverted' has some historical reasons and is, to my knowledge, used mainly in the database community and text processor community. $\endgroup$
    – TilmannZ
    Oct 5 '20 at 19:44
  • $\begingroup$ "In computer science, an index is usually an integer used to index into an array.". Or an index in a relation as in SQL, or or or. $\endgroup$
    – Polygnome
    Oct 6 '20 at 7:16
9
$\begingroup$

The reason why we use the term "inverted index" is that the term "index" came to computer science first. In fact, it has several common meanings in computer science, but in this case it refers to the more general concept of an efficient lookup data structure for a database.

What we call an "inverted index" is, strictly speaking, an inverted file used as a database index. "Inverted file" is the data structure, and "index" is the use to which it is put. A B-tree data structure, similarly, can be put to more uses than just database indexing, but it makes sense to talk of a "B-tree index".

The index in a book is not the only kind of text index. Strong's Concordance, which is considered an important ancestor of modern full-text search, is a permuted index (specifically, a variant known today as a KWIC index).

The inverted file is not the only data structure that can be used for text/string indexing. Suffix arrays and Burrows-Wheeler indexes are commonly used for strings that don't need linguistic analysis such as indexing DNA or RNA sequences. Some of these index variants have efficient partial match queries.

The signature file (a probabilistic index structure, essentially Bloom filters for text search) was briefly popular, but it turned out to be nowhere near as generally useful as its competitors.

$\endgroup$
3
$\begingroup$

It's Relative

The distinction is between "keys" and "values". However, what counts as a "key" vs. a "value" depends on the maintainer. Consider a phone book. Most people would keep a phone book around because they know the name of someone they wish to call, but don't know their phone number. Thus, the book is arranged with names as the key, and phone numbers as the value. On the other hand, it is also useful to see a phone number which is calling you, and know the name associated with it. We generally call this service "Caller ID". Since this mapping from phone number to name inverts the most common search, one might call the database which contains this information an "inverted index" from values to keys. Even so, it's merely a matter of perspective. The phone company may very well maintain the information in a database with the number as the primary key and the subscriber as a non-key field, which would therefore cause the Caller ID function to depend on an "index", while the phone book would be considered an "inverted index".

Google

Since the URI is, by definition, the canonical way to identify a web page, it is natural to use the URI as the key when building a collection of web pages (relational theory tells us that the primary key should be unique for each tuple, although that is not really true for URIs, since they have relative addressing and aliases). Unfortunately, this is only useful for answering queries like: "Which URLs contain the word 'cat'?" Most users are not interested in such queries. Most users are more interested in searching not by the keys of this index, but rather by the values: "Which pages contain the word 'cat'?"

Now, we know that URIs are logically the keys to a web search index, because you can't follow content words from one page to another. You can only follow URIs. Further, if your crawler ends up at the same page from multiple pathways, you don't want to store the page multiple times as distinct entities. You want to ensure that each page is stored at most once. This is also a good reason to use the URI as the index. However, in order to support the content search function, it is useful to create a mapping from content words to URIs. Since the page content is considered the values of the index, this value to key mapping is therefore called an "inverted index".

If, for some reason, it were more natural to index web pages internally by their content, then that would be considered the "forward index", and the URI to page mapping would become the "inverted index". But web pages resist this categorization because the content is not necessarily stable over time, while the primary key of a tuple should remain immutable (and effectively, HTTP attempts to enforce this by providing redirects when the URI for a page logically changes). Thus, URI to page content is strongly preferred as the "forward mapping".

Books

If you want to know what page a particular word appears on in a book, you may have to search the whole book to find the answer. Thus, the "index" in a book maps from keywords to pages. But if you want to know what words appear on a particular page in a book, you just need to turn to that page and you will find the answer after reading at most one page. Random access to a particular page in a book is fast and efficient (relatively speaking), which is why books generally don't come with a mapping from page numbers to keywords (wouldn't that be an unusual book?!). However, one could make the argument that the page number is the most natural "index" for the content in a book. I would base this argument on the fact that indexed access is usually the naturally fastest access method for a database. Note that word-based access without an index is essentially sequential (assuming the book is not specially ordered, like a dictionary). From this perspective, one could quite reasonably argue that the "index" in a book is really an "inverted index", in very close analogy to the Google scenario. We simply define the page number as the "URI" for page content within a book, and you have a kind of isomorphism between book pages and web pages (complete with the fact that textbooks will sometimes refer to other pages within the book by page number or chapter).

Memory

If we examine computer memory, we see that the CPU only allows us to access its contents by address. Therefore, the memory address is the "key" to the datastore that we call "working memory". If you had the query: "Tell me the locations which contain the value 0x12345678", you would be frustrated by the fact there are no machine instructions which perform this function (although, CISC architectures like x86 come close with instructions like REPNZ SCAS).

When a memory is specifically designed for the inverse value to key search, we call it a "content-addressable memory". This can be implemented in hardware or software (but most commonly in software, via associative maps of all kinds). Again, the fact that searching for a value by address is easy, while searching for an address by value is hard biases the definition of "key" and "value" for the case of general memory in a very natural way. Good luck finding someone who calls a MOVE instruction an "inverted index" because they think of memory contents as keys and addresses as values.

Conclusion

While an "index" does not necessarily require a unique set of keys, this is almost universally preferred. And, since the majority of mappings in the world are not bijective, it is often the case that the "values" for an index are far from unique. These facts orient the "natural" definition of an "index": a mapping from a set of unique keys to non-unique values. Then, the inverse mapping is naturally an "inverted index".

A quick rule of thumb to tell whether you are looking at an index or an inverted index to ask: "How many results do I get for this key?" If the answer is: "Zero or one", then you are probably querying an index. If the answer is: "Zero to many", then you are probably looking at an "inverted index". And so, contrary to convention, you should think of the table at the end of many books as an inverted index, rather than an "index". ;)

$\endgroup$

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.