Topic 3
The inverted index
Term-based retrieval is fast because of the data structure behind it. AI Engineering (Ch. 6, "Term-based retrieval") describes the inverted index used by Elasticsearch, which is built on Lucene: a dictionary from each term to the documents that contain it. It can also store each term's frequency and document count, which help in computing TF-IDF scores.
Predict first
Scroll sideways to see the whole diagram
The query, after lowercasing and dropping stop words, is three terms that appear in the collection.
Text version
- The query, after lowercasing and dropping stop words, is three terms that appear in the collection.
- An inverted index maps each term to the documents that contain it, with how often: like the index at the back of a book.
- Look up each query term. The number of documents in each list is the term's document frequency, which IDF needs.
- Only documents on some list are scored. That's why term-based search is fast, and why a document sharing no term is never returned.
Terms and articles from the search-lab help centre (lib/labs/data/search-lab.json).
The same structure explains a behaviour you've already seen: a document that shares no term with the query isn't on any list, so it isn't returned at all. For “how do I stop paying every month”, the only match in the collection is “every”, in the Wi-Fi article, and the cancellation article never appears.
The book also mentions an alternative: score documents by n-gram overlap with the query, the lexical similarity of Module 04. It works best when queries and documents are similar in length. When documents are much longer, many of them overlap with the query by chance, and the scores stop separating relevant from irrelevant.
Quick check