Offensive Security Researcher & Quantum Cryptography Analyst

Inverted Indexes Algorithm: Working, Explanation, and Information Retrieval

Abdul Wahab Junaid
Inverted indexes algorithm and working of this algorithm

Inverted indexes algorithm and working of this algorithm

I want to explain the inverted index the way I understood it while learning how search engines work. An inverted index is a data structure that maps content, usually words, to the locations (documents) where they appear, instead of mapping documents to the words they contain. I find this idea important because it’s the backbone of nearly every search engine I use, letting me search millions of documents for a keyword in milliseconds instead of scanning every document one by one.

History and Background

I found that inverted indexes have roots going back to manual concordances of religious and literary texts, where scholars listed words and the pages they appeared on, long before computers existed. In computing, the concept became essential with the rise of information retrieval systems in the 1960s and 1970s, and it became the foundation of modern search engines once Google and other companies scaled it to index the entire web starting in the late 1990s.

Problem Statement

The problem I need an inverted index to solve is fast keyword search across a huge collection of documents. If I searched by scanning every document for a keyword every time (a “forward” or linear search), it would take far too long as the collection grows. I need a way to precompute which documents contain each word, so a search becomes a fast lookup instead of a full scan.

Core Concepts

How It Works

  1. I collect a set of documents to index.
  2. I tokenize each document into individual words, removing punctuation and often stop words.
  3. For each word (term), I record which document IDs it appears in, building a posting list per term.
  4. I store these term-to-posting-list mappings in the inverted index structure.
  5. When a search query comes in, I tokenize the query the same way, look up each term’s posting list, and combine (intersect for AND queries, union for OR queries) to find matching documents.

Working Principle

The internal logic relies on inverting the natural document-to-words relationship into a word-to-documents relationship. Once built, this structure lets me answer “which documents contain word X” in near-constant time through a hash table or sorted lookup, rather than scanning through every document’s content at query time. The precomputation cost is paid once during indexing, and it pays off across every subsequent search.

Mathematical Foundation

I often describe search relevance using Term Frequency-Inverse Document Frequency (TF-IDF), which scores how important a term is to a document within a collection:

$$\text{TF-IDF}(t, d) = tf(t,d) \times \log\left(\frac{N}{df(t)}\right)$$

where $tf(t,d)$ is how many times term $t$ appears in document $d$, $N$ is the total number of documents, and $df(t)$ is the number of documents containing term $t$. This formula tells me that common words appearing in many documents get a lower weight, while rare, distinctive words get a higher weight, which helps rank search results by relevance.

Diagrams

flowchart TD
    A[Documents] --> B[Tokenize Text]
    B --> C[Extract Terms]
    C --> D[Build Term -> Posting List Mapping]
    D --> E[Inverted Index]
    F[Search Query] --> G[Tokenize Query]
    G --> E
    E --> H[Return Matching Document IDs]

Pseudocode

function BUILD_INDEX(documents):
    index = EMPTY_MAP()
    for doc_id, text in documents:
        terms = TOKENIZE(text)
        for term in UNIQUE(terms):
            if term not in index:
                index[term] = EMPTY_LIST()
            index[term].append(doc_id)
    return index

function SEARCH(index, query):
    query_terms = TOKENIZE(query)
    result = index[query_terms[0]]
    for term in query_terms[1:]:
        result = INTERSECT(result, index[term])
    return result

Step-by-Step Example

Suppose I have 3 documents:

  1. Tokenizing gives terms: Doc1 → {the, cat, sat}, Doc2 → {the, dog, ran}, Doc3 → {the, cat, ran, fast}.
  2. Building the index: the → [1,2,3], cat → [1,3], sat → [1], dog → [2], ran → [2,3], fast → [3].
  3. If I search for “cat ran”, I look up cat → [1,3] and ran → [2,3].
  4. Intersecting these lists gives [3], meaning only Doc3 contains both “cat” and “ran”.

Time Complexity

Building the index takes $O(T)$ where $T$ is the total number of word tokens across all documents. Once built, a single-term query lookup takes $O(1)$ average case with a hash-based index, and multi-term queries take $O(m + n)$ time to intersect two posting lists of length $m$ and $n$ if they’re sorted.

Space Complexity

Space complexity is $O(T)$ in the worst case, since I store an entry for every occurrence of every term across all documents, though in practice, compression techniques (like delta encoding of document IDs) significantly reduce the actual storage needed.

Correctness Analysis

I consider the inverted index correct as long as every document that contains a term is included in that term’s posting list, and no document that doesn’t contain the term is incorrectly included. This directly follows from how the index is constructed — during indexing, I only add a document ID to a term’s list when that term is genuinely found in that document’s tokenized text.

Advantages

Disadvantages

Applications

I see inverted indexes used in web search engines, document retrieval systems, log search tools like Elasticsearch, library catalog systems, e-commerce product search, and email/message search features.

Implementation in C

Here is a simplified inverted index builder and searcher in C.

#include <stdio.h>
#include <string.h>

#define MAX_TERMS 50
#define MAX_DOCS 10
#define MAX_LEN 20

typedef struct {
    char term[MAX_LEN];
    int doc_ids[MAX_DOCS];
    int doc_count;
} IndexEntry;

IndexEntry index_table[MAX_TERMS];
int index_size = 0;

void add_to_index(char* term, int doc_id) {
    for (int i = 0; i < index_size; i++) {
        if (strcmp(index_table[i].term, term) == 0) {
            // avoid duplicate doc_id entries
            for (int j = 0; j < index_table[i].doc_count; j++) {
                if (index_table[i].doc_ids[j] == doc_id) return;
            }
            index_table[i].doc_ids[index_table[i].doc_count++] = doc_id;
            return;
        }
    }
    strcpy(index_table[index_size].term, term);
    index_table[index_size].doc_ids[0] = doc_id;
    index_table[index_size].doc_count = 1;
    index_size++;
}

void search(char* term) {
    for (int i = 0; i < index_size; i++) {
        if (strcmp(index_table[i].term, term) == 0) {
            printf("Documents containing '%s': ", term);
            for (int j = 0; j < index_table[i].doc_count; j++) {
                printf("Doc%d ", index_table[i].doc_ids[j]);
            }
            printf("\n");
            return;
        }
    }
    printf("Term '%s' not found in any document.\n", term);
}

int main() {
    char* docs[3] = {"the cat sat", "the dog ran", "the cat ran fast"};

    for (int d = 0; d < 3; d++) {
        char buffer[100];
        strcpy(buffer, docs[d]);
        char* token = strtok(buffer, " ");
        while (token != NULL) {
            add_to_index(token, d + 1);
            token = strtok(NULL, " ");
        }
    }

    search("cat");
    search("ran");
    search("fast");

    return 0;
}

Sample Input and Output

Input: Documents ["the cat sat", "the dog ran", "the cat ran fast"], searching for “cat”, “ran”, “fast”.

Output:

Documents containing 'cat': Doc1 Doc3
Documents containing 'ran': Doc2 Doc3
Documents containing 'fast': Doc3

Optimization Techniques

I improve inverted index performance by compressing posting lists using delta encoding (storing gaps between document IDs instead of full IDs), using skip lists within posting lists to speed up intersection, applying stemming and stop-word removal to reduce index size, and sharding the index across multiple machines for very large collections.

Common Mistakes

I’ve noticed people forget to normalize text consistently (case-sensitivity mismatches between indexing and querying), fail to handle duplicate terms within the same document correctly, don’t account for index updates when documents change, and use unsorted posting lists that make intersection slower than necessary.

Further Reading

Exit mobile version