How Search Engines Actually Find Things: Inverted Index, TF-IDF, and KNN

Type a word into a search bar and get results in under a second, out of billions of documents. That’s not magic. It’s a handful of data structures doing very specific jobs.

This post covers three: the inverted index (finds documents fast), TF-IDF (ranks them by relevance), and K-Nearest Neighbors (finds similar items by comparing features, not just keywords). Different problems, same goal: pull the right thing out of a huge pile, fast.

Inverted Index: Find Documents Without Reading All of Them

What it does: Instead of scanning every document every time someone searches, an inverted index flips the relationship. Words become the keys. Documents become the values.

So if “python” shows up in Document 1 and Document 3, the index stores it like this:

python → [Document 1, Document 3]

Search for “python,” and you get the list instantly. No scanning required.

How you build one:

1. Fetch the document.
2. Strip out stop words: “I,” “a,” “an,” “the.” They’re too common to help you find anything.
3. Stem the remaining words down to their root form. “Swimming” becomes “swim.”
4. Add each word to the index.
5. Word’s already a key? Add this document to its list.
6. Word’s new? Create the entry.

Porter’s Stemmer is a common tool for the stemming step.

What that looks like in code

Here’s a simplified version, no stop words or stemming, just the core idea of flipping documents into a word-to-document map:

documents = ["hey x, this is day 13 of 100 days of code",
             "i love 100 days of code as it keeps me accountable"]

wordsInDocs = {}
for idx, doc in enumerate(documents):
    wordsInDocs[f"Document {idx}"] = doc.lower().split()

print(wordsInDocs)
uniqueWords = list(set([item for sublist in wordsInDocs.values()
                              for item in sublist]))
# or   uniqueWords = sum(wordsInDocs.values(), [])

invertedIndex = {}
for word in uniqueWords:
    presentIn = []
    for key, value in wordsInDocs.items():
        if word in value:
            presentIn.append(key)
    invertedIndex[word] = presentIn

for word, documents in invertedIndex.items():
    print(f"{word.title()} is present in {documents}")

Run that on two sentences about 100 Days of Code, and you’ll see words like “code” and “100” mapped to both documents, while unique words map to just one. That’s the whole idea, just without the cleanup steps (stop words, stemming) a production index would add.

The messy part: real-world scale

Real collections don’t just have “words.” They have typos, emojis, hashtags, and every variant in between, and each one can become its own term. A few ways to keep that under control:

• Stop word removal. Cut the high-frequency, low-information words before they clutter the index.
• Stemming vs. lemmatization. Stemming chops words down using rough heuristics. Lemmatization uses actual grammar rules and vocabulary to find the true root. Lemmatization is more accurate, stemming is faster.
• Term dictionary compression. Structures like tries, FSTs (finite state transducers), and block trees keep the term dictionary itself from becoming unwieldy.
• Sharding. Split one massive index across multiple machines instead of cramming it onto one server. You can split by term or by document.

Tiered indexing: not every term gets searched equally often. Keep “hot” terms, the frequently searched ones, in memory. Push “cold” terms to slower storage. Same index, faster average lookup.

TF-IDF: Once You’ve Found the Documents, Rank Them

Finding documents with the word you searched is step one. Step two is figuring out which of those documents actually matters most.

That’s what TF-IDF (Term Frequency to Inverse Document Frequency) is for.

The basic formula:

score = tf × idf

Term Frequency (TF): how often the term shows up in a given document. Show up a lot, and it’s probably important to that document.

Inverse Document Frequency (IDF): how rare the term is across the whole collection. A word that appears in nearly every document (think “the” if you skipped stop-word removal) tells you almost nothing about which document is relevant. A rare word narrows things down fast.

Multiply the two together, and you get a score that favors words that show up a lot in this document, but not everywhere else. That’s usually a good sign of relevance.

K-Nearest Neighbors: Find What’s Similar, Not Just What Matches

Inverted index and TF-IDF both work off text and terms. KNN works differently: it compares data points directly, based on their features.

For classification: look at the k nearest neighbors to a new data point. Whatever category shows up most among them, that’s the category you assign.

For regression: same neighbors, different math. Instead of taking the majority category, you average their values. Classification gives you a category. Regression gives you a number.

How “nearest” gets measured:

In two dimensions, it’s straightforward distance:

sqrt((x2 - x1)^2 + (y2 - y1)^2)

That formula extends to higher dimensions too. But distance isn’t always the right measure. Cosine similarity, comparing the angle between two vectors instead of the distance between two points, often works better, especially when the direction of the data matters more than the raw magnitude. Higher cosine similarity means more similar vectors.

Getting to numbers in the first place: feature extraction

KNN can’t compare raw objects. It needs numbers. Feature extraction is the step that turns an object into a list of comparable values.

Take OCR (optical character recognition): a character gets broken down into features like lines, points, and curves. A new character comes in, gets the same treatment, and KNN compares its features against known examples to figure out what letter it is.

Three Tools, One Job

Each of these answers a different question:

Tool	Question it answers
Inverted index	Which documents contain this term?
TF-IDF	Which of those documents is more relevant?
KNN	Which data points are most similar to this one?

Different mechanics, same underlying problem: pull the relevant thing out of a pile of data, fast enough that nobody notices the pile was ever big.

FAQ

What is an inverted index?

A data structure that maps terms to the documents they appear in, so a search engine can look up matches instantly instead of scanning every document.

Why are inverted indexes useful?

They make it possible to retrieve documents containing a specific term quickly, even across huge collections.

What is TF-IDF?

A scoring method that ranks how relevant a term is to a document, based on how often it appears in that document (term frequency) and how rare it is across all documents (inverse document frequency).

What is K-Nearest Neighbors?

An algorithm that classifies or predicts values for a new data point by comparing it to its closest neighbors in a dataset.

What’s the difference between KNN classification and regression?

Classification assigns the most common category among the nearest neighbors. Regression averages their values instead.

What is cosine similarity?

A way to measure similarity by comparing the angle between two vectors, rather than the straight-line distance between them.

What is feature extraction?

The process of converting an object, like an image or character, into a list of numerical features an algorithm like KNN can compare.